二分圖匹配算法及其應(yīng)用【畢業(yè)論文】

1、<p><b>　　本科畢業(yè)論文</b></p><p><b>　　（20 屆）</b></p><p>　　二分圖匹配算法及其應(yīng)用</p><p>　　所在學(xué)院 </p><p>　　專業(yè)班級 數(shù)學(xué)與應(yīng)用數(shù)學(xué)

2、 </p><p>　　學(xué)生姓名 學(xué)號 </p><p>　　指導(dǎo)教師 職稱 </p><p>　　完成日期 年 月 </p><p><b>　　摘要</b></p>

3、<p>　　圖的匹配理論簡單的說就是使得圖中每兩個點(diǎn)之間都有聯(lián)系. 匹配理論是圖論中的一個重要內(nèi)容, 它在運(yùn)籌學(xué)、系統(tǒng)工程中都有著廣泛的應(yīng)用, 近幾十年來, 隨著組合數(shù)學(xué)的迅速發(fā)展, 匹配理論成為許多重要理論的基礎(chǔ)和源泉. 二分圖的最大匹配算法是匹配理論研究的熱點(diǎn)之一. KM算法是求最大權(quán)匹配的經(jīng)典算法, 它是在匈牙利算法的進(jìn)一步提高, 它是解決數(shù)學(xué)中一類存在性問題的基本工具, 廣泛應(yīng)用于社會、經(jīng)濟(jì)、科技、自然等各個領(lǐng)域中

4、. 本文主要研究KM算法的具體原理, 步驟, 以及它一些實(shí)際問題中的應(yīng)用. </p><p>　　關(guān)鍵詞: 二分圖; 匹配; KM算法; 應(yīng)用; 工作分派</p><p>　　Binary Chart Matching Algorithms and Its Application</p><p><b>　　Abstract</b></p

5、><p>　　Chart matching theory simply means that it makes every two points in graph have relations. Matching theory is an important content of graph, it has been widely used in both operations research, system e

6、ngineering, in recent decades, with the rapid development of combinatorial mathematics, matching theory has become the foundation and source of many important theories. The biggest matching algorithm of binary chart is t

7、he hot spot of matching theory. KM algorithm is a classical algorithms of obt</p><p>　　Key words: Binary chart; Matching; KM algorithms; Application; Referral</p><p><b>　　目錄</b></

8、p><p><b>　　摘要I</b></p><p>　　AbstractIII</p><p><b>　　1 前言1</b></p><p>　　2 二分圖最大權(quán)匹配的KM算法3</p><p>　　2.1 相關(guān)定義及其定理3</p><p&

9、gt;　　2.2 KM算法的步驟6</p><p>　　3 KM算法的應(yīng)用9</p><p>　　3.1 KM算法在工作分派中的應(yīng)用9</p><p>　　3.2 KM算法在鏡頭檢索中的應(yīng)用13</p><p><b>　　4 小結(jié)16</b></p><p><b>　

10、　參考文獻(xiàn)17</b></p><p><b>　　致謝18</b></p><p><b>　　1 前言</b></p><p>　　現(xiàn)實(shí)世界中, 許多問題的數(shù)學(xué)抽象形式可以用圖來描述, 如互聯(lián)網(wǎng)、通訊網(wǎng)、集成電路、分子結(jié)構(gòu)等. 為了方便對這些問題的探索, 通過幾百年來我們對圖的研究, 從而形成了一個專門

11、的數(shù)學(xué)學(xué)科: 圖論.</p><p>　　圖的匹配理論簡單的說就是使得圖中每兩個點(diǎn)之間都有聯(lián)系. 圖的匹配理論是圖論中的一個重要的內(nèi)容. 近幾年來, 隨著組合數(shù)學(xué)的迅速發(fā)展, 匹配理論成為許多重要的理論的基礎(chǔ)和源泉. 二分圖的最大權(quán)匹配問題已成為匹配理論研究的熱點(diǎn)問題之一, 引起了廣大學(xué)者的研究和關(guān)注, 并應(yīng)用到實(shí)際中. KM算法是解決這類問題的經(jīng)典算法, 二分圖最大權(quán)匹配的KM算法看似簡單, 但二分圖最大權(quán)匹配

12、在數(shù)學(xué)的許多領(lǐng)域中都有著廣泛的應(yīng)用, 同時它的局限性也很明顯. 用KM算法解決二分圖最大權(quán)匹配問題使它的許多重要性質(zhì)仍然得以保留, 成為二分圖最大權(quán)匹配新的研究方向.</p><p>　　圖的匹配問題起源于1935年霍爾的“婚姻問題”. 當(dāng)時他成功地解決了下面問題: 有個小伙子和個姑娘, 每個小伙子認(rèn)識個姑娘中的某些人, 問在什么條件下每個小伙子能夠找到一個他認(rèn)識的姑娘結(jié)婚? 該問題抽象為圖論問題為用個頂點(diǎn)代表個

13、小伙子, 用個頂點(diǎn)代表個姑娘. 當(dāng)且僅當(dāng)小伙子認(rèn)識姑娘時在和之間連一條邊. 上面問題則抽象為在什么條件下這個圖中存在條邊分別以為端點(diǎn), 使這些邊中任意兩條邊都沒有公共端點(diǎn)? 很顯然對于“婚姻問題”有解的一個必要條件是任意個小伙子認(rèn)識的姑娘總數(shù)至少為個. 霍爾證明了這個條件也是充分的. 這就構(gòu)成了一個關(guān)于二分圖的匹配問題. 而在上面問題中加上一個條件, 就是每位小伙子對各個姑娘的喜歡程度又各不相同, 并將每位小伙子對各個姑娘的喜歡程度賦予

14、為每條邊的權(quán)值, 這就將求二分圖的完全匹配問題轉(zhuǎn)化為求二分圖的最大權(quán)匹配問題. 而KM算法是Kuhn和Munkras分別于1955年和1957年獨(dú)立提出來的, 這是求解二分圖最優(yōu)匹配的經(jīng)典算法.</p><p>　　劉桂真[1]對二分圖最大權(quán)匹配開討論, 介紹了二分圖最大權(quán)匹配并將匹配問題從“婚姻問題”推廣到工作分派問題.</p><p>　　耿素云[2]通過對二分圖的匹配及帶權(quán)圖的應(yīng)用進(jìn)

15、行了討論并其運(yùn)用到實(shí)際中, 以此解決了最短路徑的問題、關(guān)鍵路徑問題以及中國郵遞員問題. </p><p>　　楊勝超、張瑞軍[3]在介紹畢業(yè)論文選題系統(tǒng)的系統(tǒng)用例、功能模塊、和流程圖的基礎(chǔ)上, 針對學(xué)生選題不均衡這一突出問題, 引出了二分圖最大權(quán)匹配的經(jīng)典算法—KM算法, 該算法能夠根據(jù)學(xué)生的題目預(yù)選、自命題、未定題等多種情況, 完成題目與學(xué)生的智能匹配, 使最終題目的整體滿意度最高, 從而提高學(xué)生畢業(yè)論文選題質(zhì)

16、量. 該系統(tǒng)在武漢科技大學(xué)管理學(xué)院04級畢業(yè)論文選題中實(shí)施.</p><p>　　謝政、程浩光[4]利用賦雙權(quán)的二分圖中求關(guān)于第一個權(quán)最大的限制下、第二個權(quán)最小的完美匹配的網(wǎng)絡(luò)模型, 給出了這一模型的有效性, 并用此算法解決了企業(yè)的優(yōu)化組合分工中的挖潛問題.</p><p>　　彭宇新、Ngo Chong-Wah、肖建國[5]嘗試將二分圖的最大權(quán)匹配用于鏡頭檢索. 把兩個鏡頭的相似度度量建

17、模為一個帶權(quán)的二分圖: 鏡頭中的每一幀看成二分圖的一個結(jié)點(diǎn), 兩個鏡頭之間任意幀的相似值作為邊的權(quán)值. 在一一對應(yīng)的前提下, 利用最大權(quán)匹配的KM算法求出該二分圖的最大權(quán), 以此作為兩個鏡頭的相似度. 考慮到檢索的速度的問題, 提出了兩個改進(jìn)算法.</p><p>　　對于二分圖最大權(quán)匹配的算法有不少, 如: 頂點(diǎn)標(biāo)記法等. 但KM算法是求解二分圖最大權(quán)匹配的經(jīng)典算法. </p><p>

18、　　本文主要研究用KM算法解決二分圖最大權(quán)匹配的步驟過程及二分圖最大權(quán)匹配算法的應(yīng)用. 特別是在解決工作分派問題上以及其他實(shí)際問題中的應(yīng)用.</p><p>　　2 二分圖最大權(quán)匹配的KM算法</p><p>　　二分圖最大權(quán)匹配的KM算法看似簡單, 但二分圖最大權(quán)匹配在數(shù)學(xué)的許多領(lǐng)域中都有著廣泛的應(yīng)用. 本文首先給出KM算法的描述.</p><p>　　2.1

19、定義及其定理</p><p>　　定義2.1 圖由三部分組成</p><p>　　(1) 非空集合, 稱為的結(jié)點(diǎn)集, 其成員稱為結(jié)點(diǎn)或頂點(diǎn).</p><p>　　(2) 集合, 稱為的邊集, 其成員稱為邊.</p><p><b>　　(3) 函數(shù)</b></p><p><b>　　

20、,</b></p><p>　　稱為邊和頂點(diǎn)的關(guān)聯(lián)映射. 這里稱為的偶對集, 其成員偶對形如, 稱,為結(jié)點(diǎn), 它們未必不同. 當(dāng)時, 稱邊關(guān)聯(lián)端點(diǎn),. 當(dāng)用作序偶時</p><p><b>　　,</b></p><p>　　稱為有向邊, 以為起點(diǎn), 以為終點(diǎn), 圖稱為有向圖; 當(dāng)用作無序偶對時, , 稱為無向邊(或邊), 圖稱為無

21、向圖(或圖).</p><p>　　定義2.2 無向圖稱為二分圖, 如果有非空集合, 使</p><p><b>　　, ,</b></p><p>　　且對每一, , , . 此時常用表示二分圖. 若對中任一及中的任一恰有一邊, 使, 則稱為完全二分圖. 當(dāng), 時, 完全二分圖記為.</p><p>　　定義2.3

22、 圖的頂點(diǎn)到頂點(diǎn)的擬路徑是指如下頂點(diǎn)與邊的序列:</p><p>　　其中為的頂點(diǎn), 為的邊, 且以及為端點(diǎn)(對有向圖, 以為起點(diǎn), 以為終點(diǎn)). 當(dāng)各不相同時, 該擬路徑稱為路徑.</p><p>　　定義2.4 若是二分圖的一個匹配. 設(shè)從圖中的一個頂點(diǎn)到另一個頂點(diǎn)存在一條路徑, 這條路是由屬于的邊和不屬于的邊交替出現(xiàn)組成的, 則稱這條路為增廣路(或稱交互樹或交錯樹). 如果增廣路

23、的首尾兩個頂點(diǎn)不屬于, 則稱這條路為可增廣路.</p><p>　　由增廣路的定義可以推出下述三個結(jié)論</p><p>　　(1) 增廣路的頂點(diǎn)個數(shù)必定為奇數(shù), 第一條邊和最后一條邊都不屬于;</p><p>　　(2) 將和進(jìn)行取反操作可以得到一個更大的匹配;</p><p>　　(3) 為的最大匹配當(dāng)且僅當(dāng)不存在的增廣路.</p&g

24、t;<p>　　匈牙利算法就是利用增廣路來求最大匹配的算法, 它可把中任一匹配擴(kuò)充為最大匹配. 該算法是匈牙利人Edmonds于1965年提出的.</p><p><b>　　算法輪廓</b></p><p><b>　　(1) 置為空;</b></p><p>　　(2) 找出一條增廣路徑, 通過取反操作獲

25、得更大的匹配代替;</p><p>　　(3) 重復(fù)(2)操作直到找不出增廣路徑為止.</p><p>　　定義2.5 設(shè)為二分圖, 當(dāng)給賦予映射或, 為任意集合、常用實(shí)數(shù)集及其子集, 此時為賦權(quán)圖, 常用或或表示之. 稱為結(jié)點(diǎn)的權(quán), 稱為的權(quán).</p><p>　　定義2.6 設(shè)為二分圖, . 稱為的一個匹配, 如果中任何兩條邊都沒有公共端點(diǎn). 的所有匹配中邊

26、數(shù)最多的匹配稱為最大匹配, 其邊數(shù)稱為匹配數(shù). 如果()中任一頂點(diǎn)均為匹配中邊的端點(diǎn), 那么稱為()—完全匹配. 若既是—完全匹配又是—完全匹配, 則稱為的完全匹配.</p><p>　　定義2.7 設(shè)二分圖, 其中==匹配數(shù), 中每條邊有權(quán), 若能找到一個匹配(=匹配數(shù)), 滿足所有匹配的邊權(quán)和最大(或最小), 則稱為的一個最大(或最小)權(quán)匹配.</p><p>　　定義2.8 稱圖

27、中頂點(diǎn)到是可達(dá)的, 如果, 或者有一條到的路徑. 如果的任何兩個頂點(diǎn)都是互相可達(dá)的, 稱無向圖是連通的. 如果是的子圖, 是連通的, 并且不存在的真子圖, 使是連通的, 且以為真子圖, 則圖稱為圖的連通分支.</p><p>　　定理2.1(霍爾定理) 設(shè)圖. 有—完全匹配的充分必要條件是: 對每一, 其中為的鄰域, 即, 則有</p><p><b>　　.</b>

28、;</p><p>　　證明 必要性是易證的. 設(shè)有—完全匹配</p><p>　　其中諸互不相同, 諸也各不一樣, 因此對任一, 中有多少元素, 中至少也有同樣多的元素, 及.</p><p>　　現(xiàn)在證明充分性. 設(shè)為中一個最大匹配, 下面證明是—完全匹配. 否則必存在為的非飽和點(diǎn), 且必存在邊()與關(guān)聯(lián), 否則將是孤立點(diǎn), 這與已知條件相矛盾, 且中頂點(diǎn)均為

29、飽和點(diǎn). 否則, 若存在, 且也是非飽和點(diǎn), 令, 則也是中的匹配且比多一條, 這與是最大匹配相矛盾.</p><p>　　考慮從出發(fā)的盡可能長的所有增廣路, 這些增廣路都不是可增廣的, 即每條路徑均以的飽和點(diǎn)結(jié)束. 令</p><p>　　={|且在出發(fā)的增廣路上},</p><p>　　={|且在出發(fā)的增廣路上}.</p><p>　　由

30、于各路徑的始點(diǎn)與終點(diǎn)均在, 所以, . 可是, 于是, 這矛盾與已知條件, 故中不存在非飽和點(diǎn), 因而是中的完全匹配. </p><p>　　定理2.2(Tutte定理) 一個圖有完全匹配當(dāng)且僅當(dāng)對圖的任意頂點(diǎn)子集有圖的奇分支數(shù)不大于中的頂點(diǎn)數(shù), 其中表示從圖中刪去頂點(diǎn)集及其關(guān)聯(lián)的邊所得的圖, 圖的奇分支是指奇數(shù)個頂點(diǎn)的連通分支. 即</p><p>　　有完全匹配任意, , 其中用表示

31、圖的奇分支個數(shù).</p><p>　　證明 設(shè)是的完全匹配, 是的奇階連通分支, 存在, 存在, , 所以.</p><p>　　(對階數(shù)歸納)取, 得是偶階. 取, 得恰有一個奇階連通分支. 設(shè)是使得的最大集合, 是的所有奇階連通分支, 是的所有偶階連通分支.</p><p>　　(1) 每個內(nèi)部都有完全匹配., </p><p>&l

32、t;b>　　,</b></p><p>　　所以, 由歸納假設(shè), 內(nèi)部有完全匹配.</p><p>　　(2) 每個內(nèi)部有完全匹配, 其中.(反證)假設(shè), , 因兩端同奇偶, 故.</p><p>　　這與的最大性矛盾. </p><p>　　(3) 有完全匹配. , 令, 則, 即滿足霍爾定理條件, 所以有完全匹配. &l

33、t;/p><p>　　于是的完全匹配有(1)(2)(3)三部分構(gòu)成.</p><p>　　定理2.3 若由二分圖中所有滿足的邊構(gòu)成的子圖(稱做相等子圖)有完全匹配, 那么這個完全匹配就是二分圖的最大權(quán)匹配. </p><p>　　2.2 KM算法的步驟</p><p>　　當(dāng)二分圖為賦權(quán)圖時, 要求它的最大權(quán)匹配(特殊地, 當(dāng)?shù)乃羞厵?quán)為1或

34、相等時, 就是求完全匹配問題), 我們一般用KM算法.</p><p>　　Kuhn－Munkras算法(即KM算法)流程</p><p>　　(1) 初始化可行頂標(biāo)的值;</p><p>　　(2) 用匈牙利算法尋找完全匹配;</p><p>　　(3) 若未找到完全匹配則修改可行頂標(biāo)的值;</p><p>　　(4

35、) 重復(fù)(2)(3)直到找到相等子圖的完全匹配為止.</p><p>　　KM算法是通過給每個頂點(diǎn)一個標(biāo)號(我們有時稱之為頂標(biāo))來把求最大權(quán)匹配的問題轉(zhuǎn)化為不斷地尋找增廣路以使二分圖的匹配數(shù)達(dá)到最大的完全匹配的問題. 我們令二分圖中部的節(jié)點(diǎn)的頂標(biāo)為. 部的節(jié)點(diǎn)的頂標(biāo)為. 部與部節(jié)點(diǎn)之間的權(quán)值為. 要求在算法執(zhí)行過程中的任一時刻, 對于任一條邊, 使得始終成立. 在初始時, 令為所有與頂點(diǎn)關(guān)聯(lián)的邊的權(quán)值的最大值,

36、令. 如果當(dāng)前的相等子圖沒有完全匹配, 就需要修改頂標(biāo)以使擴(kuò)大相等子圖, 直到相等子圖具有完全匹配為止(這樣就可以求出最大權(quán)匹配).</p><p>　　如果當(dāng)前相等子圖找不到完全匹配, 那么是因為對于某個頂點(diǎn), 我們找不到一條從它出發(fā)的增廣路. 這時為了獲得了一條增廣路, 現(xiàn)在我們把增廣路中的頂點(diǎn)的頂標(biāo)全都減小某個值, 的頂點(diǎn)的頂標(biāo)全都增加, 就可以使得至少有一條新邊進(jìn)入相等子圖. 那么我們會發(fā)現(xiàn):</p

37、><p>　　(1) 兩端都在增廣路中的邊, 的值沒有變化. 也就是說, 它原來屬于相等子圖, 現(xiàn)在仍屬于相等子圖.</p><p>　　(2) 兩端都不在增廣路中的邊, 和都沒有變化. 也就是說, 它原來屬于(或不屬于)相等子圖, 現(xiàn)在仍屬于(或不屬于)相等子圖.</p><p>　　(3) 端不在增廣路中, 端在增廣路中的邊, 它的的值有所增大. 它原來不屬于相等子

38、圖, 現(xiàn)在仍不屬于相等子圖.</p><p>　　(4) 端在增廣路中, 端不在增廣路中的邊, 它的的值有所減小. 也就說, 它原來不屬于相等子圖, 現(xiàn)在可能進(jìn)入了相等子圖, 因而使相等子圖得到了擴(kuò)大.</p><p>　　現(xiàn)在的問題就是求值了. 為了使始終成立, 且至少有一條邊進(jìn)入相等子圖, 則, 而且在增廣路中, 不在增廣路中. KM算法的偽代碼如下:</p><p

39、>　　For to </p><p>　　將和所有的頂點(diǎn)初始化為未掃描</p><p>　　If path () 返回值為真then</p><p><b>　　進(jìn)行下一值的循環(huán)</b></p><p><b>　　Else</b></p><p>　　令(其

40、中在增廣路中, 不在增廣路中)</p><p><b>　　For to </b></p><p>　　If 節(jié)點(diǎn)已被掃描過then</p><p><b>　　減去</b></p><p><b>　　End if</b></p><p><

41、b>　　End for</b></p><p><b>　　End if</b></p><p><b>　　End for</b></p><p>　　/ / / / / / / / / 以下是遞歸函數(shù)path(int ) / / / / / / / / / / </p><p>

42、;　　Function Boolean path(int )</p><p><b>　　標(biāo)記節(jié)點(diǎn)為掃描的</b></p><p>　　For to </p><p>　　If 節(jié)點(diǎn)未掃描且等于then標(biāo)記節(jié)點(diǎn)為掃描過的</p><p>　　If節(jié)點(diǎn)還未被匹配 或者調(diào)用函數(shù)path(match[])的返回值為真

43、then</p><p>　　將賦值給match[]</p><p><b>　　返回真</b></p><p><b>　　End if</b></p><p><b>　　End if</b></p><p><b>　　End for&l

44、t;/b></p><p><b>　　返回假</b></p><p>　　End funtion</p><p>　　3 二分圖最大權(quán)匹配的KM算法的應(yīng)用</p><p>　　KM算法應(yīng)用很廣泛, 在工作分派問題以及許多實(shí)際問題上有重要的應(yīng)用. </p><p>　　3.1 KM算法在工

45、作分派中的應(yīng)用</p><p>　　如果匹配問題僅僅用在“婚姻問題”上, 那么它就沒有太大的意義. 匹配問題在實(shí)際中有許多用處. 最廣泛應(yīng)用的是工作分派問題.</p><p>　　假設(shè)有個人和件工作, 每個人能夠做其中的樣工作, 問是否能夠存在一種分配方案使每個人能夠去做一件他勝任的工作? 顯然該問題與前面的“婚姻問題”本質(zhì)上是一樣的. 我們可以用一個二分圖來表示這個問題, 其中表示個人的

46、集合, 為表示件工作. 若表示某個人的頂點(diǎn)與表示工作的頂點(diǎn)間有邊相連當(dāng)且僅當(dāng)這第個人能夠做第種工作. 更廣泛地, 有下面的最優(yōu)分派問題. 即在前面問題的基礎(chǔ)上加上第個人做第件工作的效率. 要找一個工作效率最高的分配方案. 該問題抽象為在二分圖中找最大權(quán)匹配問題. KM算法是解決上述最有匹配問題的經(jīng)典算法. </p><p><b>　　它們數(shù)學(xué)模型如下</b></p><

47、p>　　是加權(quán)完全二分圖, 的二分圖劃分為,;, , 是工作人員做工作時的效益, 求權(quán)最大的完全匹配, 這種完全匹配稱為最佳匹配.</p><p>　　Kuhn-Munkras算法步驟</p><p>　　(1) 選定初始的可行頂標(biāo), 確定, 在中選取一個匹配.</p><p>　　(2) 中頂點(diǎn)皆被許配為止, 即為最佳匹配; 否則, 取中未被許配的頂點(diǎn),令

48、, 為空.</p><p>　　(3) 若真包含, 轉(zhuǎn)(4); 若, 取</p><p><b>　　;</b></p><p><b>　　.</b></p><p>　　(4)選中一頂點(diǎn), 若已被許配, 且, 則, 轉(zhuǎn)(3); 否則, 取中一個的可增廣軌, 令, 轉(zhuǎn)(2).</p>

49、<p>　　例3.1 設(shè)有帶權(quán)完全二分圖的鄰接矩陣, </p><p><b>　　.</b></p><p><b>　　求它的最大權(quán)匹配.</b></p><p>　　解 (1)取可行頂標(biāo)為;, </p><p><b>　　, .</b></p>

50、<p><b>　　初始標(biāo)號為</b></p><p><b>　　其等式及匹配如圖</b></p><p>　　(2) , , . 擴(kuò)展交互道路: , . , 轉(zhuǎn)(3), 修改標(biāo)號.</p><p>　　(3), 則修改標(biāo)號為</p><p><b>　　新等式子圖為<

51、;/b></p><p><b>　　,</b></p><p><b>　　,</b></p><p><b>　　,</b></p><p>　　是不飽和的, 找到可增廣道路, , , 擴(kuò)張匹配, 轉(zhuǎn)(2), 檢查新匹配是否完美.</p><p&g

52、t;　　新的匹配是完美的, 其權(quán)為6+8+4, 這也是結(jié)點(diǎn)標(biāo)號之和.</p><p><b>　　已知的權(quán)矩陣為</b></p><p>　　求最佳匹配, 其中的頂點(diǎn)劃分為, , . </p><p>　　解 (1) 取可行頂標(biāo)為 .</p><p>　　(2) 及其以上匹配見圖3.1. 這個圖中, 由Tutte定理知無

53、完備匹配, 需要修改頂標(biāo).</p><p>　　(3) , 得, , , 于是</p><p><b>　　.</b></p><p>　　的頂點(diǎn)分別修改為4, 2, 3, 0, 3; 的頂點(diǎn)分別修改為0, 1, 1, 0, 0.</p><p>　　(4) 用修改后的頂標(biāo)得及其上面的一個完備匹配如圖3.2. 圖中粗實(shí)線

54、給出了一個最佳匹配, 其最大權(quán)是2+4+1+4+3=14. </p><p>　　我們看出: , 修改后的頂標(biāo)仍是可行頂標(biāo); 中仍含中的匹配, 中至少會出現(xiàn)不屬于的一條邊, 所以會造成的逐漸增廣.</p><p><b>　　圖3.1</b></p><p><b>　　圖3.2</b></p><p

55、>　　KM算法可以很好地解決在選題系統(tǒng)中, 題目與學(xué)生最優(yōu)配的問題. 在匹配過程中, 令學(xué)生集合為, 題目集合為, 學(xué)生對自己預(yù)選題目的滿意度為二維矩陣, 其它題目規(guī)定其權(quán)值為0. 系統(tǒng)在初始化時要求: 學(xué)生最多只能預(yù)選5個題目, 并按照自己對題目的滿意度由高到底排序, 其滿意度分別為0.9, 0.8, 0.7, 0.6和0.5, 該滿意度可以由管理員根據(jù)需要進(jìn)行修改, 其取值范圍是0到1之間.</p><p&

56、gt;　　數(shù)組表示題目被分配給學(xué)生.</p><p>　　在使用KM算法時, 有一個條件: 要求集合的定點(diǎn)個數(shù)必須等于集合的個數(shù)(際上, 經(jīng)分析后發(fā)現(xiàn), 對于初始化頂標(biāo)為0的集合的頂點(diǎn)個數(shù)大于另一個集合的頂點(diǎn)的個數(shù)時, 該算法同樣適用). 但當(dāng)應(yīng)用在選題系統(tǒng)中時, 由于無法預(yù)先確定是學(xué)生人數(shù)多還是題目個數(shù)多, 所以使用KM算法進(jìn)行匹配運(yùn)算時規(guī)定: 如果參加預(yù)選題目的學(xué)生人數(shù)大于被題目數(shù), 就添加一些空題目節(jié)點(diǎn)使得

57、, 與其相關(guān)的權(quán)值都為0; 同樣, 如果, 就添加一些學(xué)生節(jié)點(diǎn)使得, 與其相關(guān)的權(quán)值也都為0.</p><p>　　在經(jīng)過智能算法匹配后, 去掉那些添加的空節(jié)點(diǎn)的匹配和權(quán)值為0的匹配(如果有的話), 從而數(shù)組中剩下的就是學(xué)生與題目的最優(yōu)匹配方案.</p><p>　　3.2 KM算法在鏡頭檢索中的應(yīng)用</p><p>　　把二分圖的最優(yōu)匹配運(yùn)用到鏡頭檢索中, 可以

58、這樣表述鏡頭檢索問題: 設(shè)鏡頭有幀, 鏡頭有幀, 其中邊表示與相似, 表示與的相似值, 要求與必須一一對應(yīng)而不能多對一或多對多, 問: 能使總的相似值度最大的匹配? 這樣得到的匹配反映了鏡頭和鏡頭在一一對應(yīng)的條件下, 所能達(dá)到的最大相似度, 因此, 把它作為這兩個鏡頭的相似度. 有這個表述, 可以知道, 最大權(quán)匹配方法的實(shí)質(zhì)是在一一對應(yīng)的前提下, 衡量兩個鏡頭所能達(dá)到的最大相似度. 應(yīng)為不重復(fù)計算每一幀的相似度, 而著眼于兩個鏡頭所能達(dá)

59、到的最大相似度, 所以這個方法能夠全面客觀地衡量兩個鏡頭內(nèi)部的相似程度.</p><p>　　KM算法是解決上述最有匹配問題的經(jīng)典算法. 把兩個鏡頭和每對幀的相似值賦給的每條邊, 這時的就轉(zhuǎn)化為一個帶權(quán)的完全二分圖.</p><p>　　具體的KM算法如下:</p><p>　　給出初始標(biāo)號, , ;</p><p>　　求出邊集、及中的一個

60、匹配(, 并且中任意兩邊都不相鄰);</p><p>　　如已飽和的所有結(jié)點(diǎn), 則既是的最有匹配, 計算結(jié)束, 否則進(jìn)行下一步;</p><p>　　在中找一非飽和點(diǎn), 令, , , 是兩個集合;</p><p>　　若, 則轉(zhuǎn)第(9)步, 否則進(jìn)行下一步, 其中, 是與中結(jié)點(diǎn)連接的結(jié)點(diǎn)集合;</p><p><b>　　找一結(jié)點(diǎn);

61、</b></p><p>　　若是飽和點(diǎn), 則找出的配對點(diǎn), 令, 轉(zhuǎn)第(5)步, 否則進(jìn)行下一步;</p><p>　　存在一條從到的可增廣路, 令, 轉(zhuǎn)第(3)步;</p><p>　　按下式計算值: , 修改標(biāo)號: </p><p><b>　　根據(jù)求及;</b></p><p>

62、;　　, , 轉(zhuǎn)第(6)步.</p><p>　　KM算法的時間復(fù)雜度是, . 求出的最有匹配后, 把每條邊的權(quán)值相加, 可以求得的最大權(quán). 這里定義兩個鏡頭和視覺相似度. 使用將歸一化到0, 1之間, 值越大, 表明和越相似.</p><p><b>　　4 小結(jié)</b></p><p>　　二分圖最大權(quán)匹配的KM算法看似簡單, 但二分圖最大

63、權(quán)匹配在數(shù)學(xué)的許多領(lǐng)域中都有著廣泛的應(yīng)用, 同時它的局限性也很明顯. 使用KM算法解決二分圖最大權(quán)匹配在更廣泛的領(lǐng)域內(nèi)得到推廣, 使它的許多重要性質(zhì)仍然得以保留, 成為二分圖最大權(quán)匹配新的研究方向.</p><p>　　本文主要研究用KM算法解決二分圖最大權(quán)匹配的步驟過程及二分圖最大權(quán)匹配算法的應(yīng)用. 特別是在解決工作分派問題上以及其他實(shí)際問題中的應(yīng)用.</p><p><b>

64、　　參考文獻(xiàn)</b></p><p>　　劉桂真. 圖與網(wǎng)絡(luò)—優(yōu)化決策的圖論方法 [M]. 上海: 上?？茖W(xué)技術(shù)出版社, 2008. </p><p>　　耿秋云. 集合論與圖論 [M]. 北京: 北京大學(xué)出版社, 1997. </p><p>　　楊勝超, 張瑞軍. 基于二分圖最優(yōu)匹配算法的畢業(yè)論文選題系統(tǒng) [J]. 計算機(jī)系統(tǒng)應(yīng)用, 2008, (

65、07):14~17. </p><p>　　謝政、程浩光. 賦雙權(quán)二部圖中最大權(quán)最小權(quán)完美匹配 [J]. 國防科技大學(xué)報, 1994, 16(4): 98~101.</p><p>　　彭宇新, Ngo Chong-Wah, 肖建國. 一種基于二分圖最優(yōu)匹配的鏡頭檢索方法 [J]. 電子學(xué)報, 2004, (07): 1135~1139. </p><p>　　Ke

66、nneth H.Rosen. Discrete Mathematics and Its Applications, Fourth Edition [M]. New York: North-Holland, 2002. </p><p>　　Weat D B. Introduction to Graph Theory [M]. prentice Hall, 2001.</p><p>　　肖