アルゴリズムを考えるのを放棄してみると


2011年 01月 19日

コンピュータを上手に使うには、アルゴリズムに熟知している必要があるという。その中でも、ソート、サーチは最も基本的なものであり、呆れるほど高速な手法がある。そのような手法が見つかっている分野では、それを勉強し、抱えている問題に適用するだけでできる。

実際には、アルゴリズムが確立していない分野がたくさんある。とくに、スケジューリング問題は未開地だ。アルバイトスケジュール、ナース・スケジュール、資源割り当て、学校の時間割、列車の運行管理、配船計画、などなど、いくらでもある。

これらは、見かけよりやたらに条件が難しい。AさんとBさんは仲が悪いから一緒には働けないとか、さらには休暇や研修で穴が開くとか、船の場合だと海賊のことも考えるとか。さらには、運用中にトラブル(病気、退職、事件)が発生し、急にスケジュール変更しなければいけないこともある。

とにかく条件は無茶苦茶なのだ。学校だと、非常勤講師は色々な仕事を掛け持ちしているので、働ける時間帯が限られる。効率よく講義できるように、曜日や時間をまとめないといけない。コストも考えないといけない。

スケジュール問題は、事前にどのような条件があるかさえ定かでない世界である。この世界に向くアルゴリズムは難しい。皆が好き勝手な条件をつけてくる世界である。

上記の問題のほとんどは、今でも人間が神業で作り上げていることが多いのだが、何とか自動化できないかとずっと考えている。神業でもどうにもならないときには、増員したり、休講や運休したり、担当者を丸め込んだりして、何とか誤魔化しているのが実情だし、現実解なのだ。

それでたどり着いた戦略が、「もうアルゴリズムを考えるのをやめよう」ということだ。

アルゴリズムを放棄したのだから、ついでにプログラムも放棄してしまおう。プログラムをガリガリ書いて、条件に合う組み合わせを見つけるのは大変過ぎる。

肝心なことは、ぐちゃぐちゃの要求に対して、条件を満たす解を示すことだ。それさえできれば、OKなのだから。

では、どんな方法があるだろうか。次までに「秘策」を考えておこう。