1 回答

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