組合せ的爆発とは？わかりやすく解説

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

概説

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

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

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

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

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

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

通信ネットワークにおける組合せ爆発

コンピュータネットワークにおいて、ノードを追加していくと必要な通信路が急激に増大する。このことを組合せ爆発と称する。ただし、実際には指数関数的に増えるわけではなく、厳密にはせいぜい多項式的増大である。

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

l={\frac {n(n-1)}{2}}

この項目は、数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。

組合せ的爆発とは？わかりやすく解説

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