組合せ的爆発(読み)くみあわせてきばくはつ(英語表記)combinatorial explosion

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

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

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

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

関連語をあわせて調べる

今日のキーワード

ブラックフライデー

米国などで、感謝祭(11月第4木曜日)の翌日の金曜日のこと。休日とする職場が多く、商店にとってはクリスマス商戦の初日に当たる。「ブラック」は、買い物客による混雑、または黒字を連想させることから。→サイ...

続きを読む

コトバンク for iPhone

コトバンク for Android