組合せ爆発

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

概説

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

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

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

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

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

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

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

1対1の通信路を使うと、4ノードで6つの通信路を必要とする。

何らかの媒介手段があれば、各ノードからは1つの通信路で済む。

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

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

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

これを減らすためのひとつの方法は、情報を媒介する汎用的手段を中心に置くことであり、この場合通信路の数はノード数n に等しくて済む。しかしこの場合の欠点は、

1. 1対1では電話やテレタイプのように特に手順らしい手順を定めなくとも通信できるかもしれないが、媒介手段に対応するためには通信内容に付加された宛先に基づく経路制御をする必要があるのでTCP/IP、SMTPなど何らかの通信プロトコルを導入する必要が生じる点
2. 中心の媒介手段が障害や性能不足に陥れば全部の通信が影響を受ける点

である。2. の欠点のために、実際の設計では必ずしも通信路の数を減らしさえすればいいわけではなく、ある程度の冗長性を残した複雑なシステムを構築することが多い。

計算機科学における計算量の爆発

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

素因数分解問題の例

素因数分解問題の計算量は指数時間であって、多項式時間では解けないと予想されている。このおかげで現在広く使われている公開鍵暗号のRSA暗号が、パソコンやスーパーコンピュータでは数日、数カ月といった現実的な時間では到底解けないと期待されている。ところが、量子コンピュータを用いれば素因数分解問題は多項式時間で解けてしまうことが発見された（Shor、1994年）。

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

関連項目

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

外部リンク

• 組合せ的爆発（日本オペレーションズ・ リサーチ（OR）学会）
• 組み合わせ爆発をわかりやすく解説したアニメ（日本未来科学館）