幸せな配属問題 その２

前回に引き続き幸せな配属問題について書こうと思う。今日は枝刈りについてだ。これは特別頭のいいことをしているわけではないのでさくっと説明しよう。

このアルゴリズムは幅優先探索がベースであり、その各ノードはそこまでの幸福度の情報を持っている。そこで、同じ深さのノードに関して、ある程度幸福度の小さいノードは捨ててしまおうというのが基本的なアイディアである。

では、幸福度がいくつ以下だったら切り捨てることにしようか？これを考える指標として、同じ深さのノードの点数の平均と標準偏差を用いる。ただし、単に(平均)ー(標準偏差)を閾値とするのは芸がない。というのも、深さによって切り捨てを行う閾値は変わるはずだからだ。深さが小さいところはまだまだ序盤であり、多少悪くても後に幸福度がひっくり返る可能性がある。しかし、後半はそう簡単にノード間の幸福度が入れ替わることはないだろう。よって、比較的大胆に切り捨てても良いはずだ。

そこで、標準偏差の値を目安にしつつ、深さが進むごとに閾値をじわじわと上げていくような戦略が良さそうだ。これには無限にやり方があるが、今のところはとりあえずを閾値としている。ただし、μは幸福度の平均、σは幸福度の標準偏差、dは深さである。

さて、これでめでたしめでたしと言いたいところだが、１つ考えるべきことがある。今回は幅優先探索ベースなので、これを実現するためのコンテナとしてキューのようなものが使われるはずである。（実際には途中でノードを削除したいことがあるので、キューではなく線形リストを使用している。）上で考えたことをナイーブに実装すると、リストに入ったある深さのノードの幸福度から閾値を計算し、リストを舐めてそれに満たないノードを削除するということになるだろう。しかし、これだとどうせ消されるノードが一旦リストに入るため、時間もメモリも無駄である。

よって、リストにpushする段階で閾値以上のものだけを選別するようにしたい。しかし、これはちょっとおかしなことを言っていることになる。なぜなら、ノードを一度すべてリストにつっこまないと、そこから標準偏差を求めることはできないので、そもそもリストにpushする段階で閾値が分かるはずがないからだ。

これを解決するために、閾値を前のイテレーションでの平均、標準偏差から予測する。例を用いて説明しよう。今、部署の数が5個であり、第一、第二、第三希望に通った場合の幸福度をそれぞれ5, 3, 2点とする。すると、一人の配属割り振りを行ったときに、幸福度の平均はであることが分かる。部署の数が5個であるため、希望が通らない場合が二通りあることに注意して欲しい。標準偏差はとなる。

深さdでのデータの分布は実データがリスト内にあり、平均も標準偏差も分かっているとする。これらをそれぞれ, とする。ここで、統計学のテクニックを駆使すると、深さd+1での平均、標準偏差の予測値はそれぞれ, となる。これらの値を元に、深さd+1での枝刈りを行うのである。

以上で枝刈りの話はおしまいだ。統計なんかを持ちだしてあれこれやったが、これは私のちょっとした自己満足であり、そこまで大きな意味はない。とにかくスコアの悪いノードを適当にたたき落とせばいいというのが結論だ。やってることはそれだけのことだが、これが意外と効果がある。実験データはいずれ示したいが、枝刈りをするとそこまでスコアを落とすことなく、かつ爆速で動作するようになる。

次回だが、動的計画法の処理でちょっとした工夫を思いついたので、それについて書こうと思う。（実は実装と簡単な性能評価まで終えており、より高速に動作することが確認できている。）

いつになったら実験データが出せるのやら・・・