Решение задачи коммивояжёра с помощью гамильтоновых циклов заключается в нахождении гамильтонова цикла минимального веса в полном взвешенном графе. 2

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

Алгоритм решения: 2

1. Построение матрицы с исходными данными. 2 Длины дорог, соединяющих города, представляют в виде таблицы. 2
2. Нахождение минимума по строкам. 2 В каждой строке матрицы находят минимальный элемент и вычитают его из всех элементов соответствующей строки. 1
3. Редукция строк. 2
4. Нахождение минимума по столбцам. 2 В каждом столбце матрицы выбирают минимальный элемент и вычитают его из всех элементов соответствующего столбца. 1
5. Редукция столбцов. 2
6. Вычисление оценок нулевых клеток. 2
7. Редукция матрицы. 2
8. Если полный путь ещё не найден, переходят к пункту 2, если найден — к пункту 9. 2
9. Вычисление итоговой длины пути и построение маршрута. 2

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