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

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

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

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

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

Приклади
abcdefgh
8
8
77
66
55
44
33
22
11
abcdefgh
Початкове положення фігур у шахах

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

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

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

Шахи

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

Примітки
  1. Web Dictionary of Cybernetics and Systems (англ.)
  2. A Dictionary of Computing (англ.)
  3. Articles on Artificial Intelligence (англ.)
  4. Denys Duchier, Claire Gardent and Joachim Niehren. Concurrent Constraint Programming in Oz for Natural Language Processing (англ.)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.