質問: 各セルに数字の書かれたn行n列の表があって、この各セルの数字に下記のルールで丸をつけるとします。 * 1行あたり必ず1つのセルに丸をつけなければならない(0個でも2個以上でも駄目) * 1列あたり必ず1つのセルに丸をつけなければならない(0個でも2個以上でも駄目) ※ つまり全部でn個のセルに丸がつくことになります この時、この丸をつけた数字の合計が最大になるようにセルを選択する、効率の良い(全探索ではない)アルゴリズムを考えているのですが、あまり良い考えが浮かびません。 こうすればよいのではという考えや何か既存のアルゴリズムをご存知の方がいましたら、お知恵をお貸しいただけませんでしょうか。 --- たとえばn=2で表が下記のようになっている場合は、左上のセルと右下のセルを選択するのが解になります。(10+1 > 5+5) ``` 10 5 5 1 ``` また同じくn=2で表が下記のようになっている場合は、右上のセルと左下のセルを選択するのが解になります。(10+1 < 5+7) ``` 10 5 7 1 ```
回答: この問題はいわゆる割り当て問題です。たとえばハンガリアン法と呼ばれるアルゴリズムで解け、n 行 n 列の行列が与えられたときの時間計算量は O(n3) です。全探索だと O(n!) なので全探索よりは効率的です。ハンガリアン法の説明は長くなるのでここではいたしませんが、検索すれば豊富に文献が見つかるかと思います。 * 参考 + 割り当て問題(ハンガリアン法) -- Spaghetti Source + Hungarian algorithm -- 英語版 Wikipedia