割当問題 Hungarian method / Julia

割当問題　Hungarian method

n 人の人に n 個の仕事を割り当てるとき，最も効率のよい（コストの低い）割当方法を探る。

Project Euler の Problemm 345 で使用する。

Julia では Hungarian パッケージが用意されている。

using Hungarian

普通に使用すると，コストが最小になる割当結果が得られるので，コストを最大にする割当は，行列全体をマイナスにして関数を適用する。得られるコストの絶対値を取ったものが最大コストである。

w = [ 24     1     8
      5     7    14
      6    13    20
     12    19    21
     18    25     2];

assignment, cost = hungarian(w)

   ([2, 1, 0, 0, 3], 8)

w[1,2], w[2,1], w[5, 3] を選ぶのが最適ということだ。

m1 = [  7 53 183 439 863
     497 383 563 79 973
     287  63 343 169 583
     627 343 773 959 943
     767 473 103 699 303
   ];

hungarian(-m1)

   ([5, 2, 3, 4, 1], -3315)

m2 = [7  53 183 439 863 497 383 563  79 973 287  63 343 169 583
   627 343 773 959 943 767 473 103 699 303 957 703 583 639 913
   447 283 463  29  23 487 463 993 119 883 327 493 423 159 743
   217 623   3 399 853 407 103 983  89 463 290 516 212 462 350
   960 376 682 962 300 780 486 502 912 800 250 346 172 812 350
   870 456 192 162 593 473 915  45 989 873 823 965 425 329 803
   973 965 905 919 133 673 665 235 509 613 673 815 165 992 326
   322 148 972 962 286 255 941 541 265 323 925 281 601  95 973
   445 721  11 525 473  65 511 164 138 672  18 428 154 448 848
   414 456 310 312 798 104 566 520 302 248 694 976 430 392 198
   184 829 373 181 631 101 969 613 840 740 778 458 284 760 390
   821 461 843 513  17 901 711 993 293 157 274  94 192 156 574
    34 124   4 878 450 476 712 914 838 669 875 299 823 329 699
   815 559 813 459 522 788 168 586 966 232 308 833 251 631 107
   813 883 451 509 615  77 281 613 459 205 380 274 302  35 805
   ];

@time hungarian(-m2)

     0.000031 seconds (39 allocations: 6.656 KiB)

   ([10, 11, 8, 5, 4, 1, 14, 3, 15, 12, 7, 6, 13, 9, 2], -13938)

13938 が最大コストである。