algorithm - 无法解决匈牙利算法

Question

我正在尝试实现一个函数来解决 hungarian algorithm我认为我对算法有一些误解。

出于测试目的，我正在使用此 C++ code来自谷歌，应该可以工作。

但是当我测试这个 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，而且它们在同一行中。

Row 1 : [ 240 140 225 140 206 339 339 339 206 215 215 0 0 0 ]

Row 2 : [ 254 0 37 0 43 58 58 58 43 38 38 67 67 67 ]

Row 3 : [ 0 107 158 107 151 206 206 206 151 182 182 0 0 0 ]

Row 4 : [ 0 253 245 253 304 235 235 235 304 402 402 220 220 220 ]

Row 5 : [ 300 27 56 27 11 0 0 0 11 0 0 227 227 227 ]

Row 6 : [ 300 0 145 0 0 230 230 230 0 284 284 227 227 227 ]

Row 7 : [ 80 120 188 120 176 269 269 269 176 193 193 0 0 0 ]

Row 8 : [ 207 0 0 0 151 143 143 143 151 96 96 167 167 167 ]

Row 9 : [ 229 9 95 9 0 110 110 110 0 159 159 22 22 22 ]

Row 10 : [ 147 0 40 0 148 221 221 221 148 171 171 0 0 0 ]

Row 11 : [ 240 133 203 133 187 282 282 282 187 215 215 0 0 0 ]

Row 12 : [ 189 3 0 3 94 58 58 58 94 192 192 16 16 16 ]

Row 13 : [ 367 87 36 87 153 0 0 0 153 379 379 200 200 200 ]

Row 14 : [ 194 0 82 0 11 115 115 115 11 112 112 127 127 127 ]

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

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

提前致谢

Answer 1

这种方法有什么限制吗？是的。只有在每一步都进行了最大数量的分配时，该画线方法才能正常工作。 我不是特别想亲自解决这个问题来证明这一点，但我假设您使用的代码不能为这个特定的矩阵实现这一点。我决定解决这个问题(又名拖延) 尽我所能，因为缺乏文档，它实际上没有用最少的行数覆盖所有零的问题。只是不擅长做作业。

我在网上找到的匈牙利算法的每一个实现都行不通。不幸的是，他们都在没有真正学习其背后的数学知识的情况下互相模仿，因此他们都弄错了。我实现了类似于 Munkres 在 1957 年发表的文章“分配和运输问题的算法”中描述的内容。我的代码给出了结果:(0,1), (1,3), (2,8), (3,2), (9,12), (10,11), (4,9), (8,7), (5,10), (6,6), (7,0) 至少成本828。

您可以在这里查看我的代码:http://www.mediafire.com/view/1yss74lxb7kro2p/APS.h

ps:感谢您提供该 C++ 数组。我并不期待自己打字。

pps:这是你的矩阵，适当间隔:

  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