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

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-  

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

标签： algorithmmatrixgraph-theorygraph-algorithmhungarian-algorithm

Answer 1

如果遇到“死胡同”，则需要寻找增广路径，例如未加权的最大匹配算法。参见例如这些讲义。