組み合わせ問題の解法とその応用

No Image

 時間割作成は,すべての授業に曜日・時限・教室を矛盾なく割り当てる問題であり,多数の組み合わせの中から学生が適切に履修できるような時間割を探す問題です.また宅配便の配達では,どの荷物をどのトラックに載せ,どのような順序で運送するかを計画する必要があり,これも多数の組み合わせの中から短時間で効率的に配達できる計画を探す必要があります.ソフトウェアの開発では様々な状況で正しく動作するか検査するため,多様な状況の組み合わせを保ちつつテスト回数を抑えるようなテストケースを構成する必要があります.製品製造の工場では,工員や製造装置などの限られた資源を効率よくスケジューリングするため,どのように割り当てるべきか多数の組み合わせの中から適切なスケジュールを探す必要があります.
 このように多数の組み合わせから与えられた条件を満たす解を探し出す問題は社会の様々なところに現れます.もし組み合わせの数が少ないならば人手で解くこともできるかもしれませんが,一般には組み合わせの数は膨大なものになります.例えば2種類の状態をとる要素が100 個あるとき,2^100 個の組み合わせがあります.もし1秒間に1京個の組み合わせを調べたとしても,すべてを調べきるには単純計算で400 万年も必要となります.しかし最新のコンピュータ科学ならば,与えられた条件を満たす組み合わせを数秒で発見することが可能になってきています.私たちの研究室では,大規模な組み合わせ問題を効率的に解く手法の研究に取り組んでいます.