Пришло время рассказать о моем крайнем изобретении - о методе нахождения кратчайшего пути, который базируется на обобщении понятия детура точки и прямой на произвольный многоугольник с некоторым количеством изолированных точек внутри него.
Ранее мы выяснили, что для треугольника с изолированной точкой внутри периметра кратчайший маршрут через эту точку и все три вершины можно получить, исключив сторону треугольника, имеющую с внутренней точкой наименьший детур, и соединив эту точку с концами исключенной стороны.
Это правило можно распространить на произвольный выпуклый многоугольник с одной точкой внутри него.
Обобщая это же правило выбора минимального детура на произвольные участки маршрута с некоторым количеством изолированных точек, я получил метод, который я назвал методом "имитации термоусадки". Почему бы нет?
Ведь существует метод решения задачи коммивояжера, который называется метод "имитации отжига".
Мне показалось постепенное сжатие периметра многоугольника по мере включения в маршрут новых точек,
похожим на то, как сжимается при нагреве термоусадочная трубка на кабельной муфте, например, создавая герметичную изоляцию.
Я буду демонстрировать предлагаемый метод на примере всё той же проклятой комбинации из 13 пунктов, на которой сломался мой метод "объединения точек".
Напомню условия задачи:
1. Координаты 13 пунктов:
2. План местности:
3. Матрица расстояний:
Отредактировано Лукомор (2019-09-21 09:22:13)
