「組合せ的爆発」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【くみあわせてきばくはつ (combinatorial explosion)】''' 組合せ最適化問題の解集合が, 問題のサイズが大きくなるにつれて爆発的に...') |
|||
| 1行目: | 1行目: | ||
'''【くみあわせてきばくはつ (combinatorial explosion)】''' | '''【くみあわせてきばくはつ (combinatorial explosion)】''' | ||
| − | 組合せ最適化問題の解集合が, 問題のサイズが大きくなるにつれて爆発的に膨らむことをいう. 指数的爆発ともいう. すなわち, | + | 組合せ最適化問題の解集合が, 問題のサイズが大きくなるにつれて爆発的に膨らむことをいう. 指数的爆発ともいう. すなわち, <math>n\,</math>を問題のサイズとするとき, <math>2^n\,</math>, <math>n!\,</math>などのように指数的あるいは組合せ的に増大する. この性質は, 多くの組合せ最適化問題にとって, 効率のよい解法を開発する上で根源的かつ致命的な障壁となることがある. NP困難性に代表されるように, それを理論的に打破する解法開発の可能性が絶望的であることが示されている問題も多い. |
2007年7月15日 (日) 17:43時点における版
【くみあわせてきばくはつ (combinatorial explosion)】
組合せ最適化問題の解集合が, 問題のサイズが大きくなるにつれて爆発的に膨らむことをいう. 指数的爆発ともいう. すなわち, を問題のサイズとするとき, , などのように指数的あるいは組合せ的に増大する. この性質は, 多くの組合せ最適化問題にとって, 効率のよい解法を開発する上で根源的かつ致命的な障壁となることがある. NP困難性に代表されるように, それを理論的に打破する解法開発の可能性が絶望的であることが示されている問題も多い.
