|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Ivanov 2:5020/400 24 May 2002 02:07:58
To : Sveta Ivanova
Subject : Re: Провести ломаную через точки
--------------------------------------------------------------------------------
> А не встречалась ли кому такая задача?
> Задано n точек на плоскости. Требуется соединить их ломаной так, чтобы
> минимизировать длину максимального из отрезков ломаной. Ломаная должна
быть
> незамкнутой (т.е. проще говоря, путь), начинаться и заканчиваться может в
любой
> точке. Самопересечения допускаются. Хотелось бы не перебор всех
> перестановок,
> а полиномиальный алгоритм (если таковой существует). Может, кто-то
сталкивался
> с чем-то подобным?
>
> Всегo наилучшегo. Sveta Ivanova.
соедини все точки между собой и удаляй последовательно отрезки с
максимальной длиной до тех пор пока набор точек остается связанным. первый
отрезок удаление которого нарушает связанность и будет минимальным
максимальным отрезком. после этого удаление лишних отрезков можно вести
произвольным способом, поскольку оно не будет влиять на достигнутый уже
минимум.
Cheers,
Serge Ivanov
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
