Модификаций задачи коммивояжера много есть разных....
Про некоторые лучше и вовсе не знать! 

Шарпер как раз решает не замкнутую, как детский бильярд,
в этом вы единомышленники.

Я решаю классическую, замкнутую.
Это - как детский бумеранг.   

Так что продолжай говорить прозой,
мысли у тебя глубокие, местами пророческие,
но почерк не разборчивый.

Отредактировано Лукомор (2019-01-20 00:35:32)

Для чернового решения в первом приближении,
пожалуй, соглашусь,
что это оптимальная стратегия.

При последовательном уточнении решения,
и приближении к оптимальному маршруту,
нужно будет стратегию менять.

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

Я не смог сразу подобрать контрпример к этому утверждению.
И мне уже начинает казаться, что такого контрпримера не существует.

Зато у меня получился другой трюк.
Я взял маршрут коммивояжера, который мне не показался кратчайшим, по ссылке от Шарпера.
Я выбросил из этого маршрута один узел, соединил края, и получил новый маршрут с петлей, то-есть не кратчайший.
Когда я распутал петлю, и возвернул обратно на место исключенный узел, новый маршрут стал чуть короче исходного.
И мне кажется, что этот новый маршрут уже реально кратчайший возможный.

Вот условие задачи для N=17 узлов (в час. © Ёкэл  ).
С хабра.

Вот решение, оттуда же, по методу "ближайшего соседа", далекое от оптимального...

Вот решение, тоже оттуда, полученное модифицированным алгоритмом:

Оно выглядит оптимальным, по крайней мере трудно найти более короткий маршрут.

Я убрал точку (10,5) - это крайняя нижняя левая точка на графике.
Точки связанные с ней:
(30, 10) и (47, 50) я временно соединил отрезком.
Этот новый отрезок пересек предыдущий отрезок
(50, 25) -- (35, 25) - получилась петля.
(обход по часовой стрелке!)

Я распутал петлю, изменив порядок прохождения узлов.
Вместо (50, 25) -- (35, 25) -- (30, 10) -- (47, 50)
теперь будет (50, 25) --  (30, 10) -- (35, 25) -- (47, 50).

Теперь, вернув на место временно изъятый узел,
я получил окончательный фрагмент кратчайшего (надеюсь!) маршрута:
(50, 25) --  (30, 10) -- (10, 5 ) -- (35, 25) -- (47, 50).

И, если я не наврал в арифметике,
кратчайший путь теперь стал равным: 453,180,
короче на 4,324, нежели найденный компутером с помощью модифицированного алгоритма ближайшего соседа....

Отредактировано Лукомор (2019-01-20 10:24:46)

Я однажды с 3 км. бухты телефонного кабеля 600 метров выдернул, ну так удачно! 
(срочно нужно было 600 м.)
Оставшиеся 2,4 км. - 10 дней мы вдвоём распутывали, ругая, естественно, меня! 

Отредактировано Лукомор (2019-01-20 12:27:36)

Естественно, если выбросить все, кроме трех узлов,
то оставшийся треугольник и будет кратчайшим путем.
Он же будет и самым длинным, поскольку сам - один.

Внимание, вопрос!

Как теперь вернуть все узлы по одному или группами,
по ходу доворачивая - выворачивая, чтобы получился кратчайший маршрут на исходном графе?!

Да, кратчайший маршрут, верифицированный, что он кратчайший.

Не обязательно!

"Треугольник - фигура жесткая, но справедливая!" © Лукомор 
Недаром существует триангуляция, основанная на свойствах треугольника именно.

Отредактировано Лукомор (2019-01-20 12:30:03)