組合せ爆発のソースを表示

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

== 概説 ==
それ以外の[[伝送路|通信ネットワーク]]、情報システム開発、化学その他の分野ではより広義に、要素の数が多くなるとその組合せによって急激に、考えられる可能性の数、とりうる実現形の数、実行すべき手順の数、あるいは全体の複雑さが非常に巨大化してしまうことをいう。

'''組合せ的爆発'''（くみあわせてきばくはつ）、'''組合せ論的爆発'''（くみあわせろんてきばくはつ）ともいう。'''計算量の爆発'''（けいさんりょうのばくはつ）の方がより一般概念であり、それには'''指数的爆発'''（しすうてきばくはつ）も含まれる。こういった場合の組み合わせの数のような数を[[巨大数]]とも言う。

''n'' の[[多項式]]オーダーで解ける場合は一般に、組合せ爆発とは言わない。組合せ爆発の変わった例として、再帰的参照を含み急激に巨大化する[[アッカーマン関数]]がある。

組合せ爆発を起こす関数を[[コンピュータ]]で計算しようとすると、入力長に対して急激に出力長が大きくなったり、計算に時間がかかるようになる。そのため[[アルゴリズム]]には、組合せ爆発を防ぐ工夫をしたものがある。一方、[[多項式]]時間では解けないと証明された問題のクラスもある。

情報システム開発では、上記のような解空間巨大化による計算量増大現象とは言い方が異なるが、組合せ爆発が言われる。情報システムの構成要素やその状態が増えると、その組合せで作られるシステムの複雑性は爆発的に膨張するので、この問題への対応と解決は情報処理の重要な課題である。

日常的には、[[曽呂利新左衛門]]が「きょうは1粒、あしたは2粒…」の米を所望した話や、[[彦一]]が「将棋盤の1マス目に1粒、次のマス目には2粒」の米を所望した話のように、倍々に増える数の急激さのことなども、組合せ爆発と表現されていることがある。倍々ゲームは指数関数ではあるが、組合せとはいえない。

== 通信ネットワークにおける組合せ爆発 ==
{| align="right"
|[[ファイル:4x2.svg|thumb|125px|1対1の通信路を使うと、4ノードで6つの通信路を必要とする。]]
|[[ファイル:4xn.svg|thumb|125px|何らかの媒介手段があれば、各ノードからは1つの通信路で済む。]]
|}
[[コンピュータネットワーク]]において、ノードを追加していくと必要な[[通信路]]が急激に増大する。このことを'''組合せ爆発'''と称する。ただし、実際には[[指数関数的成長|指数関数的に増える]]わけではなく、厳密にはせいぜい[[多項式]]的増大である。

2つのノード間で通信する必要があるとき、1対1の適当な通信路1本で直接接続すればよい。しかし、3つめのノードを追加すると、通信路が3本必要となる。4ノードでは6本、5ノードでは10本、6ノードでは15本と増えていく。これを一般化すると、''n'' ノードでの通信路数''l'' は次のように、''n'' の2乗のオーダーで増加する。
:<math>l=\frac{n(n-1)}{2}</math>

これを減らすためのひとつの方法は、情報を媒介する汎用的手段を中心に置くことであり、この場合通信路の数はノード数''n'' に等しくて済む。しかしこの場合の欠点は、
#1対1では電話やテレタイプのように特に手順らしい手順を定めなくとも通信できるかもしれないが、媒介手段に対応するためには通信内容に付加された宛先に基づく経路制御をする必要があるので[[TCP/IP]]、[[SMTP]]など何らかの[[通信プロトコル]]を導入する必要が生じる点
#中心の媒介手段が障害や性能不足に陥れば全部の通信が影響を受ける点
である。2. の欠点のために、実際の設計では必ずしも通信路の数を減らしさえすればいいわけではなく、ある程度の冗長性を残した複雑なシステムを構築することが多い。

==計算機科学における計算量の爆発==
計算機科学において、[[計算複雑性理論]]は重要な研究テーマである。たとえ解が存在して計算方法があっても、現実的なCPU数やメモリ容量の計算資源を使って、入力問題のサイズの多項式関数で表せるほどの短時間には解けないほど複雑な計算問題が存在する。[[複雑性クラス]]にはさまざまあるが、多項式関数の時間で解けない場合は'''計算量が爆発する'''と言われる。計算問題が組合せを内包している場合に'''組合せ爆発'''または'''組合せ的爆発'''といい、また指数関数のサイズになる場合に'''指数的爆発'''（{{en|exponential explosion}}）という。

===素因数分解問題の例===
[[素因数分解]]問題の計算量は指数時間であって、多項式時間では解けないと予想されている。このおかげで現在広く使われている[[公開鍵暗号]]の[[RSA暗号]]が、パソコンや[[スーパーコンピュータ]]では数日、数カ月といった現実的な時間では到底解けないと期待されている。ところが、[[量子コンピュータ]]を用いれば[[素因数分解]]問題は多項式時間で解けてしまうことが発見された（Shor<ref name="Shor94">[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.3862 Peter W. Shor, "Algorithms for Quantum Computation: Discrete Logarithms and Factoring", In Proceeding of 35th IEEE FOCS, pp.124-134, Santa Fe, NM, Nov 20-22, 1994. (Shorのアルゴリズムの論文) ]</ref>、1994年）。

この例のように、新しい計算モデルによって、組合せ爆発など計算量の爆発が起こるか起こらないかは変わることがある。量子計算などにより計算する側の計算量に爆発を起こすと、計算量の爆発に対応可能となるような計算資源が用意できる（ただし、2023年現在、この例を実際に計算可能な量子コンピュータが実現できる現実的な見通しはまだ無い）。

== 参考文献 ==
<references />

== 関連項目 ==
* [[計算複雑性理論]]
* [[複雑性クラス]]
* [[力まかせ探索]]（しらみつぶし探索ともいう）
* [[総当たり攻撃]]
* [[次元の呪い]]
* [[グラフ理論]]
* [[ネットワーク構成]]
* [[欧州連合の言語]]（全加盟国の言語を公用語としているため加盟国の増大に伴い実務上の問題となっている）

== 外部リンク ==
* [http://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 組合せ的爆発]（日本オペレーションズ・ リサーチ（OR）学会）{{リンク切れ|date=2025年2月}}
* [https://www.youtube.com/watch?v=Q4gTV4r0zRs 組み合わせ爆発をわかりやすく解説したアニメ]（日本未来科学館）

{{Math-stub}}

{{デフォルトソート:くみあわせはくはつ}}
[[Category:組合せ論]]
[[Category:組合せゲーム理論]]
[[Category:コンピュータネットワーク]]
<!--物理的な爆発ではないですが、比喩としてカテゴリに入れておくのも面白いでしょう-->
[[Category:数学に関する記事]]