问题标签 [hungarian-algorithm]

我有一组主机和一组任务。
每个主机都有 cpu、mem 和 task 容量，每个 task 都有 cpu、mem 要求。
每个主机都属于一个延迟等级，并且可以与具有一定延迟值的其他主机进行通信。
每个任务可能需要以等于或小于某个值的延迟与另一个任务通信。
我的问题输入示例如下图所示。 其中任务 t1 需要分别以等于或小于 3、3 和 5 的延迟与任务 t2、t3 和 t4 通信，并且主机 h1 属于延迟等级 3，并以 2、5 和 2 的延迟与 h2、h3 和 h4 通信3分别。
我正在考虑使用 Hungarian/munkres 算法来解决这个问题，但是如何正确设置成本函数？有没有更好的分配算法来解决这个问题？
谢谢。

我正在尝试实现一个函数来解决匈牙利算法，我认为我对该算法有误解。

出于测试目的，我正在使用来自谷歌的这个 c++代码，它应该可以工作。

但是当我测试这个 14x11 矩阵时，它说不可能解决：

[ 0 0 0 0 0 0 0 0 0 0 0 ]

[ 53 207 256 207 231 348 348 348 231 244 244 ]

[ 240 33 67 33 56 133 133 133 56 33 33 ]

[ 460 107 200 107 122 324 324 324 122 33 33 ]

[ 167 340 396 340 422 567 567 567 422 442 442 ]

[ 167 367 307 367 433 336 336 336 433 158 158 ]

[ 160 20 37 20 31 70 70 70 31 22 22 ]

[ 200 307 393 307 222 364 364 364 222 286 286 ]

[ 33 153 152 153 228 252 252 252 228 78 78 ]

[ 93 140 185 140 58 118 118 118 58 44 44 ]

[ 0 7 22 7 19 58 58 58 19 0 0 ]

[ 67 153 241 153 128 297 297 297 128 39 39 ]

[ 73 253 389 253 253 539 539 539 253 36 36 ]

[ 173 267 270 267 322 352 352 352 322 231 231 ]

用于创建数组的 C++ 代码：（如果有人想使用我提供的 C++ 示例对其进行测试）

int r[14*11] ={0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 53, 207, 256, 207, 231, 348, 348, 348, 231, 244 , 244, 240, 33, 67, 33, 56, 133, 133, 133, 56, 33, 33, 460, 107, 200, 107, 122, 324, 324, 324, 122, 33, 33, 167, 340 , 396, 340, 422, 567, 567, 567, 422, 442, 442, 167, 367, 307, 367, 433, 336, 336, 336, 433, 158, 158, 160, 20, 37, 20, 31 , 70, 70, 70, 31, 22, 22, 200, 307, 393, 307, 222, 364, 364, 364, 222, 286, 286, 33, 153, 152, 153, 228, 252, 252, 252 , 228, 78, 78, 93, 140, 185, 140, 58, 118, 118, 118, 58, 44, 44, 0, 7, 22, 7, 19, 58, 58, 58, 19, 0, 0 , 67, 153, 241, 153, 128, 297, 297, 297, 128, 39, 39, 73, 253, 389, 253, 253, 539, 539, 539, 253, 36, 36, 173, 267, 270 , 267, 322, 352, 352, 352, 322, 231,231};

如果我运行我的实现以减少零的数量（这样它们就可以被最少的行数所覆盖——顶部提供的wikihow链接中的第9步——）我得到以下矩阵，我必须在其中找到唯一的 0 组合行和列。

问题是无法解决，因为第 10 列和第 11 列（粗体）各只有一个 0，并且位于同一行。

第 1 行：[ 240 140 225 140 206 339 339 339 206 215 215 0 0 0 ]

第 2 行：[254 0 37 0 43 58 58 58 43 38 38 67 67 67]

第 3 行：[0 107 158 107 151 206 206 206 151 182 182 0 0 0]

第 4 行：[0 253 245 253 304 235 235 235 304 402 402 220 220 220]

第 5 行：[300 27 56 27 11 0 0 0 11 0 0 227 227 227]

第 6 行：[300 0 145 0 0 230 230 230 0 284 284 227 227 227]

第 7 行：[80 120 188 120 176 269 269 269 176 193 193 0 0 0]

第 8 行：[207 0 0 0 151 143 143 143 151 96 96 167 167 167]

第 9 行：[229 9 95 9 0 110 110 110 0 159 159 22 22 22]

第 10 行：[147 0 40 0 148 221 221 221 148 171 171 0 0 0]

第 11 行：[240 133 203 133 187 282 282 282 187 215 215 0 0 0]

第 12 行：[189 3 0 3 94 58 58 58 94 192 192 16 16 16]

第 13 行：[367 87 36 87 153 0 0 0 153 379 379 200 200 200]

第 14 行：[194 0 82 0 11 115 115 115 11 112 112 127 127 127]

这种方法有什么限制吗？或者只是我，对算法的实现不好？在这种情况下，为什么“应该工作”的例子也不起作用？

任何建议将不胜感激，或者如果您知道任何技巧或建议来帮助找到覆盖零的最小行数，请告诉我。

提前致谢，

我正在尝试使用匈牙利算法的以下实现：http: //community.topcoder.com/tc ?module=Static&d1=tutorials&d2=hungarianAlgorithm 。

我想修改这个算法，以便我可以将一组与自身配对。也就是说，如果“a”被分配给“b”，那么“b”也被分配给“a”。我唯一的想法是更改以下内容。

到以下：

这样算法总是检查配对是相互的路径。但是，我很确定这是错误的 - 代码通常会出现段错误。

我尝试通过更改if (max_match == n)为更宽松的约束来解决问题，例如if (max_match >= n-1)，以便算法满足于次完美匹配。这有时会起作用，当它起作用时，它会像我想要的那样创建一些相互对，但有些顶点是不成对的。并且仍然存在分段错误。

那么，有没有办法解决这个问题呢？还有其他更合适的算法吗？

我正在尝试解决这个问题：乔布斯。到目前为止，我认为这个问题与分配问题相同，分销商和地区表示为二分图，边表示概率。但是在这里我们需要最大化产品而不是匹配边的权重之和。

我想到的一个想法是将每个边缘权重更改为对数（权重）。然后问题本质上变为寻找最大和，然后可以使用分配问题的算法来解决。但这带来了一个问题，因为应用 log 将使边缘权重非整数，我认为匈牙利算法不起作用。

请提出其他一些替代方法。

我有一个问题要解决，但没有看到任何最佳解决方案：/问题是：

我有 n 个工人和 k 个工作。每项工作都由指定数量的工人完成，每个工人对每项工作都有自己的幸福程度。我必须制定一个工作时间表，以便工人尽可能快乐。所以，我有 int[n,k] (k >= n) 的数组 a1。第 i 行的第 k 列包含第 i 个工人对第 k 个工作的偏好（数字从 0 到 10）。我还有 int[k] 的数组 a2，其中第 i 个元素包含将从事这项工作的人数。每个工人要做相同数量的工作。我必须找到最大可能的快乐总和，知道 n >= max(a2)。我的解决方案是使用递归。为第一个工作组合选择第一个工人，将偏好添加到总和中，检查总和是否高于已找到的最大值，如果是，则转到下一个工人。回来时，检查第一个工人等的下一个组合。这适用于少量工人，但必须有很高的计算复杂度才能解决更大的问题。您对更好的解决方案有任何想法吗？

PS。另一个站点的人推荐我使用匈牙利算法，但它假设 n == k，我不知道如何使它与 n <= k 一起使用

PS2 一个例子：

Hungarian/Kuhn-Munkres 算法的 PL/SQL 实现在哪里？网上好像没找到。

假设我们有 N 个工作和 K 个工人来做这些工作。但是对于某些工作，我们需要 2 名员工，而对于某些工作，我们只需要一名。员工也不能做所有的工作。例如，工人 1 可以从事工作 1,2 和 5，而不能从事工作 3 和 4。此外，如果我们雇用工人 1 从事工作 1，那么我们希望他从事工作 2 和 5，因为我们已经支付了他的工资。

例如，假设我们有 5 个工作和 6 个工人。对于工作 1,2 和 4，我们需要 2 个男人，而对于工作 3 和 5，我们只需要一个。这是每个工人可以做的工作清单和他需要的工资。

经过一点计算和逻辑思考，我们可以得出结论，我们要雇用工人 1、3、4 和 5，这意味着我们需要支付的最低工资是：1000+1500+2500+1500=5500 美元。

但是我们怎样才能找到一个有效的算法来输出这个数量呢？这不知何故让我想起了匈牙利算法，但所有这些额外的约束让我无法应用它。

在我的研究中，一个人被表示为一对实数 (x, y)。x 在 [30, 80] 上，y 在 [60, 120] 上。有两种类型的人，A 和 B。我每种类型都有大约 300 人。我怎样才能生成最大的（甚至是大的）一组来自 A 的人和一个来自 B 的人： ((xA, yA), (xB, yB)) 使得每对点都很接近？如果 abs(x1-x2) < dX 和 abs(y1 - y2) < dY，则两点接近。类似的约束是可以接受的。（也就是说，这个约束大致是曼哈顿度量，但欧几里得/等也可以。）并非所有点都需要使用，但没有点可以重复使用。

我的问题如下：

我天真地尝试使用匈牙利算法，希望它可以给我一个作业，让作业是对称的。但这显然不起作用，因为我没有二分图。

经过一番搜索，我发现了Stable roommates problem，这似乎和我的问题相似，但不同的是，它只是试图找到一个匹配，而不是试图最小化某种距离。

有谁知道类似的问题甚至解决方案？我错过了什么？这个问题实际上似乎并不难，但我就是想不出一个最佳解决方案。

当矩阵在任何行中包含零时，将引发上述错误。我该如何解决？

这是python中的一段代码：

我在 Ubuntu 中使用以下命令安装了库 munkres：

sudo apt-get install python-munkres