解决不了匈牙利算法 [英] Cannot solve Hungarian Algorithm
问题描述
我想实现一个功能，解决了匈牙利算法并我觉得有一些东西我误解了有关的算法。
I'm trying to implementing a function to solve the hungarian algorithm and i think that there is something i have misunderstood about the algorithm.
为了测试我使用的这个C ++ code 从谷歌是这样运作的。
For testing purposes i'm using this c++ code from google that is supposed to work.
但是，当我测试这个14x11矩阵，它说的这是不可能解决
But when i test this 14x11 matrix, it says that it is not possible to solve:
[0 0 0 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0 0 0 0 ]
[53 207 256 207 231 348 348 348 231 244 244]
[ 53 207 256 207 231 348 348 348 231 244 244 ]
[240 33 67 33 56 133 133 133 56 33 33]
[ 240 33 67 33 56 133 133 133 56 33 33 ]
[460 107 200 107 122 324 324 324 122 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 340 396 340 422 567 567 567 422 442 442 ]
[167 367 307 367 433 336 336 336 433 158 158]
[ 167 367 307 367 433 336 336 336 433 158 158 ]
[160 20 37 20 31 70 70 70 31 22 22]
[ 160 20 37 20 31 70 70 70 31 22 22 ]
[200 307 393 307 222 364 364 364 222 286 286]
[ 200 307 393 307 222 364 364 364 222 286 286 ]
33 153 152 153 228 252 252 252 228 78 78]
[ 33 153 152 153 228 252 252 252 228 78 78 ]
[93 140 185 140 58 118 118 118 58 44 44]
[ 93 140 185 140 58 118 118 118 58 44 44 ]
[0 7月22日7月19日58 58 58 19 0 0]
[ 0 7 22 7 19 58 58 58 19 0 0 ]
67 153 241 153 128 297 297 297 128 39 39]
[ 67 153 241 153 128 297 297 297 128 39 39 ]
[73 253 389 253 253 539 539 539 253 36 36]
[ 73 253 389 253 253 539 539 539 253 36 36 ]
[173 267 270 267 322 352 352 352 322 231 231]
[ 173 267 270 267 322 352 352 352 322 231 231 ]
C ++ $ C $下创建数组：（如果有人想通过使用C ++的例子我提供的测试吧）
C++ code for creating the array: (in case someone wants to test it by using the C++ example i provided)
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};
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};
如果我跑我的实现，以减少零的个数（这样他们就可以得到覆盖lines-第9步的最小数量在顶部提供wikihow的链接 - ）我得到以下矩阵，其中我必须要找到0组合独特的行和列。
If I run my implementation to reduce the number of zeros (so they can get covered by the minimum number of lines- step 9 in wikihow's link provided at the top -) I get the following matrix where i have to find the 0 combination unique for row and column.
<强>的问题是，它是不可能解决的自的列10和11（那些粗体）只能有一个0的每一个，这是在同一行中。
The problem is that it is impossible to solve since the columns 10 and 11 (the ones bold) only have one 0 each one and it is in the same row.
行1：240 140 225 140 206 339 339 339 206 215 215 0 0 0]
Row 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]
Row 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]
Row 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]
Row 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 227 227 227]
Row 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]
Row 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]
Row 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]
Row 8 : [ 207 0 0 0 151 143 143 143 151 96 96 167 167 167 ]
行9：[229 95 9 9 0 110 110 110 0 159 159 22 22 22]
Row 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]
Row 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]
Row 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]
Row 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]
Row 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]
Row 14 : [ 194 0 82 0 11 115 115 115 11 112 112 127 127 127 ]
有没有使用这种方法的任何一种限制？或只是我，做了个错误的实现算法？在这种情况下，为什么是这样运作的例子不工作要么？
Is there any kind of limitation with this method? Or is just me, making a bad implementation of the algorithm? In this case, why "is the supposed to work" example not working either?
任何建议将AP preciate，或者如果你知道任何窍门或建议，以帮助找到的最小行数来覆盖零，请让我知道。
Any suggestion would be appreciate, or if you know any trick or suggestion to help finding the minimum number of lines to cover zeros, please let me know.
在此先感谢，
推荐答案
有没有使用这种方法的任何一种限制？
是。如果你已经在每一步的转让的最大数量线描法只能正常工作。 我并不特别觉得这个工作由专人来证明这一点，但我假设你正在使用code没有完成，这个特殊矩阵。我决定去解决问题（又名拖延）是最好的，我可以从缺少文档的身影，它实际上并不有一个问题，涵盖所有与零线的最小数量。这只是坏的决策任务。
Is there any kind of limitation with this method?
Yes. That line drawing method will only properly work if you have made the maximum number of assignments at each step. I don't particularly feel like working this out by hand to prove it, but I assume that the code you are using does not accomplish that for this particular matrix. I decided to work it out (aka procrastinate) as best as I can figure from the lack of documentation, and it doesn't actually have a problem with covering all zeroes with the minimum number of lines. It's just bad at making assignments.
匈牙利算法的每一个实现我在网上发现将无法正常工作。不幸的是，他们都可以互相拷贝，而无需实际学习它背后的数学运算，因此他们都搞错了。我已经实现类似于Munkres描述了在他的文章算法的分配和运输问题，发表于1957年。我的code的东西给出了结果：（0,1），（1,3），（2， 8），（3,2），（9,12），（10,11），（4,9），（8,7），（5,10），（6,6），（7,0）为828的最小成本。
Every implementation of the Hungarian Algorithm I have found online will not work. They unfortunately all copy each other without actually learning the math behind it, and thus they all get it wrong. I have implemented something similar to what Munkres describes in his article "Algorithms for the Assignment and Transportation Problems", published in 1957. My code gives the results: (0,1), (1,3), (2,8), (3,2), (9,12), (10,11), (4,9), (8,7), (5,10), (6,6), (7,0) for a minimum cost of 828.
您可以在这里查看我的code //www.mediafire。 COM /查看/ 1yss74lxb7kro2p / APS.h
You can view my code here: http://www.mediafire.com/view/1yss74lxb7kro2p/APS.h
PS：提供了C ++数组感谢。我并没有期待中键入它自己。
ps: Thanks for providing that C++ array. I wasn't looking forward to typing it myself.
PPS：这是你的矩阵，适当间隔：
pps: Here's your matrix, properly spaced:
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
这篇关于解决不了匈牙利算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
