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

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

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

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

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

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

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

abcdefgh
8
Chessboard480.svg
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].

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