雙方匹配的貪婪算法

所以我遇到了一個問題，其中有'n'飛行員和'm'飛機。每個飛行員都有一張他可以飛行的飛機名單。一名飛行員一次只能飛一架飛機。你必須確定可以同時飛行的最大飛機數量。標準二分配匹配問題（我後來發現）。雙方匹配的貪婪算法

的較量中，我想出了一個貪心算法如下：

雖然在圖面：

1）選擇可以通過最小數量飛行飛機飛行員

2）貪婪地分配一個試點到面（從那些誰可以飛的話）

3）卸下兩個平面和一個從圖中

通常，對於二分匹配問題，我提出以下算法llocated導頻：

雖然有在右組中的二部圖的節點：

1）選擇從與最小傳入度設定權的節點

2）貪婪與任何節點F匹配它從左邊的集合（它有一個邊緣）

3）從圖形中刪除這兩個節點（這也將涉及減少此節點具有邊緣的權利的所有節點的進入度）

我不精通數學證明該算法的正確性和很多的思考後，我一直沒能拿出一個反例。所以我的具體問題是，這是一個標準或已知的算法，或者我做出了一些我看不到的明顯錯誤？

如果您有這種感覺，請隨時編輯我的問題以使其更清晰。謝謝。

來源

2015-11-04 Anirudh

反例：

a1 a2 a3 a4 a5 
p1 x x 
p2 x x x x   
p3 x x x x 
p4     x 
p5   x x x

A5首先選擇。隨機選擇導航，可能是p5。如果是，p4沒有飛機。

來源

2015-11-04 11:49:36 Jur

貪婪的方法不適用於二分匹配。您可能已經猜到的問題是「選擇左側的任何節點」。

這裏是一個例子 - 左邊的節點是A，B，C和D，右邊的節點是x，y，z，t。將A，B，C中的每一個與x，y，z中的每一個連接（所以這裏有9個邊），然後用t連接D，用t連接A。結果你有3個節點在右邊，3度（x，y，z）和1度2度（t）。所以你選擇t，你隨機選擇一個節點 - 這可能是A或D.問題是，如果你選擇A，你的最大匹配將是3，而真正的答案是4（通過選擇D）。

來源

2015-11-04 10:21:07

謝謝！出於好奇，如果我包含一個條件，例如「對於右邊的最小進入度的節點Y，選擇左邊的一個節點x，並且Y的邊緣是這樣的，那麼在所有這樣的x中，它具有最不傳出的程度「？ – Anirudh

不，它不會。但是需要更多時間才能找到反例 –

沒有理由使用貪婪算法！如果你不能證明它的正確性，那麼它是錯誤的。在這裏例如，你的貪婪算法失敗，因爲它的輸出取決於頂點的順序。

你應該看看這篇文章：https://en.wikipedia.org/wiki/Matching_%28graph_theory%29#Algorithms_and_computational_complexity

有例如用於二分圖的高效算法：Hopcroft-Karp

來源

2015-11-04 10:32:34 Labo

我理解並完全同意這個算法是不正確的。但爲了結束，我想找到一個具體的反例。 – Anirudh

你如何選擇圖形中的右側和左側？ – Labo

這沒關係。您可以將任一側設置在二分圖中的左側或右側。 – Anirudh

雙方匹配的貪婪算法

回答

相關問題