Комбінаторний вибух

Комбінаторний вибух — термін, який використовується для опису ефекту різкого («вибухового») зростання часової складності алгоритму при збільшенні розміру вхідних даних задачі.

Більш точно це означає, що алгоритм не є поліноміальним, тобто час розв'язування задачі не обмежується ніяким многочленом від довжини входу. Зазвичай такі задачі мають експоненціальну або навіть надекспоненціальну складність.

Походження назви пов'язане з тим, що для розв'язування задачі не вдається знайти іншого способу, крім повного перебору всіх можливих варіантів. У цьому випадку час, що потрібен для розв'язування, пропорційний до кількості всіх можливих конфігурацій, яка визначається на основі тих чи інших комбінаторних міркувань (сполучення, перестановки).

Для обходу проблеми комбінаторного вибуху шукають спеціальні методи розв'язування, зокрема, застосовують евристичні алгоритми.

Приклади

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Початкове положення фігур у шахах

Комбінаторний вибух виникає в багатьох задачах пошуку, в задачах прорахунку послідовностей, що розв'язуються методами прямого перебору.

Задача комівояжера

Докладніше: Задача комівояжера

У класичній задачі комівояжера потрібно знайти оптимальну послідовність відвідування комівояжером ${\displaystyle n}$ міст. Єдиний точний спосіб розв'язування задачі полягає в переборі всіх можливих маршрутів і виборі того, який потребує найменшої кількості часу. Тим самим складність розв'язування задачі комівояжера є пропорційною до кількості всіх можливих послідовностей міст, яку можна порахувати за формулою перестановок:

${\displaystyle P_{n}=n!}$

Шахи

Гіпотетично можливо прорахувати всі варіанти ходів у настільній грі шахи від початку гри до кінця методом повного перебору всіх комбінацій. Однак наразі та у найближчому майбутньому розв'язати таку задачу практично неможливо. Наприклад, для обчислювальної машини, здатної прорахувати мільйон ігрових комбінацій за секунду з відкиданням явно неоптимальних гілок, на прорахунок 6 ходів наперед потрібна 1 секунда, на 12 ходів — 11 днів, а на 18 ходів — близько 32 000 років.

Примітки

1. Web Dictionary of Cybernetics and Systems [ 2010-08-06 у Wayback Machine.] (англ.)
2. A Dictionary of Computing (англ.)
3. Articles on Artificial Intelligence [ 2011-08-23 у Wayback Machine.] (англ.)
4. Denys Duchier, Claire Gardent and Joachim Niehren. Concurrent Constraint Programming in Oz for Natural Language Processing [ 2011-08-12 у Wayback Machine.] (англ.)