当存在多个最优解时，如何用匈牙利算法求解分配问题

Question

我正在尝试用Java实现匈牙利算法。我能够为具有单一最优解的矩阵求解它。然而，当有不止一个最佳解决方案时，我不知道如何解决它(按比例说(。

以矩阵为例。

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   

现在显然有多种解决方案，例如

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

和

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

如何对一个至少能找到其中一个解决方案的方法进行编程？任意分配一个初始值0通常会迫使你进入死胡同。例如，如果在位置0,0分配了0，则会发生以下情况。

0*  0-  0-  0-  
0-  0-  0*  0-  
0-  0*  1-  2-  
0-  0-  3-  4-  

那么，我如何智能地选择最佳解决方案位置呢？

Answer 1

如果你击中一个"死胡同"；您需要寻找一个扩充路径，就像在未加权的最大匹配算法中一样。参见这些课堂讲稿。