“組合せ爆発（くみあわせばくはつ、英: Combinatorial explosion）は、計算機科学、応用数学、情報工学、人工知能などの分野では、解が組合せ（combination）的な条件で定義される離散最適化問題で、問題の大きさnに対して解の数f(n)が指数関数や階乗などのオーダーで急激に大きくなってしまうために、有限時間で解あるいは最適解を発見することが困難になることをいう。 それ以外の通信ネットワーク、情報システム開発、化学その他の分野ではより広義に、要素の数が多くなるとその組合せによって急激に、考えられる可能性の数、とりうる実現形の数、実行すべき手順の数、あるいは全体の複雑さが非常に巨大化してしまうことをいう。 組合せ的爆発（くみあわせてきばくはつ）、組合せ論的爆発（くみあわせろんてきばくはつ）ともいう。計算量の爆発（けいさんりょうのばくはつ）の方がより一般概念であり、それには指数的爆発（しすうてきばくはつ）も含まれる。こういった場合の組み合わせの数のような数を巨大数とも言う。 nの多項式オーダーで解ける場合は一般に、組合せ爆発とは言わない。 組合せ爆発の変わった例として、再帰的参照を含み急激に巨大化するアッカーマン関数がある。 組合せ爆発を起こす関数をコンピュータで計算しようとすると、入力長に対して急激に出力長が大きくなったり、計算に時間がかかるようになる。そのためアルゴリズムには、組合せ爆発を防ぐ工夫をしたものがある。一方、多項式時間では解けないと証明された問題のクラスもある。 情報システム開発では、上記のような解空間巨大化による計算量増大現象とは言い方が異なるが、組合せ爆発が言われる。情報システムの構成要素やその状態が増えると、その組合せで作られるシステムの複雑性は爆発的に膨張するので、この問題への対応と解決は情報処理の重要な課題である。 日常的には、曽呂利新左衛門が「きょうは1粒、あしたは2粒…」の米を所望した話や、彦一が「将棋盤の1マス目に1粒、次のマス目には2粒」の米を所望した話のように、倍々に増える数の急激さのことなども、組合せ爆発と表現されていることがある。倍々ゲームは指数関数ではあるが、組合せとはいえない。”— 組合せ爆発 - Wikipedia (via petapeta)
水曜日
copipe
