Как таковой публикации нет, только на форумах algolist-а трепался, там ни кому не нужно было.
Идея улучшения пути понятна из следующих рисунков.
Одновременная перестановка в двух парах точек:
Вложение:
2.png [ 19.21 КБ | Просмотров: 7047 ]
Одновременная перестановка в трёх парах точек:
Вложение:
3.png [ 22.76 КБ | Просмотров: 7047 ]
Одновременная перестановка в четырёх парах точек:
Вложение:
4.png [ 25.67 КБ | Просмотров: 7047 ]
Первый вариант пути вычисляется как угодно, например, жадным алгоритмом. Потом пытаемся уменьшить длину пути перебирая всевозможные перестановки в двух парах точек, затем пробуем все трёхпарные перестановки, потом все четырёхпарные, и так далее.
-------
А на счёт точного алгоритма для 18 точек, так там просто на каждом шаге построения пути надо оборачиваться и смотреть назад. Если окажется, что последние N точек можно было пройти в какой-то иной последовательности и путь стал бы короче, значит дальше этот вариант пути не рассматриваем так как он заведомо не оптимальный. Чем глубже назад смотреть, т.е. чем больше N тем лучше, однако такой просмотр стоит O(N!), значит слишком глубоко смотреть назад тоже нельзя. Эмпирически установил, что овчинка стоит выделки при N<=7. Написал кодогенератор, который составил код проверки для 7! = 5040 вариантов + код для 6!, 5!, 4!, 3! и 2 вариантов которые нужны в самом начале построения варианта пути когда количество точек ещё меньше семи. Ну вот и получилось, что точное решение для 18 точек вычислялось примерно за три минуты (для 19 точек -- в 19 раз дольше, т.е. примерно за час, а для 20 точек значит примерно за сутки).