最大二分組匹配方法中的錯誤

具有源和宿的二部圖如下所示。每個邊緣的容量爲1個單元： Source : GeeksforGeeks 最大二分組匹配方法中的錯誤

我試圖找到從源到匯的最大流量。一種方法是使用Ford-Fulkerson最大流問題算法，該算法適用於所有圖。我發現了一種簡單的方法來查找最大流量（太簡單了，無法正確！），我無法在該方法中找到任何錯誤。

方法：

C1 =計數具有非零數量從它始發，在具有出邊頂點列表邊緣的頂點的數量。

c2 =在具有傳入邊的頂點列表中計數具有非零邊數的頂點收斂於其中的數量。

的最大流將是最小的這兩個數字，即，分鐘（C1，C2）。由於任何路徑需要從出射頂點列表中的一個頂點，以及從傳入頂點列表其他。]

任何幫助，將不勝感激。

來源

2016-01-24 gautamk

考慮像

*--* 
/
/
* * 
/
/
*--*

圖（由連接的組件工作不解決的事情的補丁;左下連接到右上）。

來源

2016-01-24 16:36:05

非常感謝。我正在尋找這個。 – gautamk

這是我在堆棧溢出中的第一個問題。不知道這件事。謝謝。 – gautamk

還沒有一個確切的答案，但我有一個可以工作的迭代算法。對我來說，你顯然需要平衡流動，以便它分佈在可以將它發送到可以接收它的右頂點的左頂點。假設您使用包含二部分鏈接的矩陣A爲您的情況建模。那麼你可以假設，如果你的矩陣恰好包含了流量（在0和1之間）你想通過一個邊緣，那麼給出這個決定的總流量是b = A * a其中a是一個向量。如果您從A的最大容量開始，將所有其他邊緣置於其中一個，並將所有其他邊緣置於0，則可能有一些b的元素多於1，但可以減少它們對應的A元素，以使它們流過較少的流量。然後您可以恢復流量並查看您的雙向部件的最大接收容量是多少，並使用a = A'b進行測試。再一次，你可能有一個超過1的元素，這意味着理想的流量將大於從源到元素的可能容量，並減少流量中的這些元素。使用這種乒乓算法並減少逐漸修正，你保證會收斂在最佳矩陣。給出最終的b = A a，其矢量爲1，則最大流量爲總和（b）。查看下面的八度碼，我用B作爲收斂矩陣，讓我知道你的評論。

A=[0 1 0 1;1 0 0 1;1 1 0 0;0 0 1 0]; 
B=A; 
repeat 
    b=B*ones(4,1); 
    B=B.*([.8 .8 .8 1]'*ones(1,4)); 
    a=B'*ones(4,1) 
    B=B.*(ones(4,1)*[.9 .9 1 .9]); 
until converge 
maxflow=sum(b)

來源

2016-01-24 17:12:35 hjohanns

最大二分組匹配方法中的錯誤

回答

相關問題