问题标签 [hungarian-algorithm]

我想知道覆盖匈牙利算法所有零点的最少行数。我已经关注了这个链接，但是那里的代码很贪心。

匈牙利算法：如何用最少的行覆盖 0 个元素？

例如，

本案失败。我应该得到输出 3。但是这个解决方案给出的输出是 4。

任何其他解决它的方法都会有很大帮助。

谢谢

我想检查这个应用程序匈牙利系统我已经在 NetBeans 中导入了这个项目，但它给了我错误

我尝试在同一站点上搜索该文件，但我无法找到它。

请帮忙。

为了在分配问题中找到最佳解决方案，使用匈牙利算法很容易。例如：

在此使用匈牙利算法时，您将成为：

这意味着 A 被分配给“工作”2，B 被分配给工作 3，C 被分配给工作 1。但是，我想找到第二好的解决方案，这意味着我想要成本严格高于最优解决方案成本的最佳解决方案. 根据我的说法，我只需要在最后一个矩阵中找到具有最小和的分配，而不是与最优相同。我可以通过在树中搜索（修剪）来做到这一点，但我担心复杂性（O（n！））。有什么我不知道的有效方法吗？

我正在考虑一种搜索，首先对行进行排序，然后贪婪地首先选择最低成本，假设大多数最低成本将弥补最小总和 + 修剪。但是假设匈牙利算法可以产生一个有很多零的矩阵，那么复杂性又是可怕的......

我得到了一份人员名单和对这种组合有多好的评价。我需要最大化评分。我已经看过匈牙利算法，但它解决了一个稍微不同的问题。你怎么能解决这样的问题？

我正在寻找匈牙利算法的变体（我认为），它将N人与自己配对，不包括自我配对和反向配对，其中N是偶数。

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

在此示例中，生成的对将是：

N ₀ , N ₃
N ₁ , N ₄
N ₂ , N ₅

输入此内容后，我现在想知道是否可以仅增加矩阵“下半部分”中的成本值……甚至更好，将其删除。

是否有适用于非方阵的匈牙利语变体？

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

我正在为 Android 构建多人脸跟踪器，我正在使用卡尔曼滤波器，它显然需要一些算法来区分被跟踪的对象，目前我对匈牙利算法感兴趣。

我确实不明白该算法是如何工作的，但如果我有带坐标的二维空间，我无法弄清楚如何构建输入矩阵。因此，假设我在框架中检测到 3 个人：

在下一帧中，在新坐标上仍然检测到 3 个人，但现在我想知道上一张图片中哪个是Person1，哪个是Person2等。

现在我不太确定如何构建矩阵。列应该是这样的不同人：

这些值是当前位置和最后找到的位置之间的距离？我知道这可能看起来很愚蠢，但我很困惑。

谢谢您的帮助。

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

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

谢谢。

我正在尝试实施匈牙利算法，但我被困在第 5 步。基本上，给定一个n X n数字矩阵，我怎样才能找到最小数量的垂直+水平线，以便覆盖矩阵中的零？

在有人将此问题标记为与此问题重复之前，提到的解决方案是不正确的，并且其他人也遇到了那里发布的代码中的错误。

我不是在寻找代码，而是在寻找可以绘制这些线条的概念...

编辑：请不要发布简单（但错误）的贪心算法：鉴于此输入：

我显然选择了第 2 列（0 索引）：

现在我可以选择第 2 行或第 1 列，它们都有两个“剩余”零。如果我选择 col2，我最终会得到不正确的解决方案：

正确的解决方案是使用 4 行：

例如两个数组：

是否有一个函数可以将两个数组构造为映射，例如：

和其他 3 个... 总共给定两个数组，返回的地图编号应该是 A33 = 6。通过 javascript 或 python 任何都可以做到。有任何想法吗？

是否可以为有向图实现 Christofides 算法？

假设您有一个无向图，其中每个顶点在图中的每个顶点（而不是自身）都有一条边。但是边缘的权重不一定在两种方式上都相同（不对称）。

例如，您想到一张街道地图，其中有很多单向街道。

我们现在想要找到旅行商遍历所有顶点的近似值。

首先，Christoffides 算法没有为这样的 TSP 定义，因为最小生成树没有为有向图定义。

但是我们仍然通过使用 Edmonds 算法找到以游览起点为根的最佳分支来开始算法。

然后我们找到分支的最小完美匹配，使其成为欧拉图。这将在匈牙利算法中发生，该算法找到一个最小匹配，以便分支中的每个顶点都有相同数量的边进出。

在最后一步中，我们找到欧拉环并通过走捷径来优化环。

我不得不提问：

1. 我想实现算法的方式是正确的，还是我犯了一个错误，它不能工作
2. 如果可行，它是否仍然是 tsp 最佳解决方案的 1.5 倍？