Приложение №3
Я решил две задачи коммивояжера, одна из них была линейная,
во второй я повернул каждый следующий участок маршрута
относительно предыдущего на 30 градусов.
Кратчайший маршрут от такого поворота не изменился,
сохранилась последовательность прохождения пунктов,
и длина маршрута в незамкнутом варианте задачи (=700).
В замкнутом варианте длина маршрута стала короче
(1230,06 против 1400 в линейной задаче).
Я предположил, что пока многоугольник остается выпуклым,
кратчайший маршрут будет пролегать по внешнему периметру
многоугольника, и по этой причине можно не рассматривать те
участки пути, которые являются диагоналями многоугольника,
и сразу выбросить из рассмотрения те маршруты, которые
содержат хотя бы одну диагональ многоугольника.
Ни один из таких маршрутов не будет кратчайшим.
Чтобы убедиться в справедливости такого вывода,
я решил еще несколько задач коммивояжера.
Все эти задачи объединяет одно общее условие.
Все они на нахождение кратчайшего маршрута через 6 пунктов,
и расстояния между соседними пунктами равны:
AB=100, BC=120, CD=140, DE=160, EF=180.
Переменным условием в этих задачах будет угол поворота
последующего участка маршрута по отношению к предыдущему.
Для первой (линейной) задачи этот угол был равен 0,
так, что все пункты лежали на одной прямой.
Для второй задачи угол между соседними звеньями составлял 30 градусов.
Такой поворот не повлиял на порядок проследования пунктов кратчайшего маршрута.
В третьей задаче я увеличил угол между соседними участками пути до 45 градусов,
Так, ч то величины углов между соседними участками составили 135 градусов:
Это углы: ABC = BCD = CDE = DEF = 135 (градусов).
Условие задачи №3. Граф и матрица расстояний.
Решение задачи №3.
Я не буду здесь повторять своё "решение руками" из предыдущих задач.
Любой желающий может найти его самостоятельно.
Доверим решение задачи коммивояжера с новыми условиями онлайн-сервису.
Введем матрицу расстояний:
И получим решение:
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(6,5), (5,4), (4,3), (3,2), (2,1), (1,6),
Длина маршрута равна F(Mk) = 1054.9
Решение было получено и оформлено с помощью сервиса:
Задача коммивояжера
Вывод:
Многоугольник остался выпуклым, поэтому
порядок проследования пунктов и длина кратчайшего незамкнутого маршрута не изменились
при повороте на 45 градусов последующих участков по отношению к предыдущим.
Отредактировано Лукомор (2018-09-19 17:47:17)
