Эпиграф:
"Итак-а!" (с) Столбняк
Вступление:
Сразу оговорюсь, я решаю незамкнутый вариант
симметричной геометрической задачи коммивояжера.
Это означает, что маршрут коммивояжера начинается в одном городе,
проходит все остальные города ровно по одному разу,
и заканчивается в каком-нибудь другом городе,
без возврата в город, где маршрут начался.
При этом, расстояния "туда" и "обратно" между любой парой городов
равны между собой, а дороги между всеми городами являются прямыми линиями.
Следует отметить, что геометрическая задача коммивояжера с евклидовой метрикой
всегда будет одновременно и метрической,
поскольку в этом случае относмтельно длин всех рёбер выполняется неравенство треугольника.
В своем решении я нигде не использую ни манхэттенскую (квартальную метрику)
ни максимальную метрику.
Таким образом,
я НЕ решаю:
-замкнутый вариант симметричной геометрической задачи коммивояжера;
-замкнутый вариант асимметричной геометрической задачи коммивояжера;
-незамкнутый вариант асимметричной геометрической задачи коммивояжера;
Я также не решаю никакой из вариантов обобщенной задачи коммивояжера.
Постановка и решение задачи:
В отличие от классической ненаписанной статьи Белопушистого,
где автор предлагает решать задачу коммивояжера методом генерации
максимально возможного количества траекторий, которые не могут являться
маршрутами коммивояжера (т.наз. "мусорных" траекторий),
с последующим их исключением из рассмотрения,
наш оригинальный метод заключается в максимальном исключении из рассмотрения,
еще на предварительном этапе решения задачи,
тех разрешенных маршрутов, которые, по тем или иным признакам,
не могут, в принципе, быть кратчайшими.
После максимального исключения таких маршрутов,
решение задачи коммивояжера становится тривиальным.
Выявление и исключение таких разрешенных маршрутов на предварительном этапе решения задачи возможно, прежде всего,
исходя из геометрической формы графа расстояний, составленного на основании данных из условия задачи.
Исходя из сформулированной парадигмы, была поставлена и решена следующая задача:
"Каким условиям должен удовлетворять граф расстояний для задачи коммивояжера,
чтобы задача решалась за минимальное время?"
В результате всесторонних, более чем получасовых, исследований,
было найден ответ:
Задача коммивояжера проще всего решается, когда все N городов,
которые должен посетить коммивояжер, лежат на одной прямой линии".
Мы назвали этот вариант задачи коммивояжера - Линейной Задачей Коммивояжера.
Решениями Линейной Задачи Коммивояжера являются два кратчайших маршрута,
проложенных между двумя наиболее удаленными друг от друга городами,
таким образом, что все другие города находятся между этими двумя городами.
В этом варианте задачи коммивояжера длина кратчайшего маршрута
будет равна арифметической сумме расстояний между соседними городами.
Таким образом, для Линейной Задачи Коммивояжера с количеством городов равным N,
общее количество арифметических операций сложения, необходимых для нахождения
кратчайшего пути равно (N-1) и линейно растет с ростом N.
Для нахождения самого кратчайшего маршрута необходимо выполнить только сортировку расстояний от каждого города до остальных городов.
Два города с максимальным расстоянием между ними будут начальным и конечным на кратчайшем маршруте, остальные будут иметь наименьшие расстояния до соседних с ними городов вдоль всего маршрута.
Заключение:
Полученное решение было проверено путем сравнения результата расчета для матрицы расстояний, соответствующих Линейной Задаче Коммивояжера, полученного вручную, с решением, полученным после ввода данных в матрицу расстояний онлайн-калькулятора для решения задачи коммивояжера методом ветвей и границ.
Порядок проследования городов коммивояжером и длина кратчайшего пути совпали
для обоих вариантов расчета, что подтверждает правильность решения задачи.
Отредактировано Лукомор (2018-09-11 07:32:57)
