組合せ爆発

組合せ最適化問題の解集合が問題のサイズが大きくなるにつれて爆発的に膨らむことをいう。指数的爆発とも。
即ち、n を問題のサイズとするとき 2^n、n! などのように指数的あるいは組合せ的に増大する。
この性質は多くの最適化問題にとって効率のよい解法を開発する上で根源的かつ致命的な障壁となることがある。
NP困難性に代表されるように、それを理論的に打破する解法開発の可能性が絶望的であることが示されている問題も多い。
そのためアルゴリズムには、組合せ爆発を防ぐ工夫をしたもの（近似アルゴリズム）がある。

ttp://www.orsj.or.jp/~wiki/wiki/index.php/%E7%B5%84%E5%90%88%E3%81%9B%E7%9A%84%E7%88%86%E7%99%BA
ttp://ja.wikipedia.org/wiki/%E7%B5%84%E5%90%88%E3%81%9B%E7%88%86%E7%99%BA
ttp://en.wikipedia.org/wiki/Combinatorial_explosion

参照（語彙）：
最適化問題
ttp://ja.wikipedia.org/wiki/%E6%9C%80%E9%81%A9%E5%8C%96%E5%95%8F%E9%A1%8C
ttp://en.wikipedia.org/wiki/Optimization_(mathematics)
ttp://www.orsj.or.jp/~wiki/wiki/index.php/%E7%B5%84%E5%90%88%E3%81%9B%E6%9C%80%E9%81%A9%E5%8C%96%E5%95%8F%E9%A1%8C
近似アルゴリズム
ttp://ja.wikipedia.org/wiki/%E8%BF%91%E4%BC%BC%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
ttp://en.wikipedia.org/wiki/Approximation_algorithm
ttp://www.orsj.or.jp/~wiki/wiki/index.php/%E8%BF%91%E4%BC%BC%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

参照（関連サイト）：
次元の呪い
ttp://ja.wikipedia.org/wiki/%E6%AC%A1%E5%85%83%E3%81%AE%E5%91%AA%E3%81%84
ttp://en.wikipedia.org/wiki/Curse_of_dimensionality
無限の猿定理
ttp://ja.wikipedia.org/wiki/%E7%84%A1%E9%99%90%E3%81%AE%E7%8C%BF%E5%AE%9A%E7%90%86
ttp://en.wikipedia.org/wiki/Infinite_monkey_theorem

参照（過去の日記）：NP困難とNP完全
ttp://mixi.jp/view_diary.pl?id=666798284&owner_id=14882521

参照（未来の日記）：
ソート
ttp://mixi.jp/view_diary.pl?id=1668462451&owner_id=14882521
自己回避歩行
ttp://mixi.jp/view_diary.pl?id=1871027720&owner_id=14882521
エイト・クイーンパズル
ttp://mixi.jp/view_diary.pl?id=1896503142&owner_id=14882521
魔方陣
ttp://mixi.jp/view_diary.pl?id=1912359226&owner_id=14882521