ハンガリーのアルゴリズムを解決する関数を実装しようとしていますが、アルゴリズムについて誤解しているものがあると思います。
テスト目的で、動作するはずのGoogleのこのC++コードを使用しています。
しかし、この 14x11 行列をテストすると、解決できないと表示されます。
[ 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 (太字のもの) にはそれぞれ 1 つの 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 ]
この方法に何らかの制限はありますか? それとも、アルゴリズムの実装が悪いのは私だけですか? この場合、「動作するはずの」例も動作しないのはなぜですか?
任意の提案をいただければ幸いです。または、ゼロをカバーする最小行数を見つけるのに役立つトリックや提案を知っている場合は、お知らせください。
前もって感謝します、