93
правки
Изменения
Нет описания правки
== Варианты решения ==
В теории алгоритмов NP-полная(NPC, NP-complete) задача — задача из класса NP, к которой можно свести любую другую задачу из класса NP за полиномиальное время. Таким образом, NP-полные задачи образуют в некотором смысле подмножество «самых сложных» задач в классе NP; и если для какой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро». Cтатус NP-полных задач пока что неизвестен. Для их решения до настоящего времени не разработано алгоритмов с полиномиальным временем работы, но и не доказано, что для какой-то из них алгоритмов не существует. Этот так называемый вопрос P<tex>\ne</tex>NP с момента своей постановки в 1971 году стал одним из самых трудных в теории вычислительных систем.
Так вот задача о коммивояжере относится к классу NP-полных задач. Рассмотрим два варианта решения.
Можно решить задачу перебором всевозможных перестановок. Для этого нужно сгенерировать все <tex> N! </tex> всевозможных перестановок вершин исходного графа, подсчитать для каждой перестановки длину маршрута и выбрать минимальный из них. Но тогда задача оказывается неосуществимой даже для достаточно небольших <tex>N</tex>. Сложность алгоритма <tex>O(N!)</tex>.
==== Динамическое программирование по подмножествам(по маскам) ====
Задача о коммивояжере представляет собой поиск кратчайшего гамильтонова цикла в графе.
