graph - Cannot solve Hungarian Algorithm -

graph - Cannot solve Hungarian Algorithm -

i'm trying implementing function solve hungarian algorithm , think there have misunderstood algorithm.

for testing purposes i'm using c++ code google supposed work.

but when test 14x11 matrix, says it not possible solve:

[ 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++ code creating array: (in case wants test using c++ illustration 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};

if run implementation cut down number of zeros (so can covered minimum number of lines- step 9 in wikihow's link provided @ top -) next matrix have find 0 combination unique row , column.

the problem is impossible solve since columns 10 , 11 (the ones bold) have 1 0 each 1 , in same row.

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 ]

is there kind of limitation method? or me, making bad implementation of algorithm? in case, why "is supposed work" illustration not working either?

any suggestion appreciate, or if know trick or suggestion help finding minimum number of lines cover zeros, please allow me know.

thanks in advance,

is there kind of limitation method? yes. line drawing method work if have made maximum number of assignments @ each step. i don't particularly sense working out hand prove it, assume code using not accomplish particular matrix. decided work out (aka procrastinate) best can figure lack of documentation, , doesn't have problem covering zeroes minimum number of lines. it's bad @ making assignments.

every implementation of hungarian algorithm have found online not work. unfortunately re-create each other without learning math behind it, , wrong. have implemented similar munkres describes in article "algorithms assignment , transportation problems", published in 1957. code gives results: (0,1), (1,3), (2,8), (3,2), (9,12), (10,11), (4,9), (8,7), (5,10), (6,6), (7,0) minimum cost of 828.

you can view code here: http://www.mediafire.com/view/1yss74lxb7kro2p/aps.h

ps: providing c++ array. wasn't looking forwards typing myself.

pps: here's matrix, 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

algorithm graph hungarian-algorithm