組合せ的爆発

デジタル大辞泉

くみあわせ‐ばくはつ〔くみあはせ‐〕【組（み）合（わ）せ爆発】

読み方：くみあわせばくはつ

コンピューターの計算理論において、問題を解く上で必要な条件や要素の組み合わせが増加することにより、計算量の爆発を伴うこと。計算時間が問題の規模の指数関数または階乗に比例して大きくなるため、事実上、有限時間内で解けなくなる場合がある。組み合わせ論的爆発。組み合わせ的爆発。

OR事典

組合せ的爆発

読み方：くみあわせてきばくはつ
【英】：combinatorial explosion

組合せ最適化問題の解集合が, 問題のサイズが大きくなるにつれて爆発的に膨らむことをいう. 指数的爆発ともいう. すなわち, を問題のサイズとするとき, , などのように指数的あるいは組合せ的に増大する. この性質は, 多くの組合せ最適化問題にとって, 効率のよい解法を開発する上で根源的かつ致命的な障壁となることがある. NP困難性に代表されるように, それを理論的に打破する解法開発の可能性が絶望的であることが示されている問題も多い.

「OR事典」の他の用語

組合せ最適化：

混合整数計画  確率アルゴリズム  組合せ最適化問題  組合せ的爆発  計算の複雑さ  貪欲アルゴリズム  連結度

ウィキペディア

組合せ爆発

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/29 06:55 UTC 版)

組合せ爆発（くみあわせばくはつ、英: combinatorial explosion）は、計算機科学、応用数学、情報工学、人工知能などの分野では、解が組合せ（combination）的な条件で定義される離散最適化問題で、問題の大きさn に対して解の数が指数関数や階乗などのオーダーで急激に大きくなってしまうために、有限時間で解あるいは最適解を発見することが困難になることをいう。