匈牙利算法死衚衕

Question

我正在關注Youtube of the Indian guy about the Hungarian problem的教程。我決定在下一步中選擇哪些行和列。他的榜樣沒有我面臨的問題。這裏是我的例子中的表：

2 1 0 0 0 3 
2 0 4 5 2 7 
0 7 0 0 0 5 
3 2 3 1 2 0 
0 0 6 3 3 5 
3 4 5 2 0 3 

讓我們開始一步的行和列的選擇步驟：

1. 第一行包含> 1個零=>進入下一行
2. 選擇（ 2,1）零，並添加（5,1）到懸浮零
3. 第三行包含> 1個零=>去下一行
4. 選擇（4,6）零
5. 選擇（5,1）z的ERO和添加（3,1）到懸浮零
6. 選擇（6,5）零，並添加（3,5），（1,5）到懸浮零

現在，剩下的零點（1,3），（1,4），（3,3），（3,4）

我無法找到一種方法來處理它們，也沒有列明智或行明智。我應該怎麼處理它們？

以下是在端部的表：

2  1  0? 0? 0(su) 3 
3  0(se) 4  5  2  7 
0(su) 7  0? 0? 0(su) 5 
3  2  3  1  2  0(se) 
0(se) 0(su) 6  3  3  5 
3  4  5  2  0(se) 3 

其中

• ス=懸浮
• SE =選擇
• ？ =什麼，我想這樣做

Answer 1

在這個特殊的例子中，我們可以只任意選擇一個0。選擇左上角的一個給了我們

2  1  0(se) 0(su) 0(su) 3 
3  0(se) 4  5  2  7 
0(su) 7  0(su) 0? 0(su) 5 
3  2  3  1  2  0(se) 
0(se) 0(su) 6  3  3  5 
3  4  5  2  0(se) 3 

然後，我們可以選擇最終免費，並完成。

雖然這並不總是工作。考慮

0 0 0 0 
0 0 0 0 
0 0 1 2 
0 0 3 4 

（如果你喜歡的視頻，我使用的是同樣的問題here，但是我會真正解決這個問題。）

我們不能從一開始就選擇什麼，所以我們任意選擇第一個0.

0(se) 0(su) 0(su) 0(su) 
0(su) 0  0  0 
0(su) 0  1  2 
0(su) 0  3  4 

現在我們可以選擇（1,3），因爲它是唯一的空行0。

0(se) 0(su) 0(su) 0(su) 
0(su) 0(su) 0  0 
0(su) 0(se) 1  2 
0(su) 0(su) 3  4 

然後（3,1），因爲它是其列中唯一的空閒0。

0(se) 0(su) 0(su) 0(su) 
0(su) 0(su) 0(se) 0(su) 
0(su) 0(se) 1  2 
0(su) 0(su) 3  4 

這給了我們3個的總任務，但我們需要4個解決的辦法，並沒有更多的可用0的分配。在這一點上可能還沒有解決方案，所以我們需要繼續進行匈牙利算法到繪圖步驟。

G. Srinivasan教授在我鏈接的視頻中瀏覽了此內容，所以我將跳到結果。如果繪製的線數多於我們正在查找的分配數，我們會繼續適當地使用匈牙利算法的其餘部分;如果更少，在前面的步驟中出現了問題，你應該回去檢查你的工作;但如果它是平等的（就像在這個例子中那樣），那麼我們知道這裏有一個我們沒有找到的最優解。

我對有問題的任意賦值的解決方案是更加任意的賦值。第四行是此時沒有賦值的唯一一個，所以我們將從那裏開始並指定其第一個0（暫停的0現在不重要，所以我沒有標記它們）。

0(se) 0  0  0 
0  0  0(se) 0 
0  0(se) 1  2 
0(se) 0  3  4 

這顯然是有問題的，因爲我們已經在第一列中進行了分配。爲了解決這個問題，我們需要將其中一個移動到其他地方。幸運的是，第4行仍然沒有賦值，（1,4）爲零，所以我們可以將（1,1）中的賦值移動到（1,4）。

0  0  0  0(se) 
0  0  0(se) 0 
0  0(se) 1  2 
0(se) 0  3  4 

現在沒有衝突，我們有4個作業，所以這是我們的解決方案。