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