賦值算法：我該如何克服這種情況？

Question

http://en.wikipedia.org/wiki/Assignment_problem

我將要描述的是從下講的情況：http://www.youtube.com/watch?v=BUGIhEecipE在32:00 教授解釋了這個問題，但是他並沒有提出任何解決方案，它

假設我們具有下表。該行表示，工人，列中的分配和值的時候一個工人需要完成的任務

3 1 1 4 
4 2 2 5 
5 3 4 8 
4 2 5 9 

起初，我發現每行的最小值，並從所有其他值減去它的量同一行。我做同樣的列和我得到以下結果

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

現在，一個顯而易見的解決方案是工人1取任務4，工人2的任務3，工人3任務2，工人1任務1

但是，使用編程語言，您無法真正找到它。如果讓我選擇的任意我可以選擇例如

工人1，任務1名 工人2，任務2 ，然後我不能選擇任何東西，因爲剩餘的費用大於零。

如果我做滴答過程，我基本上必須勾選所有行和所有列，所以表的值不會真正改變。

我的問題是，如何克服這個問題？有什麼方法可以幫助我實現這個目標嗎？

另外，你能推薦一些更簡單的方法來解決分配問題嗎？這整個滴答過程和減去最小/最大聽起來像不是低時間複雜性的東西

我想實現一個算法，但因爲我可能不得不處理這種情況，我沒有看到實施的東西會變成是錯誤到底

在此先感謝

Answer 1

如果你看看http://en.wikipedia.org/wiki/Hungarian_algorithm節「在二部圖的方面的算法」，然後你會看到一個方法，使用廣度優先搜索，要麼找到一個匹配，要麼找到從行和列中減去的常量。在你引用的例子中，它應該找到一個匹配。

我沒有看到它在維基百科關於分配算法的文章中引用，但從內存中我認爲匈牙利算法是一個相當有競爭力的算法對這個問題。