Цитата:
Сообщение от квит
его длина маршрута - 99 условных километров против 118 у жадного алгоритма
|
причем этот результат можно еще улучшить - если развязать пересечение ребер между 2-12 и 13-0
это делает алгоритм 2-Opt
https://translated.turbopages.org/pr...org/wiki/2-opt
его смысл - развязать пересечение двух ребер, доказано, что такая перестановка всегда улучшает длину маршрута
т.е. из конфигурации
--A..B--
.. \/
.. /\
--C..D--
переходим в конфигурацию
--A----B--
--C----D--