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