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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

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

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

Приклади[ред. | ред. код]

abcdefgh
8
a8 чорна тура
b8 чорний кінь
c8 чорний слон
d8 чорний ферзь
e8 чорний король
f8 чорний слон
g8 чорний кінь
h8 чорна тура
a7 чорний пішак
b7 чорний пішак
c7 чорний пішак
d7 чорний пішак
e7 чорний пішак
f7 чорний пішак
g7 чорний пішак
h7 чорний пішак
a2 білий пішак
b2 білий пішак
c2 білий пішак
d2 білий пішак
e2 білий пішак
f2 білий пішак
g2 білий пішак
h2 білий пішак
a1 біла тура
b1 білий кінь
c1 білий слон
d1 білий ферзь
e1 білий король
f1 білий слон
g1 білий кінь
h1 біла тура
8
77
66
55
44
33
22
11
abcdefgh
Початкове положення фігур у шахах

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

Задача комівояжера[ред. | ред. код]

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

Шахи[ред. | ред. код]

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

Примітки[ред. | ред. код]