研究講演

6月1日(金) 13:00 - 13:40

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

~二分決定グラフを用いた膨大な量の組合せの数え上げと最適化~
協創情報研究部 西野 正彬

概要

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

講演アーカイブ

下記より本講演の動画をご覧頂けます.
「組合せ爆発」を乗り超える
~二分決定グラフを用いた膨大な量の組合せの数え上げと最適化~
44分33秒
再生する

当日の様子

講演資料


画像をクリックすると、PDFファイルが開きます。

講演者紹介

協創情報研究部
西野 正彬