指派問(wèn)題的匈牙利解法

1、歐陽(yáng)數(shù)創(chuàng)編指派問(wèn)題的匈牙利解法1、時(shí)間：2021.03.02創(chuàng)作：歐陽(yáng)數(shù)2、把各行元素分別減去本行元素的最小值；然后在此基 礎(chǔ)上再把每列元素減去本列中的最小值。此時(shí)每行及每列屮肯定都有0元素了。3、確定獨(dú)立零元素，并作標(biāo)記。（1）、首先逐行判斷是否有含右獨(dú)立0元索的行，如果 有，則按行繼續(xù)處理；如沒(méi)有，則要逐列判斷是否有含 有獨(dú)立0元素的列，若有，則按列繼續(xù)處理。若既沒(méi)有 含有獨(dú)立0元素的行，也沒(méi)有含有獨(dú)立0元素的列，則 仍然按行繼續(xù)處理。（2）在按行處理時(shí)，若某行有獨(dú)立0元素，把該0元素 標(biāo)記為“把該0所在的列中的其余0元素標(biāo)記為b；否 貝I，暫時(shí)越過(guò)本行，處理后面的行。把所有含有獨(dú)立0 元

2、素的行處理完畢后，再回來(lái)處理含有2個(gè)以及2個(gè)以 上的0元素的行：任選一個(gè)0做a標(biāo)記，再把該0所在 行中的其余0元素及所在列屮的其余0元素都標(biāo)記為 bo（3）在按列處理時(shí)，若某列有獨(dú)立0元素，把該0元素 標(biāo)記為“把該0所在的行中的其余0元素標(biāo)記為b；否歐陽(yáng)數(shù)創(chuàng)編貝|J,暫時(shí)越過(guò)本列，處理后面的列。把所有含有獨(dú)立0 元素的列處理完畢后，再回來(lái)處理含有2個(gè)以及2個(gè)以 上的0元素的列：任選一個(gè)0做a標(biāo)記，再把該0所在 列中的其余0元素及所在行屮的其余0元素都標(biāo)記為 bo（4）、重復(fù)上述過(guò)程，即得到獨(dú)立零元素（標(biāo)記a的 “0”）4、若獨(dú)立零元素等于矩陣階數(shù)，則已經(jīng)得到最優(yōu)解，若 小于矩陣階數(shù)，則繼續(xù)以下步驟：（1）對(duì)沒(méi)有標(biāo)記a的行作標(biāo)記c（2）、在已作標(biāo)記c的行屮，對(duì)標(biāo)記b所在列作標(biāo)記c（3）、在已作標(biāo)記c的列屮，對(duì)標(biāo)記a所在的行作標(biāo) 記c（4）、對(duì)沒(méi)有標(biāo)記c的行劃線，對(duì)有標(biāo)記c的列劃線6、 這樣必然出現(xiàn)負(fù)元素，所以對(duì)負(fù)元素所在列（或行） 中各元素都加上這一最小元素（Xniin）以消除負(fù)數(shù)。這 樣，再返回步驟2,確定獨(dú)立零元素個(gè)數(shù)。歐陽(yáng)數(shù)創(chuàng)編重復(fù)上述操作，直到找出最優(yōu)解。特殊問(wèn)題:1、若人數(shù)和工彳0 3 118Q 6 6 2用“0”來(lái)補(bǔ)全空位2、 若一個(gè)人可松幾絆事,