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

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

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

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

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

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

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

Chess zhor 26.svg
Chess zver 26.svg
Chess rdl45.svg Chess ndd45.svg Chess bdl45.svg Chess qdd45.svg Chess kdl45.svg Chess bdd45.svg Chess ndl45.svg Chess rdd45.svg
Chess pdd45.svg Chess pdl45.svg Chess pdd45.svg Chess pdl45.svg Chess pdd45.svg Chess pdl45.svg Chess pdd45.svg Chess pdl45.svg
Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg
Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg
Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg
Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg Chess d45.svg Chess l45.svg
Chess pll45.svg Chess pld45.svg Chess pll45.svg Chess pld45.svg Chess pll45.svg Chess pld45.svg Chess pll45.svg Chess pld45.svg
Chess rld45.svg Chess nll45.svg Chess bld45.svg Chess qll45.svg Chess kld45.svg Chess bll45.svg Chess nld45.svg Chess rll45.svg
Chess zver 26.svg
Chess zhor 26.svg
Начальное положение фигур в настольной игре шахматы

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

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

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

P_n = n!

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

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

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