|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 組 ： [くみ] 【名詞】 1. class 2. group 3. team 4. set ・ 組合 ： [くみあい] 【名詞】 1. association 2. union ・ 合 ： [ごう] 【名詞】 1. go (approx. 0.18l or 0.33m) ・ 爆 ： [ばく] 1. (int) exclamation 2. burst of laughter ・ 爆発 ： [ばくはつ] 1. (n,vs) explosion 2. detonation 3. eruption ・ 発 ： [はつ] 1. (n,suf) (1) departure 2. (2) beginning 3. (3) issued by (e.g., document) 4. (4) counter for gunshots
組合せ爆発（くみあわせばくはつ、）は、計算機科学、応用数学、情報工学、人工知能などの分野では、解が組合せ（combination）的な条件で定義される離散最適化問題で、問題の大きさ''n'' に対して解の数が指数関数や階乗などのオーダーで急激に大きくなってしまうために、有限時間で解あるいは最適解を発見することが困難になることをいう。 それ以外の通信ネットワーク、情報システム開発、化学その他の分野ではより広義に、要素の数が多くなるとその組合せによって急激に、考えられる可能性の数、とりうる実現形の数、実行すべき手順の数、あるいは全体の複雑さが非常に巨大化してしまうことをいう。 組合せ的爆発（くみあわせてきばくはつ）、組合せ論的爆発（くみあわせろんてきばくはつ）ともいう。計算量の爆発（けいさんりょうのばくはつ）の方がより一般概念であり、それには指数的爆発（しすうてきばくはつ）も含まれる。こういった場合の組み合わせの数のような数を巨大数とも言う。 ''n'' の多項式オーダーで解ける場合は一般に、組合せ爆発とは言わない。組合せ爆発の変わった例として、再帰的参照を含み急激に巨大化するアッカーマン関数がある。 組合せ爆発を起こす関数をコンピュータで計算しようとすると、入力長に対して急激に出力長が大きくなったり、計算に時間がかかるようになる。そのためアルゴリズムには、組合せ爆発を防ぐ工夫をしたものがある。一方、多項式時間では解けないと証明された問題のクラスもある。 情報システム開発では、上記のような解空間巨大化による計算量増大現象とは言い方が異なるが、組合せ爆発が言われる。情報システムの構成要素やその状態が増えると、その組合せで作られるシステムの複雑性は爆発的に膨張するので、この問題への対応と解決は情報処理の重要な課題である。 日常的には、曽呂利新左衛門が「きょうは1粒、あしたは2粒…」の米を所望した話や、彦一が「将棋盤の1マス目に1粒、次のマス目には2粒」の米を所望した話のように、倍々に増える数の急激さのことなども、組合せ爆発と表現されていることがある。倍々ゲームは指数関数ではあるが、組合せとはいえない。 == 通信ネットワークにおける組合せ爆発 == コンピュータネットワークにおいて、ノードを追加していくと必要な通信路が急激に増大する。このことを組合せ爆発と称する。ただし、実際にはわけではなく、厳密にはせいぜい多項式的増大である。 2つのノード間で通信する必要があるとき、1対1の適当な通信路1本で直接接続すればよい。しかし、3つめのノードを追加すると、通信路が3本必要となる。4ノードでは6本、5ノードでは10本、6ノードでは15本と増えていく。これを一般化すると、''n'' ノードでの通信路数''l'' は次のように、''n'' の2乗のオーダーで増加する。 : これを減らすためのひとつの方法は、情報を媒介する汎用的手段を中心に置くことであり、この場合通信路の数はノード数''n'' に等しくて済む。しかしこの場合の欠点は、 #1対1では電話やテレタイプのように特に手順らしい手順を定めなくとも通信できるかもしれないが、媒介手段に対応するためには通信内容に付加された宛先に基づく経路制御をする必要があるのでTCP/IP、SMTPなど何らかの通信プロトコルを導入する必要が生じる点 #中心の媒介手段が障害や性能不足に陥れば全部の通信が影響を受ける点 である。2. の欠点のために、実際の設計では必ずしも通信路の数を減らしさえすればいいわけではなく、ある程度の冗長性を残した複雑なシステムを構築することが多い。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「組合せ爆発」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Combinatorial explosion 」があります。 スポンサード リンク
|