"Вот только не надо мне тут завидовать!"  ©

Не дождетесь! 

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

И снова провожу оранжевую линию.

Точка касания уйдет теперь в верхнюю часть маршрута, а зеленая линия опустится ниже:

Убираем все лишнее и, вуаля!

Эффект - потрясающий!

Маршрут сразу стал короче на 30,512 и его длина составляет теперь 482,148.

Но это максимальный минимум для данного метода. дальнейшая оптимизация невозможна.

Но у меня еще в запасе есть вариант оптимизации, обходом маршрута из той же точки, но в противоположную сторону.
Этот вариант я рассмотрю уже этим ночером...

Отредактировано Лукомор (2019-01-22 17:54:46)

В принципе, я их везде обозначаю координатами (X,Y), мне хватает.
Более того, мне так удобно, так как я из этих же цифр сразу же и нахожу длины отрезков,
по Пифагору, а иногда и без него.

Например, ты только что предложил убрать:
- оранжевый отрезок (25,70)-(50,75);
- черный отрезок (30,50)-(50,25) ;
- зеленый отрезок (47,50)-(85,20).

Вместо них провести отрезки:
+ (25,70)-(30,50);
+ (50,75)-(47,50);
+ (50,25)-(85,20);

У меня есть два замечания по этому предложению.

1. Идея перекоммутации путей именно в таком порядке хорошая, но она ниоткуда не следует.
Напомню, что весь этот фонтан моих рисунков вылился из вопроса Шарпера: "Как развязывать петли?"
Я переспросил: что такое петля? - и Шарпер приволок с Хабра этот чертеж с петлями.
До сих пор не знаю, на хрена Шарперу развязывать петли, у него же совсем другая проблема с мусорными путями.
Но я показал на этом примере, как их развязывать, и не только реальные, которых было всего две, в самом начале,
на исходном чертеже.

Потом Зоркий Сокол наконец заметил, что если по очереди исключать по одной точке из маршрута, то при этом на сокращенном маршруте могут получаться тоже петли,
и если их распутывать, а потом возвратить на место временно исключенную точку, то получившийся маршрут может стать короче, а может и не стать.
Я таким образом распутал еще три виртуальных петли, и получил более короткий маршрут, но не кратчайший.
А вот в предложенном тобой варианте петли нет, распутывать нечего,
и не понятно, почему надо делать именно такое преобразование маршрута, хотя на первый взгляд оно выглядит хорошим.

2. Чертеж с Хабра сделан весьма неаккуратно, что на первых порах у меня вызывало массу проблем.
Во-первых, горизонтальная ось Х, начинается не с нуля, а с 5.
Две крайних левых точки имеют координаты (10,5) и (10, 85),
а не (5,5) и (5,85), как это кажется с первого взгляда.
Я достаточно долго не мог привыкнуть к этому, и постоянно ошибался в расчете длин отрезков, начинающихся в этих двух точках.
Но это ерунда, поошибался и привык.
Во-вторых, и это существенно, масштаб по вертикали в полтора раза меньше, чем по горизонтали,
из-за чего вертикальные отрезки кажутся значительно короче горизонтальных при равной их длине.
Правильный чертеж выглядит как-то так:

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

Впрочем, в оригинальной задаче, откуда взят этот чертеж,
узлы пронумерованы от нулевого до 16го, и я, в следующих рисунках,
пожалуй, пронумерую узлы на чертеже, чтобы были понятны заголовки рисунков:
маршрут начинается с 10 города, или маршрут начинается с четвертого города.

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

Аминь! 

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

Это еще два линейных участка, в дополнение к твоему,
они просто сложились в замысловатую фигуру...

Вот, кстати, исходное условие задачи из того учебного примера, :

и нумерация городов согласно этому условию:

Кстати, в заголовке к плану маршрута, вот этот вот пассаж заставляет усомниться в его истинности:
"Координаты X,Y случайные числа от 0 до 100".

Из 34 случайных координат, только абсцисса пятнадцатого узла не кратна 5.
Это ж такая редкая удача! 

Отредактировано Лукомор (2019-01-23 11:15:37)

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

Ну, не знаю... 
Ну, например, борьба с глобальным потеплением...
Или потепление - это тоже энтропия?