匹配問題與匈牙利算法和較大基數(shù)匹配

《匹配問題與匈牙利算法和較大基數(shù)匹配》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、圖論-淺談匹配問題1．匹配問題的起源匹配理論起源于組合數(shù)學(xué)中著名的婚配問題：若在一個(gè)團(tuán)體中有若干待婚的小伙子和姑娘，所有人都已到結(jié)婚年齡，若沒有其他條件的限制，為了滿足姑娘的愿望，唯一的必備條件就是小伙子的人數(shù)至少和姑娘的人數(shù)一樣多。但是在事實(shí)上，所有人都不會(huì)草率地處理自己的終身大事，以姑娘為例（與小伙子的情況是完全相同的），每個(gè)姑娘往往會(huì)排除一些小伙子作為她們可能的配偶，也即每個(gè)姑娘都會(huì)有一個(gè)有序的可接受的配偶名單。那么會(huì)有一個(gè)問題出現(xiàn)：在這個(gè)團(tuán)體中是否每個(gè)姑娘都可以嫁給自己認(rèn)可的小伙子？顯然，

2、上述問題并非是永遠(yuǎn)可以的，因?yàn)榛蛟S有幾個(gè)姑娘手頭上的名單是完全一樣的。而既然上述問題并非永遠(yuǎn)可行，那么什么條件下可以滿足上述要求？在并滿足這些條件的時(shí)候，最多會(huì)有幾位姑娘可以實(shí)現(xiàn)自己的愿望？如何配對，才能使得最終的團(tuán)體中婚后的家庭更為美滿？為了解決諸如此類的問題，人們發(fā)展得到了一種匹配理論和諸多有效算法。2．圖論相關(guān)知識若圖G的所有頂點(diǎn)能夠分為兩個(gè)非空子集X和Ｙ，并且每條邊都有一個(gè)頂點(diǎn)在Ｘ中，而另一個(gè)頂點(diǎn)在Y中，則稱此圖是二分圖或者偶圖；而如果X的每個(gè)頂點(diǎn)都與Y的每個(gè)頂點(diǎn)相連，則稱此圖為完全二分圖

3、或者完全偶圖。設(shè)M是圖G=（V,E）的邊集E的子集，如果M的任何兩邊都不鄰接，則稱M為G的一個(gè)匹配；匹配M中邊元素個(gè)數(shù)稱為此匹配的基數(shù)，而在匹配M中邊的端點(diǎn)稱為M-飽和點(diǎn)，其他的端點(diǎn)稱為M-未飽和點(diǎn)。10/10圖論-淺談匹配問題若G中的每個(gè)頂點(diǎn)都是M-飽和點(diǎn)，也即匹配M將G中的所有頂點(diǎn)進(jìn)行了配對，那么稱M為G的完美匹配；而在圖G中不存在另一個(gè)匹配M'，使得M'>M，則稱M為最大匹配，其中M稱為圖G的匹配數(shù)。設(shè)M是G的一個(gè)匹配，G的M交錯(cuò)路是指其邊在EM和M中交錯(cuò)出現(xiàn)的路。M可擴(kuò)路是指其起點(diǎn)和終點(diǎn)

4、都是M未飽和的M交錯(cuò)路。以下結(jié)論是在二分圖中尋找最大匹配和最佳匹配算法的理論基礎(chǔ)：定理1：G的匹配M是最大匹配當(dāng)且僅當(dāng)G不包含M可擴(kuò)路。定理2：設(shè)X，Y為二分圖G的二分類，則G包含飽和X的每個(gè)頂點(diǎn)的匹配當(dāng)且僅當(dāng)N(S)≥S，對所有S?X成立其中N(S)為G中S的臨集，即為與S的頂點(diǎn)相鄰的所有頂點(diǎn)的集合。定理3：G有完美匹配當(dāng)且僅當(dāng)oG-S≤S，對所有的S?V成立其中，oG-S為圖G的奇分支（圖的分支根據(jù)它有奇數(shù)或者偶數(shù)個(gè)頂點(diǎn)而分別稱為奇分支或偶分支）的個(gè)數(shù)。3．幾個(gè)典型的匹配算法由于剛接觸到圖論知

5、識，礙于在圖論方面能力有限，因此本文在本節(jié)中選擇性地介紹了三個(gè)圖論匹配問題中比較經(jīng)典的算法：婚配問題的Gale-Shapley算法、最大匹配的匈牙利算法和圖論中的較大基數(shù)匹配算法，并且對匈牙利算法和較大基數(shù)匹配算法進(jìn)行了matlab代碼實(shí)現(xiàn)。10/10圖論-淺談匹配問題3.1婚配問題婚配問題可以說是一個(gè)相對經(jīng)典的圖論匹配算法的入門問題。假設(shè)對于n個(gè)男人的集合M={m1,m2,?,mn}和n個(gè)女人的集合W={w1,w2,?,wn}。在男人女人進(jìn)行匹配的情況下，就會(huì)產(chǎn)生一個(gè)如何進(jìn)行完美匹配的問題。在這

6、個(gè)問題背景下，進(jìn)一步加入優(yōu)先的概念：根據(jù)實(shí)際情況，每個(gè)男人m∈M將對所有女人進(jìn)行排名，如果m給w的排名高于w'，那么我們就說m偏愛w超過w'，因此我們將把m的按順序的排名作為他的優(yōu)先表。依照常理來看，每個(gè)男人都會(huì)按照自己的優(yōu)先表順序從高向低依次進(jìn)行求婚，直到被接受為止。那么，接下來本文將討論如何生成一個(gè)穩(wěn)定的完美匹配。Gale和Shapley兩人根據(jù)自己對申請人-雇主之間關(guān)系的研究，提出了Gale-Shapley算法，具體算法描述如下：初始所有的m∈M和w∈W都是自由的while存在男人m是自由的

7、且還沒對每個(gè)女人都求過婚選擇這樣的一個(gè)男人m令w為m的優(yōu)先表中還沒有求過婚的最高排名的女人ifw是自由的(m,w）變?yōu)榧s會(huì)狀態(tài)elsew當(dāng)前與m'約會(huì)ifw是更加偏愛m'而不愛mm保持自由elsew更加偏愛m而不愛m'10/10圖論-淺談匹配問題(m,w)變?yōu)榧s會(huì)狀態(tài)m'變?yōu)樽杂蒭ndendend輸出約會(huì)狀態(tài)的所有匹配集合S分析Gale-Shapley算法，可以得到以下結(jié)論：結(jié)論1：G-S算法至多在n2次while循環(huán)的迭代之后終止；結(jié)論2：程序終止時(shí)返回的集合S為一個(gè)完美匹配；結(jié)論3：考慮G-S

8、算法的一次執(zhí)行，結(jié)果為一個(gè)集合S，且S是一個(gè)穩(wěn)定匹配；結(jié)論4：G-S算法的每次執(zhí)行最終得到的匹配集合是相同的；結(jié)論5：穩(wěn)定匹配集合S中，每個(gè)女人與她最差（即排名最低）的有效伴侶匹配。由結(jié)論5，在G-S算法中，主動(dòng)進(jìn)行求婚的一方以最佳可能的穩(wěn)定匹配結(jié)束，而另一方則以最差可能的穩(wěn)定匹配結(jié)束。3.2匈牙利算法二分圖的匹配問題是圖的最大匹配問題的特殊類型。對于一個(gè)二分圖G=（X,Y,E），我們可以利用匈牙利算法對其進(jìn)行最大匹配。其基本的思想為：從G的任意匹配M開始,對X中所有M的非飽和點(diǎn),