Крайняя итерация заключалась в том, что отрезок MN мы заменили медианным пунктом P,
который мы соединили с пунктами  K и L.

Высадив бабу с воза, и развернув кобылу на обратный путь, мы должны проделать следующее:
восстановить отрезок MN, исключив пункт Р,
и
соединить концы восстановленного отрезка - пункты М и N - с пунктами К и L.

В отличие от отдельного пункта, который можно соединить с двумя пунктами единственным образом,
отрезок с двумя теми же пунктами можно соединить "либо так, либо наоборот".

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

Теперь нам нужно перепрыгнуть от четырех пунктов к восьми.
Мы восстанавливаем отрезки:
№3 - Е (исключив из рассмотрения пункт К)
№9 - B (исключив пункт L)
№0 - F (исключив пункт M)
№1 - J (исключив пункт N)

Эти четыре отрезка надо соединить теперь так, чтобы получился замкнутый маршрут минимальной длины.
Чтобы не делать полный перебор всех вариантов, я разбиваю процедуру на два этапа.
На предварительном этапе, благо его можно проводить для каждого из четырех новых отрезков по отдельности, этот выбор никак не влияет на соседние отрезки,
я выбираю отрезок (например №9 - В) и сравниваю, опять же, два варианта суммы расстояний от его концов до старых пунктов, K и  M, как будто трех других новых отрезков еще нет.
Так я поступаю независимо с каждым новым отрезком, полагая на время, что это единственный новый отрезок, а остальные все точкипункты из прошлой итерации.

Выясняется (я всё посчитал), что:
Сумма длин отрезков (№3 - L)  и (E - N)
меньше чем (№3 - N) и (E - L).
Сумма длин отрезков (№9 - K)  и (B - M)
меньше чем (№9 - M) и (B - K).
Сумма длин отрезков (№0 - N)  и (F - L)
меньше чем (№0 - L) и (F - N).
Сумма длин отрезков (№1 - K)  и (J - M)
меньше чем (№1 - M) и (J - K).

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

Для этого мы попарно соединяем пункты, из которых более короткие пути ведут во встречных направлениях.
Мы выяснили на предварительном этапе, что из пункта №3 соединительная линия пойдет в сторону пункта L,
то -есть, теперь уже в направлении пары, (№9 - В) ,
а от точки №9 - в направлении пункта К, то-есть теперь уже в направлении пары (№3 - Е).
Из этих четырех пунктов совпадают только два №3 и №9.
Вот их мы и соединим окончательно.
Аналогично, из пункта Е будем двигаться в направлении пунктов №1 и J, из пункта №1 в направлении №3 или Е.
Соединяем, соответственно, совпавшие  пункты №1 и Е.
Точно также совпадут пункты B   и  F,  №0 и J.
Окончательная картинка получившегося кратчайшего маршрута через 8 пунктов такова:

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

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

- Знаете ли вы, кто был главным противником антиалкогольной компании,
объявленной Горбачевым?
- Пьяницы?
- Некрасивые женщины!

ЗЫ: Карлсон улетел, но угрожал вернуться. 
ЗЗЫ: Цифру назови - длину кратчайшего маршрута для этой задачи...

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

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

Если же до конца понедельника не объявлюсь:

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

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

!. Он никогда не дает, в результате его применения,
маршрутов с пересечением отрезков (явных петель),
которые гарантированно отсекаются на этапе разделения пунктов.

2. Он не зависит от выбора начального пункта,
поскольку на первой итерации этапа объединения пунктов
выбираются первые участки маршрута сразу от всех пунктов одновременно.

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

Не факт!
Мне вот пришла такая мысль в сознание:
Возможно для решения задачи коммивояжера за полиномиальное время нужно пользоваться не одним каким-то методом, а гибко и плавно переходить с одного метода на другой совершенствуя решение, подобно тому, как сложное изделие не изготавливается при помощи одной лишь кувалды, а требует соответствующего инструментария и.т.п.

Вот вечер понедельника, и я готов продолжить отчет о своих изысканных изысканиях в причудливом и загадочном мире коммивояжеров.

Короче,
"Я тут порисую... немножко!"
(с) Лукомор