Комбинаторный взрыв

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

Более точно это означает, что рассматриваемый алгоритм не является полиномиальным, то есть время решения задачи не ограничено никаким многочленом от длины входа. Обычно такие задачи имеют экспоненциальную или даже сверхэкспоненциальную сложность.

Происхождение названия связано с тем, что для решения задачи не удается найти иного способа^{[источник не указан 868 дней]}, кроме полного перебора всех возможных вариантов. В этом случае время, требуемое для решения, пропорционально количеству всех возможных конфигураций, которое определяется из тех или иных комбинаторных соображений (сочетания, перестановки).

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

Примеры

Начальное положение фигур в настольной игре шахматы

Комбинаторный взрыв возникает во многих задачах поиска^[2], в задачах просчёта последовательностей, решаемых методами прямого перебора.^[3][4]

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

См. также: Задача коммивояжёра

В классической задаче коммивояжёра требуется найти оптимальную последовательность посещения коммивояжером $n$ городов. Единственный точный способ решения задачи состоит в том, чтобы перебрать все возможные маршруты и выбрать тот, который занимает наименьшее количество времени. Тем самым сложность решения задачи коммивояжера оказывается пропорциональной числу всех возможных последовательностей городов, которое дается формулой перестановок:

$P_n = n!$

Шахматы

Так, например, гипотетически возможно просчитать все варианты ходов в настольной игре шахматы от начала игры до конца методом полного перебора всех комбинаций. Однако в настоящее время и в ближайшем будущем^[2] решить такую задачу практически невозможно. Например, для вычислительной машины, способной просчитать миллион игровых комбинаций в секунду с отсевом заведомо неоптимальных ветвей, на просчёт 6 ходов вперёд потребуется 1 секунда, на 12 ходов — 11 дней, а на 18 ходов — около 32000 лет.^[2]

Примечания

1. ↑ Web Dictionary of Cybernetics and Systems
2. ↑ ^{1 2 3} 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