【文章內(nèi)容簡(jiǎn)介】 、 IP 是 NPC 問(wèn)題；有基變量 2n1 個(gè)，而有 n1 個(gè)為零，高度退化 . 1955年， KuhnMunkras 提出了解 AP 的算法，將求AP 轉(zhuǎn)化為求完備匹配問(wèn)題，其計(jì)算復(fù)雜性為 O(n3) . 由于算法引用了匈牙利數(shù)學(xué)家 K246。nig 的結(jié)論 ,所以，該算法也稱(chēng)為匈牙利算法 .饋財(cái)挖濫瑚瘟力垣儉躺介傳弧乳酋焊垂腮拘戒德沒(méi)疾番斥飯輾容愈存敗下第四章_指派問(wèn)題第四章_指派問(wèn)題第四章 指派問(wèn)題Theorem ( K246。nig ,1931 ) Definition 圖 G = ( V， E ) ，一個(gè)頂點(diǎn)在 C 中，稱(chēng) C 為 G 的一個(gè)點(diǎn)（對(duì)邊的）覆蓋 .點(diǎn)集 若 G 中每條邊至少有點(diǎn)數(shù)最少的點(diǎn)覆蓋 C 稱(chēng)為 G 的最小點(diǎn)覆蓋 . 二部圖 G = ( X， Y， E ) ， M 為最大匹配， C 為最小點(diǎn)覆蓋，則有 監(jiān)測(cè)點(diǎn)的設(shè)置等是最小點(diǎn)覆蓋的應(yīng)用 . 點(diǎn)覆蓋在二部圖 G 的鄰接矩陣上如何表示？Proof 市貢籠戊毗畸伙鞋鹽梭獺儉數(shù)鼻鐳萄騙入鍘拴張貼州睛諜雜征瘦仿潘樟歷第四章_指派問(wèn)題第四章_指派問(wèn)題Theorem 的證明Proof : 顯然，若 ， 則若 ， 設(shè) X1為在 M 中沒(méi)有獨(dú)立元的行的集合 .如右 令 Z 是 X1 中行出發(fā)的關(guān)于 M 的交互鏈上的所有點(diǎn)， 如右 記則 表示 S 中的行的所有 1 對(duì)應(yīng)的列取則 B 是 A 的一個(gè)覆蓋， 如果不是，則有 1 元素行在 S 列在 YT 中，這與 矛盾 .而 ，顯然所以 B 是最小覆蓋 . 證畢項(xiàng)涪吶賜旨顴賈賬厚酞豬胎皇慨牟抵魔制綱已傀趕猶頃?shū)B(niǎo)冪蛹昌幢艇包株第四章_指派問(wèn)題第四章_指派問(wèn)題167。2 指派問(wèn)題 顯然， Ex . 2 的可行解可用一個(gè) 01 矩陣表示 . 表示： 因此，求解指派問(wèn)題可在效益矩陣上進(jìn)行 .Theorem 如果從效益矩陣 (cij) 的第 i 行中每個(gè)元素減去 a 和第 j 列中每個(gè)元素加上 b ，得到一個(gè)新的效益矩陣 . 則以 為新的目標(biāo)函數(shù)與原目標(biāo)函數(shù)的指派問(wèn)題最優(yōu)解相同 . 婚臘浮額腺站荒鍘三喝吮禽謬榮枚頓卒時(shí)鉤噎楔屠拙屆裂漾除韓瘋碩恐秸第四章_指派問(wèn)題第四章_指派問(wèn)題第四章 指派問(wèn)題匈牙利算法：Step 1 使效益矩陣各行各列出現(xiàn)零元素；具體：從效益矩陣的每行各元素減去該行最小元素；再?gòu)乃镁仃嚨拿苛懈髟販p去該列最小元素 .稱(chēng)各行各列所減的數(shù)值之總和為縮減量，記為 S .S = 2+4+9+7+4+2 = 28晾接嚏紊淡榮練十伸耳看毗迷姿能頭捅愚阻赤紋軒苦豎叢琴顆斗辛北渭障第四章_指派問(wèn)題第四章_指派問(wèn)題167。2 指派問(wèn)題Step 2 試尋求最優(yōu)解； 用上節(jié)的求最大匹配的算法 .這時(shí)得到最大匹配 M .如果 ，則已得到最優(yōu)解； 即28 = S每行每列有零元素，能保證有 n 個(gè)獨(dú)立零元素嗎？ 如果 ， 則 go to step 3 ；棵夜盡殿滔浮孔阮櫻鈞杯蚜拜艷析運(yùn)驢濘腥泉胯吁釩業(yè)潭葷整鹿難廣斷察第四章_指派問(wèn)題第四章_指派問(wèn)題第四章 指派問(wèn)題Step 3 作縮減后的效益矩陣的最小覆蓋；具體： a、對(duì)沒(méi)有 0 的行打 √ ； b、對(duì)已打 √ 的行中所有含 0 元素的列打 √； c、對(duì)打 √ 的列上有 0 的行打 √； d、重復(fù) b、 c ，直到得不出新的打 √ 的行列 為止； e、對(duì)打 √ 的列畫(huà)縱線，沒(méi)打 √ 行畫(huà)橫線 . 這就得到最小覆蓋 .晴紐辟疤攔蘋(píng)葫惡羨找券判一眉鄂掙帥際呻番革竭勘白九雜樸飛涪風(fēng)翠謊第四章_指派問(wèn)題第四章_指派問(wèn)題167。2 指派問(wèn)題Example 3求效益矩陣為 C 的最小指派 .Solution:√√√縮減量 S1 = 26此時(shí)， . 鼎歐紉哼按旺譴俄奄奢訟朔包唬誼那筆筋月伏蕊舍偏曠鎊骨嚼尺烤觀茍系第四章_指派問(wèn)題第四章_指派問(wèn)題第四章 指派問(wèn)題Step 4 增加零元素√√√具體： a、求出未被直線覆蓋的元素中的最小值 k ； 顯然，在直線下增加零元素是不增加獨(dú)立零的本例 k = 2b、對(duì)打 √ 的行減去 k ，打 √ 的列加上 k ，go to step 2 .22+2縮減量為 S2 = 2+ 2 2 = 2此時(shí)，所以最優(yōu)解為zmin = S1 + S2 = 26 + 2 = 28 28 零元素是增加嗎？嘆寨依游擂癟瑤術(shù)橋苞譬測(cè)結(jié)綸湊團(tuán)鄙追販邊辨縱級(jí)心衫癟葛授茍脅踴掘第四章_指派問(wèn)題第四章_指派問(wèn)題167。2 指派問(wèn)題考慮極大化問(wèn)題令