hungarian-algorithm - 匈牙利算法 - 二分图方法

Question

我在理解这里概述的匈牙利算法时遇到了一些困难。这对我来说似乎不完整和/或错误。主要问题是行：

如果 R_T ^ Z 不为空，则反转有向路径的方向...

我们如何知道选择哪条路径作为“路径”？如果我们选择了错误的路径，我们如何恢复？这似乎是一种单调分配算法，因为我们只能创建新的分配，而不能删除或更改现有的分配。

假设我们有一个简单的例子 S = {A, B}, T = {W, X} 权重为 AW: 2, AX: 2, BW: 6, BX: 4。我们如何选择添加 AW 或 AX首先到映射，或者我们如何从错误的选择中恢复？

标签： hungarian-algorithm

Answer 1

我更熟悉矩阵解释，但看起来确实有点缺失。

我们如何知道选择哪条路径作为“路径”？

随便选一个；哪个都没有关系（只要它在R _T中）。在这一点上，它们都应该是等价的。

如果我们选择了错误的路径，我们如何恢复？这似乎是一种单调分配算法，因为我们只能创建新的分配，而不能删除或更改现有的分配。

这是缺少的部分，由于我对图形方法不太熟悉，我无法确切告诉您如何操作，但允许更改现有分配。缺少的选项是您可以将现有分配交换到相同成本的未分配边，然后允许您进行新分配。更难的部分是找到要交换的边缘，使其不会与任何其他分配冲突，并且通过进行这种交换，您可以进行新的分配。