> -- Сергей Губанов писал(а):
> Первый вариант пути вычисляется как угодно, например, жадным алгоритмом. Потом пытаемся уменьшить длину пути перебирая всевозможные перестановки в двух парах точек, затем пробуем все трёхпарные перестановки, потом все четырёхпарные, и так далее.

На практике получалось что-то вроде следующего. После двухпарных распутываний путь, например, 70 километров, после трёхпарных, например, 65 км, после четырёхпарных, например, 64, а после пятипарных - 63.8 км. То есть пятипарное распутывание улучшало путь метров на двести, но с такой точностью общей длины пути мы и карту-то задать не могли. Так что реально прерывать алгоритм можно было уже после трёхпарных распутываний.