二分圖匹配匈牙利算法和km算法簡(jiǎn)介-文庫(kù)吧資料
2025-02-22 14:29本頁(yè)面
【正文】 于是，問(wèn)題轉(zhuǎn)化為求圖的最大獨(dú)立集問(wèn)題。在同一行或同一列的兩個(gè)機(jī)器人，若它們之間沒(méi)有墻，則它們可以互相攻擊。 KM算法 ?上述算法的證明也很容易 ? Kuhn－ Munkras算法流程： ? (1)初始化可行頂標(biāo)的值 ? (2)用匈牙利算法尋找完備匹配 ? (3)若未找到完備匹配則修改可行頂標(biāo)的值 ? (4)重復(fù) (2)(3)直到找到相等子圖的完備匹配為止 參考文獻(xiàn) ?王樹(shù)禾《離散數(shù)學(xué)引論》 ?吳文虎 王建德《圖論算法與程序設(shè)計(jì)》 ?劉汝佳 黃亮《算法藝術(shù)與信息學(xué)競(jìng)賽》 ? 2023年冬令營(yíng)論文－孫方成 《 偶圖的算法及應(yīng)用》 ? 2023年冬令營(yíng)論文－黃源河《淺談圖論模型的建立與應(yīng)用》 例題 1 Place the Robots（ ZOJ1654） 問(wèn)題描述 有一個(gè) N*M(N,M=50)的棋盤(pán)，棋盤(pán)的每一格是三種類型之一：空地、草地、墻。然后調(diào)整 lx和 ly：對(duì)于訪問(wèn)過(guò)的 x頂點(diǎn)，將它的可行標(biāo)減去 d，對(duì)于所有訪問(wèn)過(guò)的 y頂點(diǎn)，將它的可行標(biāo)增加 d。 KM算法 ?修改方法如下： ?先將一個(gè)未被匹配的頂點(diǎn) u(u in {x})做一次增廣路，記下哪些結(jié)點(diǎn)被訪問(wèn)那些結(jié)點(diǎn)沒(méi)有被訪問(wèn)。證明很容易。 KM算法 ?窮舉的效率－ n！，我們需要更加優(yōu)秀的算法。 ?實(shí)際模型：某公司有職員 x1,x2,…,x n,他們?nèi)プ龉ぷ?y1,y2,…,y n,每個(gè)職員做各項(xiàng)工作的效益未必一致，需要制定一個(gè)分工方案，使得人盡其才，讓公司獲得的總效益最大。 ? Writeln(Bmatch)。 ? Bmatch := 0。 ? end。 ? until stsf。 ? end。 ? exit。 匈牙利算法 ? end。 ? i := t。 ? match2[i] := j。 ? while true do ? begin ? t := match1[j]。 ? father[i] := queue[st]。 ? repeat 匈牙利算法 ? for i:=1 to n do ? if (father[i]=0)and(a
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1