赋值算法:如何克服这种情况？

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中的“关于二分图的算法”一节，那么您将看到一个使用广度优先搜索的方法，它要么查找匹配项，要么查找要从行和列中减去的常量。在您引用的示例中，它应该找到一个匹配项。

我没有在维基百科上关于赋值算法的文章中引用它，但根据记忆，我认为匈牙利算法在这个问题上是一个非常有竞争力的算法。