Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

5.6. Г
АМИЛЬТОНОВЫ ЦИКЛЫ И ЗАДАЧА КОММИВОЯЖЕРА
 
Одной из формулировок задачи о поиске гамильтонова цикла является 
известная задача коммивояжера. Требуется найти кратчайший замкнутый 
21 / 23

---

183 
путь обхода нескольких городов, заданных своими координатами. Уже для 
относительно небольшого числа городов, порядка 60, эта задача оказывается 
практически неразрешимой путем простого перебора вариантов. Попытки ее 
решения дали толчок развитию новых вычислительных методов, в том числе 
нейронных сетей и генетических алгоритмов. 
Каждый вариант решения данной задачи представляет собой строку, 
где на j-ом месте стоит номер j-го по порядку обхода города. Таким образом, 
в этой задаче N параметров, причем не все комбинации значений допустимы. 
Эта задача NP-полная (задача с нелинейной полиномиальной оценкой числа 
итераций). Генетический алгоритм используется для нахождения приблизи-
тельно оптимального пути за линейное время. В любой момент времени ком-
мивояжер может быть только в каком-то городе. Города могут посещаться 
только однажды. 
Проблема коммивояжера может быть успешно решена аналитическими 
методами для небольшого количества городов. Существенным недостатком 
этих методов является то, что при увеличении числа городов вычислительная 
сложность решения этой проблемы существенно возрастает, и при некоторых 
условиях она уже не может быть решена за линейное время или решается, но 
не оптимально. 
Самые простые из аналитических методов решений – это полный пере-
бор, кратчайший незамкнутый путь и метод ветвей и границ 
Полный перебор крайне неэффективен с точки зрения вычислительной 
сложности. Количество всех просматриваемых решений равно N!, где N — 
количество городов. Преимущество этого метода заключается в том, что по-
лученное с его помощью решение является однозначно оптимальным. 
Метод кратчайшего незамкнутого пути заключается в следующем спо-
собе построения пути. Соединяются ребром две ближайшие точки, затем 
отыскивается точка, ближайшая к любой из уже рассмотренных точек, и со-
единяется с ней и т. д., до исчерпания всех точек. Главный недостаток этого 
метода состоит в том, что этот метод одиночной связи приводит к «серпан-
тинным» или «цепным» решениям. Также имеет экспоненциальную скорость 
роста.