Изменения

}}

[[NP-полнота задач о гамильтоновом цикле и пути в графах]]

Так вот задача о коммивояжере относится к классу NP-полных задач. Поэтому, рассмотрим два варианта решения с экспоненциальным временем работы.

Можно решить задачу перебором всевозможных перестановок. Для этого нужно сгенерировать все <tex> N! </tex> всевозможных перестановок вершин исходного графа, подсчитать для каждой перестановки длину маршрута и выбрать минимальный из них. Но тогда задача оказывается неосуществимой даже для достаточно небольших <tex>N</tex>. Сложность алгоритма <tex>O({N!}\times{N})</tex>.

Задача о коммивояжере представляет собой поиск кратчайшего гамильтонова цикла в графе.