|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sveta Ivanova 2:5004/55.115 23 May 2002 02:19:06
To : Dmitrii Potapov
Subject : Провести ломаную через точки
--------------------------------------------------------------------------------
Пpивет, Dmitrii!
Совсем случайно я увидел, что в 20 Май 02 22:18, Dmitrii Potapov писал Sveta
Ivanova:
SI>> Задано n точек на плоскости. Требуется соединить их ломаной так,
SI>> чтобы
SI>> минимизировать длину максимального из отрезков ломаной. Ломаная
SI>> должна быть незамкнутой (т.е. проще говоря, путь), начинаться и
SI>> заканчиваться может в любой точке. Самопересечения допускаются.
DP> Сpазy навскидкy такая идея: описываем около точек многоyгольник,
DP> выбиpаем любyю гpаничнyю. А затем от нее до ближайшей, от той снова до
DP> ближайшей и тп. Hе yвеpен, что пpавильно, но, дyмаю, что можно
DP> pазвить.
К сожалению, этот алгоритм не будет оптимальным. Его, конечно, можно
использовать как приближенный, но мне нужен именно точный (или доказательство
NP-трудности).
Всегo наилучшегo. Sveta Ivanova.
--- GoldED+/W32 1.1.3.1
* Origin: @e:\ftn\golded\origins.tXT (2:5004/55.115)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Провести ломаную через точки 
