匈牙利算法：将一个集合匹配到其自身

Question

匈牙利算法：将一个集合匹配到其自身

3

我正在寻找一种变体的匈牙利算法（我认为），它将N个人配对，排除自我配对和反向配对，其中N是偶数。

例如，给定N₀-N₆和每对之间成本的矩阵C，如何获得三个成本最低的配对集合？

C = [ [ - 5 6 1 9 4 ]
      [ 5 - 4 8 6 2 ]
      [ 6 4 - 3 7 6 ]
      [ 1 8 3 - 8 9 ]
      [ 9 6 7 8 - 5 ]
      [ 4 2 6 9 5 - ] ]

在这个例子中，得到的配对将是： N0, N3 N1, N4 N2, N5

在输入完这个问题后，我现在想知道是否可以增加矩阵“底部”的成本值……或者更好的方式是删除这些成本值。

有没有一种匈牙利算法适用于非方阵？

或者，是否有另一种算法可以解决这个问题的变化？

- Jon

1

你的问题是加权完美匹配问题（非二分图），该问题也有多项式时间解决方案。请查看Edmond's花托算法的原始对偶变体。 - Niklas B.

@NiklasB. 谢谢... 我正在努力将我的“矩阵”转换为图形... 如果您能在答案中详细说明您的评论，那就太好了。 - Jon

将矩阵解释为无向图的邻接矩阵。 - Niklas B.

2个回答

0

正如@Niklas B所说，您正在解决加权完美匹配问题，请查看this

这里是部分描述加权完美匹配的原始对偶算法的文档 enter image description here

请仔细阅读并告诉我是否对您有用

- edgarmtze

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Isaac · Accepted Answer

增加下半部分的值可能导致不正确的解决方案。您可以将此视为上半部分的角坐标（在您的示例坐标0,1和5,6中）始终被认为处于最小X对中，其中X是矩阵的大小。 我的解决方案寻找最小X对 采用标准的匈牙利算法您可以将对角线设置为大于未更改矩阵中元素总和的值 - 根据您的实现如何处理nulls，此步骤可能会使您加快实现速度。

1）标准算法的第一步是遍历每行，然后每列，逐个减少每行和每列，以使每行和每列的最小值为零。这没有改变。 这个解决方案的一般原则是围绕对角线镜像每个原始算法的后续步骤。

2) 算法的下一步是选择行和列，以便包含每个零在内，使用最少的行和列。我的算法修改意味着，在选择行/列时，还要选择围绕该对角线镜像的列/行，但将其视为一个行或列选择，包括计算对角线（这将是这些镜像行/列选择对的交集）只被选中一次。

3) 下一步是检查您是否拥有正确的解决方案 - 在标准算法中，这意味着检查选择的行数和列数是否等于矩阵的大小 - 在您的示例中，如果选择了六行和列，则为正确的解决方案。然而，在计算何时结束算法时，请将每个镜像选择的行/列对作为单个行或列选择处理。如果您有正确的解决方案，则在此处结束算法。

4) 如果行数和列数小于矩阵的大小，则找到最小的未选择元素，并将其称为k。从所有未覆盖的元素中减去k，并将其添加到涵盖两次的所有元素中（再次将镜像行/列选择计为单个选择）。我的算法修改意味着，在更改值时，您将以相同方式更改它们的镜像值（这应该自然发生，因为镜像选择过程的结果）。

然后回到第2步，重复第2-4步，直到第3步指示算法完成为止。这将产生成对的镜像答案（这些是坐标 - 要获取这些坐标的值，请参考原始矩阵） - 您可以安全地任意删除每个对的一半。要修改此算法以查找最小的R对（其中R小于矩阵的大小），请将第3步中的停止点减少到R。这种修改对于回答您的问题至关重要。