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

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

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

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

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

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

Примеры[править | править вики-текст]

a b c d e f g h
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
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Начальное положение фигур в настольной игре шахматы

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

Задача коммивояжера[править | править вики-текст]

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

Шахматы[править | править вики-текст]

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

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