当存在多个最优解时如何用匈牙利算法解决指派问题

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

如果你遇到了“死胡同”，你需要寻找一条增强的路径，就像在未加权的最大匹配算法中一样。例如，参见these lecture notes。