幸せな配属問題

　突然私事で恐縮なのだが、少し前に会社の配属が決まった。そんなわけで現在は配属先の部署で元気に働いているわけだが、私はこの配属で希望通りの部署に配属されなかった。これは大変残念なことだ。しかし周りを見渡すと、どうも私一人が不幸になったわけではなく、配属の仕方が最適でないように思えて仕方がなかった。どうすればみんなが幸せになる配属ができたのだろう？

　そこで、私は幸せな配属問題というものを考え、解いてみることにした。早速だが、幸せな配属問題を以下のように定義する。

• n人がM個の部署に対してそれぞれ第3希望までの希望を出す。
• 第k希望の部署に配属された場合、その人の幸福度はである。
• 希望の部署に配属されなかった場合、その人の幸福度は0である。
• 以上のような条件の下で、全員の幸福度の総和が最大になるような配属方法を見つける。

　これは組合せ最適化問題の一種である。普通にやるとO()の計算時間が必要となり、現実的な時間で解くことは出来ない。そこで、今回は動的計画法と、望みの薄いノードの枝刈りによって計算量を削減する。ここではこれら２つの工夫について説明する。

　説明の中でアルゴリズムに名前がないと分かりづらいので、以下ではこのアルゴリズムを暫定的にPDP(Pseudo Dynamic Programming)と呼ぶことにしよう。（なぜpseudoなのか、そしてなぜ暫定なのかは後述。）名前の中に枝刈りが出て来ないが、こっちはおまけというか、実行速度を上げるために無理やりやっているものなので、本質的に重要ではない。

　それでは、動的計画法の適用方法について説明する。アルゴリズムの基本的な方針は幅優先探索である。まず適当に一人を選び、その人がM個あるそれぞれの部署に配属になった場合を考える。次に、その各場合について、二人目がそれぞれの部署に配属になる場合を考える、といった具合である。

　これだと状態が多くなりすぎるので、こういう問題には定番の解法である動的計画法(以下、DP)の力を借りたい。DPの使い方はいろいろあるが、１つには同一状態にある複数の処理について、スコアがより高い方のみを残していくというやり方がある。最短経路を求める問題なんかがそうだ。ある点に至るまでの経路の中で、最も距離が短いものだけを採用し、その先の経路を考える。これと似たようなことができないだろうか？

　そのためには、まずこの問題でいうところの状態とは一体何を指すかを考えなければならない。ここでは、ある時点までに選択した部署の集合を状態と考えることにする。集合と言っても、部署Aが二回選ばれれば、Aを２つ含むような集合、すなわちmultisetだ。これが同じ処理については、スコアが一番大きいものだけ続行し、残りは終了させるようにすれば、状態数は一気に削減できる。

　しかしちょっと待って欲しい。上で定めた状態というのは、本当に正しい考え方なのだろうか？つまり、全然違う部署を志望している二人が部署A, Bに配属になった場合と、配属が逆になった場合を同一状態とすることは正しいのだろうか？これについては現状ではよく分かっていない。そして、大きな問題に対して真の解を求めることは実質不可能であるため、実験的に確かめようもない。しかし、今のところはgreedyにやるよりは良い結果が得られることが経験的に分かっている。

　この部分がもし正しくなかった場合、ここで決めた状態はあやふやなものになってしまう。しかし、それでも結果的にはそれなりの答えが得られているので、今のところはこれをPseudo DPと呼んているのである。

　以上のように、このアルゴリズムにはまだ不安なポイントが残っている。しかしそれでも、現実的な時間とメモリである程度良い解が得られていることは事実だ。引き続きさらなる研究を続けたい。

　少々長くなってしまったので、望みの薄いノードの枝刈りについてはまた次回書くことにする。ついでに実験結果なんかも載せられると嬉しいな。