К этому моменту я самоотверженно построил маршруты от каждого из 17 пунктов, определенных условием задачи.
Затем я распутал явные петли, которые были на 10 из 17 построенных маршрутов.

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

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

Тут же, для сравнения, новая таблица с маршрутами после распутывания всех явных петель.

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

На данный момент имеем 11 уникальных маршрутов и никаких идей, что с ними делать дальше.

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

Нет.
А зачем отделять?!
Все равно манку солить, когда варишь...

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

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

Но внезапно оказалось, что когда подвижная точка пересекает границу периметра,
то это не приводит сразу к замене одного кратчайшего маршрута на другой.
Кратчайший маршрут остается прежним и при дальнейшем погружении подвижной точки вглубь многоугольника,
до достижения некоторого критического угла, после которого уже появляется другой кратчайший маршрут.

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

Рассматривая один из маршрутов с явной петлей, именно вот этот :

я озадачился вопросом:
"А что произойдет, если точку Р я начну двигать вниз?"
Когда точка Р окажется на пересекающей маршрут прямой,

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

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

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

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

Поняв, что скрытые петли реально существуют,
я далее нашел способ их находить на маршруте,
и алгоритм их распутывания.

Поиск скрытых петель я продемонстрирую на простом примере маршрута через 6 пунктов.

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

Там где синяя или красная линия пересекли черную линию (рассматриваемый маршрут)
между двумя пунктами, - это и есть скрытая петля.
У нас получилось две скрытых петли:
Красная линия CD  пересекла участок маршрута     AF,
и синяя линия BF пересекла участок маршрута        СЕ.

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

Найдя скрытые петли - распутаем их.
Как и в случае явных петель - просто исключим отрезки на которых получились пересечения:

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

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

Скрытых петель нет. Всё ОК!

Отредактировано Лукомор (2019-08-13 11:54:06)

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

Где вы берете эту гадость?