Та главное, шоб не таксидермия...

Ни в двух, ни в трех словах не получится никак:

- уже четыре слова! 

С этого места продолжу...
Уже после первой итерации возникают сами  собой четыре фрагмента маршрута, уже с готовыми кратчайшими маршрутами внутри фрагментов (напомню, мы эти участки выбирали по методу ближайшего соседа).

Теперь надо их сшить по концам так чтобы сумма длин каждой пары отрезков была минимальной.
Сразу отпадает вариант сшивки крест-накрест, поскольку он неизбежно даст самопересечения.
Остается вариант сшивать фрагменты по кругу, окончание одного фрагмента с одним из двух окончаний соседнего.
Поскольку у соседнего фрагмента два окончания, более короткий вариант сшивки даю зеленым цветом, более длинный - красным.

С двумя соединительными линиями сразу все понятно: участки 1 - 16  и  3 - 9 сомнения не вызывают.
их сразу включаем в маршрут, и убираем лишние красные линии.

Остается два варианта включения участка 0 - 14 - 12 - 8 в кольцо маршрута:
0 - 2  и  8 - 15,
дибо
0 - 15  и 2 - 8.
Тут уже надо считать суммы длин пар отрезков.
Первый вариант:
90,139 + 25,179 = 115,318
Второй вариант:
58,258 + 55,902 = 114,160
С небольшим перевесом, но второй вариант победил.

Хотя, почему, собственно, с небольшим перевесом?
Второй вариант, в качестве бонуса, имеет еще скрытую петлю между пунктами №8 и №15.
Её распутывание сократит общий маршрут еще на 4,322 км и мы вновь получим кратчайший маршрут в 448,150 км.
Первый вариант скрытых петель не имеет. Улучшать его некуда...

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

Отредактировано Лукомор (2019-08-28 06:19:24)

Ты даже не представляешь, насколько близко ты подошел к...

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

Отредактировано Лукомор (2019-08-28 09:33:09)

Я вернулся!

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

Я начал с того, что взял для рассмотрения условия несложной учебной задачи
на 17 пунктов с вот этого сайта

Координаты пунктов:

План местности:

Воспользовавшись онлайн-калькулятором с того же сайта,
я нашел решение методом "ближайшего соседа" для начала маршрута из каждого из 17 пунктов.
Для этих условий задачи длины кратчайших маршрутов оказались в диапазоне от 457.504 до 567.480 км,
в зависимости от выбранного стартового пункта.

Вот самый короткий из найденных маршрутов:

Его длина L = 457.504 км.

Далее я оптимизировал маршруты,
исключив пересечения, которые я также называю "явными петлями".
Новый диапазон кратчайших маршрутов от 455.413 до 532.008 км.

Вот новый самый короткий кратчайший маршрут:

Его длина L = 455.412 км.

На следующем этапе я ввел новое понятие "скрытая петля".

Распутав скрытые петли я получил 10 различных кратчайших маршрутов в диапазоне длин маршрутов
от 453.182 до 509.714 км.

Абсолютным рекордсменом стал маршрут длиной
L = 453.182 км, вот он:

После того, как все возможности метода "ближайшего соседа" были исчерпаны,
я применил собственный, только что изобретенный, метод "объединения пунктов",
и нашел маршрут длиною  L = 452.472 км., который стал новым рекордом для данных начальных условий.

Очевидным достоинством данного метода является то,
что он не зависит ни от выбора стартового пункта,
ни от порядка нумерации пунктов в целом.

Недостаток метода в том, что он не находит скрытые петли.

Распутывание скрытой петли на найденном маршруте дало новый рекордный результат с длиной маршрута L = 448.150 км.

С этой отправной точки мы и отправимся в дальнейший путь.

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

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

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

Для тех, кто не в теме, отсылаю на стр.14 этого топика, еще более точно,  к сообщению 411,
Еще точнее -

ТУДОЙ или СЮДОЙ!

С этого сообщения начинается изложение метода "объединения точек",
применительно как раз к этой задаче для 13 точек, которая получается там после первой итерации.
Заканчивается изложение метода на следующей странице, последнее сообщение имеет номер 434.
Дальнейшее всё: разумное, доброе и вечное, - накрыто девятым валом флуда...

У меня есть условия задачи с 17 пунктами, которую сюда приволок Шарпер когда-то с сайта МЭИ,
или с Хабра, и все свои теоретические построения я проверяю на ней, однообразия для.

На первой итерации я для каждого из 17 пунктов нахожу ближайший к нему пункт.
Сверху это выглядит, как будто 17 коммивояжеров стартуют одновременно из 17 пунктов, руководствуясь старым добрым методом "ближайшего соседа"

При этом некоторые коммивояжеры двигаются навстречу друг другу. (зеленые линии на плане).
У нас таких взаимно ближайших точек нашлось - четыре пары: 7 и 16, 2 и 10, 8 и 12, 5 и 6.
Коммивояжеры вышедшие из этих пунктов, при условии равных скоростей, встретятся посредине, между соответствующими пунктами.
А остальные девять коммивояжеров не встретятся (красные стрелки), поскольку ближайшие пункты к их исходным пунктам, не соответствуют друг другу.

Теперь я каждую из четырех пар пунктов заменяю пунктами, где пара коммивояжеров встретилась, я обозначил их, соответственно, -
А, B, C, D.

Поэтому (лукаш !) у нас больше нет пунктов 7 и 16, 2 и 10, 8 и 12, 5 и 6,
а есть лишь 13 пунктов: 0, 1, 3, 4, 9, 11, 13, 14, 15, А, B, C, D.