[Mozgunov]

Добрый день! Прошу поделиться идеями по решению следующей задачи (желательно на Autolisp). Или хотя бы алгоритм. Спасибо заранее!

Условия:
1-имеется n точек (3-50)
2-имеется заданная длина полилинии которая должна соединить все n точек

Задача:
Требуется соединить точки таким образом, чтобы длина построенной полилинии была максимально приближена к заданной длине при этом чтобы она обязательно проходила через все точки.
P.S. Полилиния не должна проходить через каждую точку больше одного раза.

[Дима_]

Ищи по фразе "задача комивояжора", все отличие с Вашей задачей - у Вас заданый путь (спидометр подгоняете?), а там кротчайший.

[Mozgunov]

Да Дима_ вы в точку. Подгоняем спидометр) Спасибо! Буду искать. Вот как раз с отличием я думаю будут большие проблемы)

[gomer]

В задаче про комивояжера ищется минимальная длина, а это извращение какое-то
[IMG]http://img233.**********.us/img233/5277/tsp2xd1.jpg[/IMG]

[Mozgunov]

gomer, Может и извращение, но у него есть смысл. Когда-нибудь появится алгоритм решения этой задачи.

[Кулик Алексей aka kpblc]

Отлично. Есть 4 точки с координатами 0,0,0; 1,1,0; 1,0,0; 0,1,0. Задача - построить путь, длина которого наиболее близка к 3.9. Второй вариант - к 3.5. Третий вариант - к 4.6.
И доказать, что этот вариант единственно возможный.

[Mozgunov]

Кулик Алексей aka kpblc, Если в условия задачи добавить начальную и конечную точку, то эта проблема пропадает?

[Кулик Алексей aka kpblc]

А на этот вопрос надо отвечать не мне

[Mozgunov]

Пропадет. К условию задачи добавляется начальная и конечная точка. Алгоритм решения такой задачи тоже будет неизвестен? Я так понял что простым перебором, даже если будет до 20-ти точек её никогда не решить? Можете ответить можно ли решить такую задачу с поправкой о начальной и конечной точке?