幸せな配属問題 その３

今回で３回目となる幸せな配属問題であるが、最近さらなる最適化の余地を見出した。それは、処理をする人の順番である。この工夫をするのとしないのとで実行時間が大きく変わってくる。

どういう順番で人を処理すると速くなりそうだろうか？これは、DPのステップと関係がある。DPによって、すでに現れたことのある状態については、スコアの高い方だけを残し、あとは捨てるようにしている。今、ノードA, Bがある深さdで同じ状態になるとしよう。まずAが最初に現れたとすると、これはまだ未登録なのでスコアをDP用のテーブルに記録し、ノードをリストに入れる。次にBが現れたとする。ここでもしBのスコアの方が高かったら、DPテーブルは更新され、Bの情報がリストに入れられる。しかし、もしBのスコアの方が低かったら、何もせずに次の処理に移る。

以上のような動作をしていることを考えると、できるだけ最初の方に、スコアが高くなりそうなノードを処理しておくとよさそうだ。つまり、同じ状態の中でスコアが高くなりそうな人を先に処理した方がよいことになる。そうすれば、後で現れる同じ状態のノードについては、ほぼすべてスルーすることができる。これはどうしたら実現できるだろう？

今、木を展開するときは、対象となる人が部署0, 1, 2, ..., M-1を志望した場合の状態を順にノードとして表現し、幅優先探索を行なっている。つまり、番号が小さい部署を志望している人を先に処理することで、よりスコアの高いノードが先に処理されるようになるのである。

というわけで、私のアルゴリズムでは、まず各人の志望度ベクトルを辞書順に並べて、それが小さい人から順に選んでいる。これにより、あらゆる入力データに対して、いつでもそこそこ速く動作できるようになるのである。

絵に描かないと分からない気もするが、ちょいと面倒くさいのでここでは勘弁させていただく。そんなに難しいことは言っていないはずだ。

以上で幸せな配属問題はおしまいだ。ソースは一応githubに上げてあるので、興味がある人は見てみて欲しい。（豆腐メンタルなのでソースのダメ出しはご遠慮願います。）

peng225/happy_arrange · GitHub

肝心の評価だが、まだ全然やっていない。なぜなら、入力ファイルを作るのがとっても面倒なのだ。これはひょっとしたらそのまま頓挫するパターンか・・・

ここまで３回続けて「俺が考えた最強のアルゴリズム」の話を書いた。実は私は高校の頃から、今回のように日常のふとした疑問を問題として定義し、それを解くのが趣味である。今後もまた何か思いついたら今回のように突発的に書いてみようと思う。

D言語をしばらくお休みすることにしたせいで、書くべき記事の内容が当初の予定と変わってしまったが、これからは何か思いついたときにそれを形に残しておく場所としてこのブログを活用しよう。