it技術(shù)匈牙利算法和km算法簡(jiǎn)介-資料下載頁(yè)
2025-05-21 16:19本頁(yè)面
【導(dǎo)讀】二分圖又稱(chēng)作二部圖，是圖論中的一種特殊。設(shè)G=是一個(gè)無(wú)向圖。依附的兩個(gè)頂點(diǎn)都分屬兩個(gè)不同的子集。給定一個(gè)二分圖G，在G的一個(gè)子圖M中，M. 頂點(diǎn)，則稱(chēng)M是一個(gè)匹配。但是這個(gè)算法的復(fù)。雜度為邊數(shù)的指數(shù)級(jí)函數(shù)。因此，需要尋求一種更。上交替出現(xiàn)，則稱(chēng)P為相對(duì)于M的一條增廣路徑。由增廣路的定義可以推出下述三個(gè)結(jié)論：。1－P的路徑長(zhǎng)度必定為奇數(shù)，第一條邊和最。3－M為G的最大匹配當(dāng)且僅當(dāng)不存在相對(duì)于。用增廣路求最大匹配(稱(chēng)作匈牙利算法，匈牙。找出一條增廣路徑P，通過(guò)取反操作獲得。在主程序中調(diào)用下面的程序即可得出最大匹。如果邊上帶權(quán)的話(huà)，找出權(quán)和最大的匹配叫。,yn,每個(gè)職員做各項(xiàng)工作的效。人盡其才，讓公司獲得的總效益最大。），Kuhn和Munkras給出了一個(gè)解決該問(wèn)。的可行標(biāo)增加d。不屬于M的邊，所以造成M的逐漸增廣。若未找到完備匹配則修改可行頂標(biāo)的值。在同一行或同一列的。人，使它們不能互相攻擊。只是空地和空地之間的聯(lián)系。
【正文】 ：模型一過(guò)于簡(jiǎn)單，沒(méi)有給問(wèn)題的求解帶來(lái)任何便利；模型二則充分抓住了問(wèn)題的內(nèi)在聯(lián)系，巧妙地建立了二部圖模型。為什么會(huì)產(chǎn)生這種截然不同的結(jié)果呢？其一是由于對(duì)問(wèn)題分析的角度不同：模型一以空地為點(diǎn)，模型二以空地為邊；其二是由于對(duì)原型中要素的選取有差異：模型一對(duì)要素的選取不充分，模型二則保留了原型中 “ 棋盤(pán) ” 這個(gè)重要的性質(zhì)。由此可見(jiàn)，對(duì)要素的選取，是圖論建模中至關(guān)重要的一步。 例題 1 Place the Robots（ ZOJ） 小結(jié) 例題 2 救護(hù)傷員 （ TOJ1148） ?無(wú)情的海嘯奪取了無(wú)數(shù)人的生命 .很多的醫(yī)療隊(duì)被派往災(zāi)區(qū)拯救傷員 .就在此時(shí) ,醫(yī)療隊(duì)突然發(fā)現(xiàn)自己帶的藥品已經(jīng)不夠用了 ,只剩下了N種。 (1 n = 20)，隨著病人病情的發(fā)展，每種藥在每天能獲得的效果是不一樣的。同時(shí)，每天病人只能服用一種藥。也就是說(shuō)，這些藥還夠支持 N天?，F(xiàn)在，給出你每種藥在每天使用的效果，請(qǐng)你判斷當(dāng)每種藥都用完后所有藥達(dá)到的效果之和最大可以是多少。 例題 3 打獵 ?獵人要在 n*n的格子里打鳥(niǎo)，他可以在某一行中打一槍?zhuān)@樣此行中的所有鳥(niǎo)都被打掉，也可以在某一列中打，這樣此列中的所有鳥(niǎo)都打掉。問(wèn)至少打幾槍?zhuān)拍艽蚬馑械镍B(niǎo)？ ?建圖：二分圖的 X部為每一行， Y部為每一列，如果 (i,j)有一只鳥(niǎo)，那么連接 X部的 i與 Y部的 j。 ?該二分圖的最大匹配數(shù)則是最少要打的槍數(shù)。 例題 4 最小路徑覆蓋 ?一個(gè)不含圈的有向圖 G中， G的一個(gè)路徑覆蓋是一個(gè)其結(jié)點(diǎn)不相交的路徑集合 P，圖中的每一個(gè)結(jié)點(diǎn)僅包含于 P中的某一條路徑。路徑可以從任意結(jié)點(diǎn)開(kāi)始和結(jié)束，且長(zhǎng)度也為任意值，包括 0。請(qǐng)你求任意一個(gè)不含圈的有向圖G的最小路徑覆蓋數(shù)。 ?理清一個(gè)關(guān)系：最小路徑覆蓋數(shù)＝ G的定點(diǎn)數(shù)－最小路徑覆蓋中的邊數(shù) 例題 4 最小路徑覆蓋 ?試想我們應(yīng)該使得最小路徑覆蓋中的邊數(shù)盡量多，但是又不能讓兩條邊在同一個(gè)頂點(diǎn)相交。 ?拆點(diǎn)：將每一個(gè)頂點(diǎn) i拆成兩個(gè)頂點(diǎn) Xi和 Yi。然后根據(jù)原圖中邊的信息，從 X部往 Y部引邊。所有邊的方向都是由 X部到 Y部。 例題 4 最小路徑覆蓋 ?因此，所轉(zhuǎn)化出的二分圖的最大匹配數(shù)則是原圖 G中最小路徑覆蓋上的邊數(shù)。因此由最小路徑覆蓋數(shù)＝原圖 G的頂點(diǎn)數(shù)－二分圖的最大匹配數(shù)便可以得解。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1