|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitrii Potapov 2:5035/43.27 20 May 2002 23:18:26
To : Sveta Ivanova
Subject : Провести ломаную через точки
--------------------------------------------------------------------------------
Хой, Sveta!
_Суб Май 18 2002_ 22:42, Sveta Ivanova сообщал All примерно следуЮщее:
SI> А не встречалась ли кому такая задача?
SI> Задано n точек на плоскости. Требуется соединить их ломаной так,
SI> чтобы
SI> минимизировать длину максимального из отрезков ломаной. Ломаная должна
SI> быть незамкнутой (т.е. проще говоря, путь), начинаться и заканчиваться
SI> может в любой точке. Самопересечения допускаются. Хотелось бы не
SI> перебор всех перестановок, а полиномиальный алгоритм (если таковой
SI> существует). Может, кто-то сталкивался с чем-то подобным?
Сpазy навскидкy такая идея: описываем около точек многоyгольник, выбиpаем любyю
гpаничнyю. А затем от нее до ближайшей, от той снова до ближайшей и тп.
Hе yвеpен, что пpавильно, но, дyмаю, что можно pазвить.
[The OFFSPRING]
Играет: Тихий шелест куллера...
... _/Demon Is Alive Forever!!! e-mail:demon@zadnica.net/_
--- ---Satyricon 6.66---
* Origin: От Парижа до Hаходки с водкой лучше, чем без водки! (2:5035/43.27)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Провести ломаную через точки 
