问题标签 [hungarian-algorithm]

如何使用匈牙利算法将连续两帧之间的对应目标关联起来，最终实现可以判断下一帧中的运动目标是已经存在的还是新的？我没有在实际执行程序时如何开始使用C++和Opencv3库？

现在我可以得到每帧卡尔曼滤波器检测到的运动目标的质心。

//这是主函数的一部分。

我已经得到了移动目标的质心点集合，那么如何结合匈牙利算法使用这些数据？

在我的计划中，将有学生（来自多年组/年级）为周一至周五的活动提交选择。

每项活动可能适用于一年或多年组。每个学生每天都有 4 个选择（第 1、第 2、第 3 和第 4）。这将作为 int[][] studentCosts 存储在每个学生对象中，这将是studentCosts=new int[5][4].

我已经完成了我的匈牙利算法，但我需要决定如何将所有学生的选择添加到 int[][]。

我将每天分别执行该算法，因此我需要将所有学生在那一天的选择整理到一个 int[][] costForThatDay 中。

我的问题是如何为某些年级组提供某些不提供给其他人的活动，例如，周一提供 7 年级的帆板运动，而周一提供 8 年级和 9 年级的高尔夫。

如果我要每天执行算法，最好将不可用活动的“成本”设置为Integer.MAX_VALUE确保绝对没有办法选择它？例如，让 7 年级学生的高尔夫“成本”和 8 年级和 9 年级学生的风帆冲浪“成本” Integer.MAX_VALUE

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

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

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

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

给定 100 个人，创建 6 人的小组，每个人都指定了他们最想加入的前 10 名其他人。

理想情况下，我想在 Python 中执行此操作。

我在网上四处寻找，遇到了我以前不知道的术语，现在我很迷茫。我知道这是一个 NP 完全问题或 NP 难题，尽管我不完全确定这意味着什么。这似乎也是一个组合优化问题，但同样——这些只是我在研究这个问题时几乎没有任何理解的术语。

我尝试使用 networkx 并创建了一个定向网络，但仅此而已。社区函数或团函数都不适用于有向图，仅适用于无向图。

我需要按距离将蓝色物体映射到红色物体。每个对象的中心是已知的。黄色和绿色对象（如果显示）是提示。它们有助于确定哪个红色物体更重要。

例如，在下图所示的情况下：

• 底部的蓝色对象应该映射到最右下方的红色对象，因为绿色和黄色对象都非常靠近那个红色对象。
• 右边的蓝色对象应该映射到右上角的红色对象，因为它更靠近它。

我有一个天真的解决方案，但我不太确定该怎么做而不是“？？？？” 以下

你有什么建议吗？

我在某种伪代码中的天真解决方案：

UPDATE1
在研究了@ldog 建议的最小成本流问题后，我决定使用Hungarian Algorithm。我创建了二分图，其中每个蓝色节点都连接到每个红色节点，边上的权重是蓝色和红色之间的距离。 现在，在我解决图表之前，我需要在黄色/绿色接近红色的边缘上应用奖励。我不太明白该怎么做。 假设蓝色 1 和红色 4 之间的距离是 D_1_4 = 10，黄色提示 11 和红色 4 之间的距离是 D_4_11 = 3。那么，因为 D_1_4 > D_4_11，我应该只在边 1_4 上添加奖励吗？或者，我应该将奖励添加到进入节点 4 的每条边，即边 1_4、2_4 和 3_4？

我需要找到一种方法来编写两个向量（数据实例）之间的相似函数，让我们将它们命名为. 这些数据实例具有分类特征和数量。因此，我想找到一种方法来结合，比如说汉明距离和欧几里得距离，以便在我的关联问题中使用它。

k-NN有合并类型，比如投票等，仍然不能通过投票方式解决关联问题。

我在正确重新排序由不同设备发送的一系列事件时遇到问题：它们是连续的，有时可能会发生除第一个之外的所有事件都可以完全或部分绕过。例如，假设有 3 个设备D1 D2和D3，必须按照 D1 -> D2 -> D3 的顺序通过所有设备。

第一个设备D1可以在每次有人通过它时给我一个时间戳。

每当有人在其区域内时，第二个设备D2可以给我一个或多个时间戳。

第三个设备D3可以给我一个时间戳，每次一个人通过它。（有时可能会在D2的某个时间戳之前发送D3）。 现在，如果只有一个人穿过所有设备，我可以看到如下内容：

D1：时间戳 20/01/2020 13:45:24.000

D2：时间戳 20/01/2020 13:45:25.700

D2：时间戳 20/01/2020 13:45:26.800

D3：时间戳 20/01/2020 13:45:27.010

在这种情况下，我可以轻松获得正确的过渡。假设现在我们有两个人，当第一个在中间时，第二个开始穿过设备：

人 1 - D1：时间戳 20/01/2020 13:45:24.000

人 1 - D2：时间戳 20/01/2020 13:45:25.700

人 2 - D1：时间戳 20/01/2020 13:45:25.900

人 2 - D2：时间戳 20/01/2020 13:45:26.500

人 1 - D2：时间戳 20/01/2020 13:45:26.800

人 1 - D3：时间戳 20/01/2020 13:45:27.000

人 2 - D2：时间戳 20/01/2020 13:45:27.400

人 2 - D3：时间戳 20/01/2020 13:45:28.000

有没有办法分别生成它们的完整过渡，如下所示？

人 1

D1：时间戳 20/01/2020 13:45:24.000

D2：时间戳 20/01/2020 13:45:25.700

D2：时间戳 20/01/2020 13:45:26.800

D3：时间戳 20/01/2020 13:45:27.000

人 2

D1：时间戳 20/01/2020 13:45:25.900

D2：时间戳 20/01/2020 13:45:26.500

D2：时间戳 20/01/2020 13:45:27.400

D3：时间戳 20/01/2020 13:45:28.000

（显然我的数据中没有第 1个人和第2 个人，问题必须推广到 n 个人和不同的过境点）。

我必须实现一个 C++ 代码，我可以在其中解决这个问题并生成一些充满完整转换（D1->D2->D3）的向量。我想了一些关于分配问题的事情，但我不知道我是否正确。任何想法？

我正在尝试用 Java 实现匈牙利算法。我能够为具有单一最佳解决方案的问题解决它。但是，当有多个最佳解决方案时，我不知道如何解决它（从程序上讲）。

以示例矩阵为例。

在执行行和列缩减之后。矩阵看起来像。

现在显然有多种解决方案，例如

和

如何编写一种能找到至少一种解决方案的方法？随意分配初始 0 往往会迫使你走入死胡同。例如，如果分配了位置 0,0 的 0，则会发生以下情况。

那么如何智能地选择最佳解决方案位置呢？

我正在尝试学习匈牙利算法的各种实现。具体来说，我想最大化并获得最高分。

我从各种包中找到了两种解决方案：（1）munkres 包，和（2）Scipy 中的线性总和分配

(1) http://software.clapper.org/munkres/ (2) https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.optimize.linear_sum_assignment.html

我能够与 #1 一起获得一些东西，但在我的实现中发现了问题（https://github.com/bmc/munkres/issues/39）。所以，我现在正在尝试使用选项#2。

这是我到目前为止所拥有的：

它返回 1510.21 的正确解。

帮助我将不胜感激：

我一直在努力展示作品。理想情况下，我想看到的是匹配的行列对和分数。在此示例中，它将是：

这对于 munkres 包（上面详述的#1）来说是直截了当的，但我很难弄清楚如何通过 scipy 实现来实现这一点。

谢谢你的帮助

请注意，员工 1 无法执行职责 3，而员工 3 无法执行职责 4。

任何想法如何找到 (-) 的值，或者如何使用匈牙利算法解决这个问题？