hungarian-algorithm - 匈牙利算法

Question

我找到了匈牙利算法的实现，但我对“零星号”和“零星号”的含义有疑问。我认为这用于指代标记的零，但我不确定。这是对的吗？

这是代码：http ://ccp.uchicago.edu/khetarpal/code/edit-distance/HungarianAlgorithm.java

谢谢。

Answer 1

如您所知，匈牙利（或 Kuhn–Munkres）算法是一种解决分配问题的组合优化算法。它由一组应用于方阵的操作组成，其单元格值是分配“任务”i 到“工人”j 或“工人”i 到“任务”j 的成本的函数。分别为 i 和 j 的行号和列号。在这里，我简要介绍了您正在使用的实现，以便您了解加星标和启动单元格（或零）的目的。

步骤 0：创建一个称为成本矩阵的矩阵，其中每个元素代表将一名工人分配给一项工作的成本。转到步骤 1

第 1 步（reduceMatrix）：对于每一行，找到最小的元素并将其从其行中的每个元素中减去。转到步骤 2。

第 2 步（initStars）：在结果矩阵中找到一个零 (Z)。如果在其行或列中没有星号零，则星号 Z。对矩阵中的每个元素重复。转到步骤 3。

第 3 步（coverColumnsOfStarredZeroes）：覆盖包含星号零的每一列。如果 K 列被覆盖，加星号的零描述了一组完整的唯一分配。在这种情况下，转到DONE，否则，转到Step 4。

第 4 步（primeSomeUncoveredZero）：找到一个未覆盖的零并对其进行初始化。如果在包含此前置零的行中没有星号零，则转到步骤 5。否则，覆盖这一行并发现包含星号零的列。以这种方式继续，直到没有未覆盖的零。保存最小的未覆盖值并转到步骤 6。

第 5 步（incrementSetOfStarredZeroes）：构造一系列交替的带底数和星号的零点，如下所示。让 Z0 表示在第 4 步中找到的未覆盖的底数零。让 Z1 表示 Z0 列中的星号零（如果有的话）。让 Z2 表示 Z1 行中的零（总是有一个）。继续，直到系列在其列中没有星号的零处终止。取消系列中每个已加星标的零的星号，为系列中的每个带素数的零加星号，擦除所有素数并发现矩阵中的每一行。返回步骤 3。

第 6 步（makeMoreZeroes）：将第 4 步中找到的值添加到每个覆盖行的每个元素，并从每个未覆盖列的每个元素中减去它。返回第 4 步，不更改任何星号、素数或覆盖线。

DONE：分配对由成本矩阵中星号零的位置指示。如果 C(i,j) 是星号零，则与行 i 关联的元素分配给与列 j 关联的元素。

希望这可以帮助。