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

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

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

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

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

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

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

a b c d e f g h
8
Chessboard480.svg
a8 black rook
b8 black knight
c8 black bishop
d8 black queen
e8 black king
f8 black bishop
g8 black knight
h8 black rook
a7 black pawn
b7 black pawn
c7 black pawn
d7 black pawn
e7 black pawn
f7 black pawn
g7 black pawn
h7 black pawn
a2 white pawn
b2 white pawn
c2 white pawn
d2 white pawn
e2 white pawn
f2 white pawn
g2 white pawn
h2 white pawn
a1 white rook
b1 white knight
c1 white bishop
d1 white queen
e1 white king
f1 white bishop
g1 white knight
h1 white rook
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]

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

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

P_n = n!

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

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

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