1 回答

TA貢獻(xiàn)1815條經(jīng)驗(yàn) 獲得超10個(gè)贊
對(duì)于二分匹配問(wèn)題,例如分開(kāi)的男性和女性組之間的快速約會(huì),您可以使用最大流算法。
構(gòu)建 4 層圖:
源節(jié)點(diǎn)S
每個(gè)人一個(gè)節(jié)點(diǎn)
每位女性一個(gè)節(jié)點(diǎn)
匯聚節(jié)點(diǎn)T
完全連接第 1 層到第 2 層,邊緣容量為 1
完全連接第 2 層至第 3 層,邊緣容量為 1
完全連接第 3 層至第 4 層,邊緣容量為 1
當(dāng)添加一個(gè)人時(shí),將其添加為第 2 層或第 3 層中的新節(jié)點(diǎn),并如上所述完全連接到相鄰層。
當(dāng)一個(gè)人被移除時(shí),移除他們?cè)诘?2 層和第 3 層的節(jié)點(diǎn)以及他們節(jié)點(diǎn)上的所有邊。
在每一輪中,使用最大流算法來(lái)識(shí)別您的配對(duì)。本輪結(jié)束后,將參與配對(duì)的第2層->第3層邊的容量設(shè)置為0。這樣可以防止相同的兩個(gè)人在后續(xù)輪次中再次匹配。
啟發(fā)式:您可以修改最大流算法,將日期最少或輪次最多的人員配對(duì),因此,如果存在奇數(shù)人數(shù),則最新的人和同一個(gè)人都不會(huì)坐在輪次中。
擴(kuò)展:您可以通過(guò)過(guò)濾第 2 層和第 3 層之間添加的邊集來(lái)實(shí)現(xiàn)首選項(xiàng)來(lái)限制潛在匹配集。
時(shí)間:每輪大約 O(n^3)
對(duì)于任何人對(duì)任何人的匹配問(wèn)題,您必須將最大流算法替換為更復(fù)雜的 Blossom 算法。
與最大流一樣,該算法通過(guò)查找增廣路徑然后修改其當(dāng)前的匹配集來(lái)迭代地細(xì)化匹配。
該算法的輸入是:
為每個(gè)人添加一個(gè)節(jié)點(diǎn)
完全連接所有節(jié)點(diǎn)
與二分情況一樣,在每輪結(jié)束時(shí),刪除與前幾輪匹配的所有邊,以防止相同的兩個(gè)人被匹配。
當(dāng)有新人加入時(shí),添加一個(gè)節(jié)點(diǎn)并將其與其他人完全連接起來(lái)。
當(dāng)一個(gè)人離開(kāi)時(shí),刪除他們的節(jié)點(diǎn)和所有連接的邊。
添加回答
舉報(bào)