Быстрый TSP на плоскости для маленького числа точек

[iposov]

Задача: на плоскости дано несколько точек, требуется построить минимальную по длине ломаную (незамкнутую), проходящую через все точки.
Как решить это эффективно? Хочется, чтобы программа всегда укладывалась в 30-40 секунд для 20 точек

[stopa85]

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

Если да, то Вам нужно посмотреть метод Литтла. Думаю, что для 20 точек он управиться в 30 секунд. В крайнем случае, можно взять его текущую оценку сверху и удалить самое длинное ребро.

Остается выяснить. Прав ли я.

[North]

iposov писал(а):

Задача: на плоскости дано несколько точек, требуется построить минимальную по длине ломаную (незамкнутую), проходящую через все точки.
Как решить это эффективно? Хочется, чтобы программа всегда укладывалась в 30-40 секунд для 20 точек

Любые существующие алгоритмы (кроме прямого перебора конечно ) - будут решать такую задачу на много быстрее чем за 30-40 сек. 20 точек - это совсем маленькая размерность - не более десятых долей секунды.

Существует много алгоритмов решения этой задачи - можно выбрать наиболее удобный и подходящий для вас - можно начать читать с этой статьи - обратите внимание на метод "ветвей и границ".