「組合せ爆発」を乗り超える

会社の従業員を同じ人数の２つのグループに分けたいとします。このとき可能なグループ分けは何種類あるでしょうか？可能なグループ分けの種類数は、従業員の数が増えると急激に増加していきます。このような現象は「組合せ爆発」と呼ばれます。コンピュータを用いて組合せ爆発を起こす問題を素朴な方法で解こうとすると、計算時間が膨大になり、現実的な計算時間で問題が解けなくなります。本講演では二分決定グラフとよばれる技術を用いて膨大な数の組合せを効率的に数え上げる方法、および数え上げることで何が分かるかを、いくつかの事例を交えて紹介します。