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

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

Это правило можно распространить на произвольный выпуклый многоугольник с одной точкой внутри него.
Пример для выпуклого четырехугольника ABCE c точкой F внутри:

Это правило можно распространить на произвольный выпуклый многоугольник с одной точкой внутри него.
Пример для выпуклого четырехугольника ABCE c точкой F внутри:


Мы нашли кратчайший маршрут Lкр = 168, просто , как сумму периметра четырехугольника и наименьшего из детуров.
Соответственно , сам маршрут получается исключением стороны четырехугольника , соответствующей наименьшему детуру
и соединением точки внутри четырехугольника с вершинами - концами исключенной стороны.

Отредактировано Лукомор (2019-09-16 09:14:37)

Как скажешь!
Если тебе лучше - пусть будет.
Мне - одинаково.

У меня тоже есть более сложная мысля... и она более простая!
Но все мои мысли почему то ломаются об условие задачи на 13 пунктов. 

И количество три-на-дцать тоже не сахар...
Для 17 точек оба моих метода работают великолепно.
Для 13 точек проседают хуже метода ветвей и границ и даже хуже метода ближайшего соседа.
Дно пробито...

Отредактировано Лукомор (2019-09-19 14:49:42)