Вариант задачи коммивояжера

Devid

Точки расположены на плоскости и разбиты на пары. Нужно, как обычно, найти короткий путь, проходящий по одному разу через все точки. Дополнительное условие, что точки из одной пары должны проходиться подряд (в произвольном порядке).
Ищется не слишком сложный алгоритм со временем работы не больше O(n^3) (если он детерминированный). Быстрое гугление показывает, что рулит симуляция отжига, но мб кто-то знает решение получше?

Dimon89

А если в лоб - слить твои пары точек в одну в их центре масс, дальше построить путь как обычно, потом развернуть пары обратно?

Devid

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