WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте

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

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

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

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

Примеры

abcdefgh
8
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]

Примечания

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии