組合せ爆発(くみあわせばくはつ、英: combinatorial explosion)は、計算機科学、応用数学、情報工学、人工知能などの分野では、解が組合せ(combination)的な条件で定義される離散最適化問題で、問題の大きさn に対して解の数が指数関数や階乗などのオーダーで急激に大きくなってしまうために、有限時間で解あるいは最適解を発見することが困難になることをいう。 概説[編集] それ以外の通信ネットワーク、情報システム開発、化学その他の分野ではより広義に、要素の数が多くなるとその組合せによって急激に、考えられる可能性の数、とりうる実現形の数、実行すべき手順の数、あるいは全体の複雑さが非常に巨大化してしまうことをいう。 組合せ的爆発(くみあわせてきばくはつ)、組合せ論的爆発(くみあわせろんてきばくはつ)ともいう。計算量の爆発(けいさんりょうのばくはつ)の方がより一般概念であり、そ
![組合せ爆発 - Wikipedia](https://cdn-ak-scissors.b.st-hatena.com/image/square/170481a1b7288fe25925eddc19061783059f3ec5/height=288;version=1;width=512/https%3A%2F%2Fupload.wikimedia.org%2Fwikipedia%2Fcommons%2Fthumb%2F6%2F67%2F4x2.svg%2F125px-4x2.svg.png)