Некоторые исследования задачи коммивояжера

Метод выпуклого многоугольника
Построение наибольшего выпуклого многоугольника
Включение внутренних точек к ближайшим граням

Недостатки метода
Подразумевается существование полного связного графа
Неудобный метод задания условия

Метод достройки до эйлерова цикла

Добавим ребро
6 — 2
2 — 3
2 — 5
2 — 1 — 3
3 — 4 — 5
2 — 6 — 5
Конечный тур:
3-1-2-6-5-4-3

Задача с несколькими коммивояжерами
Наиболее удаленные вершины 4 и 3
1 — 4 — 5
2 — 3 — 6
2 + 3 + 4 = 9
2 + 1 + 5 = 8
17 < 23
1-4-5-6-3-2-1 — точный тур