二分圖匹配-匈牙利算法和km算法簡介-資料下載頁
2025-02-18 14:43本頁面
【正文】 了二部圖模型。為什么會產(chǎn)生這種截然不同的結(jié)果呢？其一是由于對問題分析的角度不同：模型一以空地為點，模型二以空地為邊；其二是由于對原型中要素的選取有差異：模型一對要素的選取不充分，模型二則保留了原型中 “棋盤 ”這個重要的性質(zhì)。由此可見，對要素的選取，是圖論建模中至關(guān)重要的一步。例題 1 Place the Robots（ ZOJ）小結(jié)例題 2 救護傷員 （ TOJ1148）v無情的海嘯奪取了無數(shù)人的生命 .很多的醫(yī)療隊被派往災(zāi)區(qū)拯救傷員 .就在此時 ,醫(yī)療隊突然發(fā)現(xiàn)自己帶的藥品已經(jīng)不夠用了 ,只剩下了N種。 (1 n = 20)，隨著病人病情的發(fā)展，每種藥在每天能獲得的效果是不一樣的。同時，每天病人只能服用一種藥。也就是說，這些藥還夠支持 N天?，F(xiàn)在，給出你每種藥在每天使用的效果，請你判斷當(dāng)每種藥都用完后所有藥達到的效果之和最大可以是多少。 例題 3 打獵v獵人要在 n*n的格子里打鳥，他可以在某一行中打一槍，這樣此行中的所有鳥都被打掉，也可以在某一列中打，這樣此列中的所有鳥都打掉。問至少打幾槍，才能打光所有的鳥？v建圖：二分圖的 X部為每一行， Y部為每一列，如果 (i,j)有一只鳥，那么連接 X部的 i與 Y部的 j。v該二分圖的最大匹配數(shù)則是最少要打的槍數(shù)。例題 4 最小路徑覆蓋v一個不含圈的有向圖 G中， G的一個路徑覆蓋是一個其結(jié)點不相交的路徑集合 P，圖中的每一個結(jié)點僅包含于 P中的某一條路徑。路徑可以從任意結(jié)點開始和結(jié)束，且長度也為任意值，包括 0。請你求任意一個不含圈的有向圖G的最小路徑覆蓋數(shù)。v理清一個關(guān)系：最小路徑覆蓋數(shù)＝ G的定點數(shù)－最小路徑覆蓋中的邊數(shù)例題 4 最小路徑覆蓋v 試想我們應(yīng)該使得最小路徑覆蓋中的邊數(shù)盡量多，但是又不能讓兩條邊在同一個頂點相交。v 拆點：將每一個頂點 i拆成兩個頂點 Xi和 Yi。然后根據(jù)原圖中邊的信息，從 X部往 Y部引邊。所有邊的方向都是由 X部到 Y部。例題 4 最小路徑覆蓋v因此，所轉(zhuǎn)化出的二分圖的最大匹配數(shù)則是原圖 G中最小路徑覆蓋上的邊數(shù)。因此由最小路徑覆蓋數(shù)＝原圖 G的頂點數(shù)－二分圖的最大匹配數(shù)便可以得解。演講完畢，謝謝觀看！
研究報告相關(guān)推薦
鄂ICP備17016276號-1