|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexandr Otroshchenko 2:5071/45.515 25 May 2002 17:53:08
To : Sveta Ivanova
Subject : Re: Провести ломаную через точки
--------------------------------------------------------------------------------
ЙДНННННННННДДДДДД ДДДДД ДДД ДД Д
і Привет, /*Sveta!*/
ИДНННННННННДДДДДД ДДДДД ДДД ДД Д
СИжу почту читаю, а тут Sveta Ivanova пишет Serge Ivanov по поводу Провести
ломаную через точки.
>>> Задано n точек на плоскости. Требуется соединить их ломаной так,
>>> чтобы минимизировать длину максимального из отрезков ломаной.
>>> Ломаная должна быть незамкнутой (т.е. проще говоря, путь)
SI>> соедини все точки между собой и удаляй последовательно отрезки с
SI>> максимальной длиной до тех пор пока набор точек остается
SI>> связанным.
SI> Hо ведь связность графа не гарантирует, что это будет путь? В
SI> результате мы можем получить произвольное дерево, а мне надо именно
SI> простой путь.
Так тебе нужен именно путь? То есть - ломаная без ветвлений? Тогда задача
совсем проста:
1. задаёшься исходной точкой
2. делаешь её текущей.
3. Перебором находишь ближайшую из оставшихся.
4. найденую делаешь текущей.
5. повторяешь пп3-5.
і Свидимся, Sveta!
і 25 мая 2002, -=Al=-
Д ДД ДДД ДДДДД ДДДДДННННННННДКДННННННННДДДДД ДДДДД ДДД ДД
...Metallica -Garage, inc- Die, Die My Darling, *Мыллер отдыхает*
--- [VC++ ObjectProgramming][BodyBuilding][BasketBall][Metallica][Queen][БрГТУ]
* Origin: Александр Фёдорович Отрощенко aka -=Al=- (2:5071/45.515)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
