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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

Примеры[править | править код]

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 ходов — около 32000 лет.[2]

Примечания[править | править код]