问题标签 [hungarian-algorithm]

我正在 Python 3.4 中从头开始编写匈牙利算法，并且遇到了关于覆盖零的最佳行的问题。

我从其 Wikipedia 页面中获取了算法的定义，这是查找覆盖所有零的最小行的代码：

问题是，当我通过它运行下面的矩阵时，在初始分配零作为找到覆盖它们的最少行的第一步时，选择了 matrix[1][1] 处的零。这会导致函数稍后标记所有行，这意味着它们不会被排列，即使行矩阵 [1] 显然应该是。

这是似乎导致问题的部分：

我认为必须有一些我错过的条件会阻止分配零，但这在我查看的描述和其他地方没有详细说明。有谁知道我做错了什么？

我有一个矩阵大小（N，N），我需要在它上面运行线性求和分配算法。

我正在使用 scipy 版本的实现，它的性能在大型矩阵中显着下降。

例如，对于 N=2000，它最终会挂起很长时间。

这是一个调用算法的简单片段：

是否有更快的算法实现？此类问题的典型补救措施是什么？

谢谢你。

所以这对我来说似乎很奇怪。我首先使用匈牙利算法（munkres python 包）解决了 174x174 矩阵上的分配问题，然后使用 Google OR tools min-cost flow solver解决了它。我对它所花费的时间进行了基准测试，而 Munkres 的运行速度非常慢（几乎慢了 12 倍！）：

芒克雷斯：48.2650001049s

谷歌或：4.4240000248s

由于这些是优化算法，因此结果选择是相同的，但为什么 GoogleOR 这么快？谁能解释一下？

编辑：我发现这更令人惊讶的原因是 Munkres 算法是专门为解决分配问题而设计的，而 min-cost-flow 是一种更通用的算法。

谢谢。

我有两套S_1和S_2。鉴于这两组，我需要将每个元素 fromS_1与一个元素 from配对S_2。

• 元素不可重复使用，所以如果S_1[A]与 配对S_2[D]，那么我也不能S_1[B]与配对S_2[D]。
• 目标是使用所有元素生成配对，以使配对的距离最小化。
• 配对的距离被计算为每对之间的距离之和。
• 产生具有最低总配对点值的结果

是否有任何已知的算法可以有效地解决此类问题？

部分困难在于采取贪婪的方法是行不通的。如果S_1 = [A, B, C]and S_2 = [D, E, F], and distance(A, D) = 0.1, distance(A, E) = 0.3, distance(A, F) = 0.4, 你不能仅仅因为它在这个集合中的距离最小就天真地匹配A到。D假设distance(B, D) = 0.1,distance(B, E) = 0.8和distance(B, F) = 0.9。如果您在第一次迭代中天真地选择匹配(A, D)，那么您实际上会使总距离更高，因为这会迫使您匹配(B, E)或(B, D)。(A, E)匹配然后允许匹配将是一个更好的选择(B, D)。这意味着您不能S_1根据 的每个元素S_1与S_2.

这似乎类似于分配问题，我可以使用匈牙利算法（https://en.wikipedia.org/wiki/Hungarian_algorithm）之类的方法来解决，但我相信该算法允许重用元素，这对我来说不起作用案子。

我有 2D 点，我想计算每对连续时间实例之间的成本。所以很简单norm(point 1¹ - point 2¹) + norm(point 1² - point 2²) + norm(point 1³ - point 2³)。请参阅以下信息。在 C++ 中，我会使用双 for 循环，它不会对计算造成太大影响，但是在 Python 中......那么，有没有办法用库或只用 Python 来做到这一点？

所以在时间 t：

在时间 t+1：

我这样做是为了创建一个成本矩阵并将应用匈牙利语。

我有一个集合，我需要在这个集合中生成两个元素对。作业都是加权的。匹配应该是受限的或完美的，取决于结果。我想，我需要在一般图表中进行加权匹配，据我所知，Edmonds 的算法是正确的地址。那正确吗？

我已经实现了 Kuhn-Munkres 算法，但我很晚才意识到这仅适用于二分图。是否有一种（简单的）方法可以将 Kuhn-Munkres 算法调整为 Edmond 的？否则我会选择爱德蒙算法。

我正在尝试使用 t-sne 根据它们的视觉相似性来排列图像，类似于这个很酷的表情符号示例（来源）：

但是 t-sne 的输出只是一个“点云”，而我的目标是以规则的、接近正方形的、密集的网格来显示图像。所以我需要以某种方式将 t-sne 的输出转换为网格上的 (x,y) 位置。

到目前为止，我已经遵循了这篇很棒的博客文章中的建议：我将其表述为线性分配问题，以找到最佳嵌入到规则网格中。我对结果很满意，例如：

我的问题是“捕捉到网格”阶段结果是一个巨大的瓶颈，我需要我的方法来很好地扩展大量图像（10K）。为了解决线性分配问题，我使用了 Jonker-Volgenant 算法的 Java 实现，其时间复杂度为 O(n^3)。所以虽然 t-sne 是 nlogn 并且可以很好地扩展到 10K 图像，但对齐到规则网格的部分最多只能处理 2K 图像。

潜在的解决方案，在我看来：

1. 从总共 10K 中随机抽取 2K 图像
2. 将 10K 图像分成 5 个并创建 5 个地图。这是有问题的，因为有一个“鸡和蛋”的问题，我该如何做好划分？
3. 以准确性换取性能：大约在接近线性的时间内解决线性分配问题。我想试试这个，但我找不到任何现有的实现供我使用。
4. 以不同的、更有效的方式实施“对齐网格”部分。

我正在使用 Java，但 cpp 中的解决方案也很好。我猜我不是第一个尝试这个的人。有什么建议么？想法？

谢谢！

我一直在使用一些已经在 python 中实现的匈牙利/munkres 算法（munkres 包和 scipy linear_sum_assignment 是具体的）并且它们都运行良好（无论如何它们都基于相同的 C 实现），但是它们缺乏我特别需要的功能。

为了给出一些上下文，我正在跟踪从一个图像到另一个图像的点，所以成本矩阵是图像 1 中的点到图像 2 中的所有点之间的距离。

问题出现在一个非常特殊的情况下，即如果图像 1 中的一个点在第二个图像中丢失，但在图像 2 中也检测到一个新的不同点，那么图像 1 中的一个点总是与新的点匹配观点。这是匈牙利算法按预期工作，不要误会我的意思。但是我需要的是匈牙利算法返回一个“不匹配”的点，如果它想要匹配的点太远的话。在 matlab 中，文件交换中有一个名为 simpletracker.m 的示例，那里的 munkres 实现可以允许没有良好链接的情况。因此，即使您有两个图像，例如 5 个粒子，它也可能只链接这些粒子中的 2 个，因为您可以使用最大链接距离参数来决定是否应该进行分配。

举个简单的例子，如果我们有一个在 (1,1) 和 (10,1) 有两个点的 image1，并且为了争论，我们知道它们会在下一张图像中向右移动一个像素，所以我们希望它们在图像 2 中位于 (2,1) 和 (11,1) 处，如果在第二张图像中找到正确的粒子，匈牙利算法将很容易链接正确的粒子。但是，如果没有找到其中一个，就会出现问题，比如 (11,1) 处的点，而是在 (20,1) 处发现视频中出现的随机噪声点或新点。然后匈牙利算法将按预期链接点 (1,1) 和 (2,1)，但现在也将 (10,1) 链接到 (20,1)。

所以在matlab实现中你可以选择一个最大链接距离值，然后将成本矩阵条目设置为无穷大，如果只能分配一个粒子，那么没关系，算法只返回一个链接。在 munkres.py 包中，有一个叫做 DISALLOWED 的东西，但是一旦这阻止了对每个点的分配，算法就会失败。例如，差分矩阵将是 [[1, 9^2],[8^2, 10^2]]。如果我们将 70 设置为最大链接距离，则矩阵为 [[1, DISALLOWED],[64, DISALLOWED]] 这意味着唯一有效的分配是图像 1 (1,1) 中的点 1 到图像 2 中的点 1 (2 ,1)。然而，munkres 算法只会返回 UnsolvableMatrix: Matrix cannot besolved！因为它无法链接第二点。

很抱歉文字墙和可能的混乱。我要问的是，是否有人知道可以允许非赋值的 munkres 实现，它已经在 python 中实现了？或者，处理错误匹配点的最佳做法是什么？我在想我可以在分配完成后尝试过滤掉异常值，或者如果所有值都被禁用，或者在计算距离矩阵后可能从距离矩阵中删除列，但是我不确定这是否足够强大以涵盖所有可能案例。

经典的分配问题涉及将 N 个代理分配给 M 个工作，同时最小化每个工作所花费的时间。该问题在多项式时间内有一个解决方案，称为匈牙利算法，它以成本矩阵 C 作为输入并返回最佳分配列表。

就我而言，我遇到了同样的问题，但有一点不同。每个工作都需要分配给它的两个工作。选择代理的数量，使得 N 是偶数，以便使这成为可能。

我对分配问题相关的问题相当陌生，所以我不确定如何解决这个问题。

如何解决这个问题？

编辑：请注意，一个代理最多可以分配给一个任务，它不能分配给多个任务。可以假设 M(jobs) = 2N(agents)，否则会引入虚拟代理或任务。

问题场景：

• 任务数（n）大于工人数（m）。

• 我需要将多个任务分配给一个工人。

  这是成本矩阵

  • 我有 6 个任务和 3 个可用的工人。

  • C (i,j) = 1，对于指示的单元格，可以将工人分配给任务。

  • C (i,j) = 1000，对于表示不能将工人分配给任务的单元格。

成本矩阵

这里，worker1可以做任务（TASK-1，TASK-4）worker2可以做任务（TASK-2，TASK-5）worker3可以做任务（TASK-6）

为了创建方阵，我添加了虚拟 WORKERS：DWORKER1、DWORKER2 和 DWORKER3)，如下所示，并为单元格值分配了非常大的值 (1000000)。

我用了这个scipy包scipy.optimize.linear_sum_assignment。如下：

col_ind 的输出是array([5, 3, 4, 0, 1, 2])

输出表明（如果我没记错的话）：

我所期待的是，将 TASK（1、2 和 3）分配给真正的工人而不是假工人。通过这个实现有可能吗？或者我在这里遗漏了什么？