logo标签列表

匈牙利算法 - 任意选择

graph-algorithmhungarian-algorithm
4
我看了几篇关于匈牙利算法解决分配问题的解释，其中绝大多数只涵盖了非常简单的情况。
我找到的最易懂的解释是一个YouTube视频。
我能编写算法，但我担心有一个特殊情况。如果你观看视频，相关情况从31:55到37:42进行了解释，但我会在下面解释一下。
首先，我要提到我将处理一个300 x 300矩阵，因此无法进行视觉检查。此外，我需要找到所有最小分配。换句话说，如果有多个分配产生相同的最小值，我需要找到它们所有。
这是我担心的特定情况。你可以在YouTube视频中看到这个解释，但我会在这里解释一下。我们从这个矩阵开始：
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

(Let me mention that I can visually see there are 4 solutions to this matrix and the total score is 13.)
给定上述简化矩阵，任何行或列中都没有唯一的零元素，因此根据视频中描述的算法，我可以任意选择任何一个零元素进行分配，所以我选择(1,1)。
我将已分配的零用星号标记，并在不再考虑的行和列中的零旁边放置“x”。现在我们有这个：
0*  0x  0x  0x
0x  0   0   0
0x  0   1   2
0x  0   3   4

接下来，我们继续检查具有唯一零点的行。我们在(3,2)处找到了一个，因此我们用星号标记它，并用"x"标记不可用的零点。
0*  0x  0x  0x
0x  0x  0   0
0x  0*  1   2 
0x  0x  3   4

接下来，我们开始在列中寻找独特的零（因为所有行都已经遍历完）。我们发现第三列在(2,3)处有一个独特的零，因此我们标记它：
0*  0x  0x  0x
0x  0x  0*  0x
0x  0*  1   2
0x  0x  3   4

此时，没有更多可用的零，并且第4行未被分配。（此YouTube视频现在使用“打勾过程”，这是一种确定覆盖所有零所需的最小行数的常见技术。如果您不熟悉此技术，请参见14:10到16:00的解释，尽管演示者使用的矩阵与此处显示的不同）。“打勾过程”如下：
  1. 打勾所有没有分配零的行（第4行）。
  2. 对于每个被打勾的行，在该行中包含零的列也打勾。
  3. 对于步骤2中打勾的每个列，打勾具有已分配零的相应行。
  4. 重复步骤2和3，直到无法再打勾为止。
  5. 通过所有打勾的列和未打勾的行画线。
此时，打勾过程生成4条垂直线，覆盖所有的0。这4条垂直线告诉我们矩阵中的0表示一个或多个解，然而，正如我们所看到的，第4行未被分配。第四行仍然未被分配，尽管有4条垂直线，这表明我们选择了错误的零进行分配！视频的主持人指出，这个问题是由于我们最初（任意）分配元素（1,1）引起的。主持人说，“有更复杂的方法可用”来使我们摆脱这种情况，但他没有解释这些技术是什么。他提到存在“智能”的方法来选择零，而不是我们用来选择（1,1）处的零的任意选择。
我可以采取的一种方法（我不确定是否最好），当面临任意分配时，是从可用任意选择最少的行或列中进行分配。在这个例子中，这意味着我会从只有两个任意选择的第3行或第4行进行任意分配，而不是从有四个任意选择的第1行或第2行进行分配。当然，由于我需要所有正确的解决方案，每当进行任意分配时，都必须遍历所有可用的任意分配。例如，如果我选择(3,1)作为任意分配，我还必须稍后分配(3,2)。
我的问题是，在面临任意选择零进行分配的选择时，最好的方法是什么？是我在前面提到的方法吗？如何消除像所示的死胡同解决方案？请记住，我仍然需要枚举所有具有相同最小分数的解决方案。
我认为第二个矩阵中存在错误。假设第一个矩阵是正确的，那么在(3, 3)处我也会得到0而不是1。 - trincot
@trincot - 对不起，已经更正了。原始矩阵在(3,3)处应该有一个4。 - Tom Baxter
2个回答
3
一旦您完成了所有行和列的减法步骤，就像您所做的那样，算法中有这一步骤要求您找到可以划掉的最少的行或列，以找出剩下的单元格中没有零的单元格（请参见维基百科文章中的第三步）。 如果这些划掉的行/列的最小数量等于n，则您已经到达了一个矩阵，在该矩阵中，分配可以在位置上进行，这些位置全部由零表示。
这是您的第二个矩阵的情况。
然后，一旦您完成了所有可能的减法步骤，还有这个算法步骤：如果一行或一列只有一个零，则该零表示一个（最优）分配。
我认为此规则可以概括如下：
如果i行（或列）中每行最多有i个零，则其中i个零代表（最优）分配。
当i等于n时，该规则显而易见（但毫无帮助）。
但是对于较小的i，这可能很有帮助，尽管查找这些行的算法可能会耗费时间。在示例问题中，我们发现对于i = 2，规则适用于第3和第4行。该规则还意味着我们可以禁止包含零的列中的任何其他分配。这意味着我们可以将矩阵写为：
-   -   0   0
-   -   0   0
0   0   1   2
0   0   3   4

现在规则可以再次应用于第1行和第2行，它们现在也只有2个零。
我们看到两个仅由零组成的子矩阵（应用规则的主题）：
0   0
0   0

有两种方法可以进行赋值操作：

x   0
0   x

或者：

0   x
x   0

一般而言，对于一个有i行和i列的子矩阵，如果它的所有元素都是0，则有i!种解决方案，但如果其中一些元素不为0，则可能会更少。
以具体的例子来说，左下角子矩阵有2!种解决方案，右上角矩阵也有2!种解决方案，因此共有4种可能的解决方案。
结论：
虽然以上考虑听起来很有趣，但我认为搜索这种子矩阵的算法并不比按顺序选择赋值的算法更有效，而且只要发现正在进行错误的轨迹，就应该立即回溯。由于需要找到所有的解决方案，所以从某一行开始没有意义。回溯应确保算法不浪费时间在没有未来的选择上。
维基百科的一篇文章说，直线绘制需要赋值，即“标记所有没有赋值的行”-但如何有效地进行最优赋值呢？ - Gurwinder Singh
在分配过程中，您可以针对每一行更新一个作业计数器。 - trincot
但是赋值过程是什么？那里没有真正解释。我特别遇到了选择多个零的问题。 - Gurwinder Singh
这个评论区并不适合这样的问题。如果您有新的问题，请使用“提问”按钮，并清楚地描述您的问题。 - trincot
我的问题与这个相同。你的答案没有回答这个问题。 - Gurwinder Singh
这里的问题是：“当我面临任意选择赋值的零时，最好的方法是什么？”我的答案回答了这个问题。我的回答非常简短：算法“按顺序选择分配，并在发现错误轨道时立即回溯”。换句话说，没有贪心算法可以保证给出最优解。 - trincot
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接