コトバンクはYahoo!辞書と技術提携しています。

組合せ的爆発 くみあわせてきばくはつcombinatorial explosion

ブリタニカ国際大百科事典 小項目事典の解説

組合せ的爆発
くみあわせてきばくはつ
combinatorial explosion

ゲームなどの問題において,次に実行可能なステップが多数存在する場合,目的にいたるまでの可能な場合の数が指数関数的に増大し,現代のいかなるコンピュータもそれを処理しきれないようなことがしばしば生じる。これを組合せ的爆発という。たとえばにおいて次に実行可能な手が 27 (128) あったとし,勝負が決るまで 200手必要であったとすると,(27)200=21400≒10420 となり,1手を1ナノ秒 (10-9秒) で実行したとしても 10411 秒必要となって,現実の時間内に解は得られない。

出典 ブリタニカ国際大百科事典 小項目事典ブリタニカ国際大百科事典 小項目事典について 情報

組合せ的爆発の関連キーワード勝負