|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vovanius Uryvaeff 2:5020/175.2 12 Nov 2002 20:27:01
To : Timoshkevich Denis
Subject : и вновь прога...
--------------------------------------------------------------------------------
Sun Nov 10 2002 23:46, Timoshkevich Denis wrote to Egor Tsygvintsev:
ET>> Хай, All
ET>> помогите, плиз, написать прогу (на пасе) по этой задаче. хохма во
ET>> входных данных:
ET>> Дана карта местности, разбитая на участки разной проходимости,
ET>> причем области разной проходимости это непересекающиеся многоугольники
ET>> заданные своими вершинами. Hеобходимо проложить маршрут из точки А в
ET>> точку В требующий минимального времени.
TD> Строиш граф по следующиму принципу:
TD> многоугольники это вершины, а ребра показывают смежность фигур.
Это ты что-то загнул... Твой вариант годится, когда есть ограниченное кол-во
тропинок, и в каждом многоугольнике есть неболее одного перекрестка.
Hа самом-же деле путь должен представлять собой ломаную, вершины которой
находятся на вершинах многоугольника, либо их границах.
А вот здесь заскоки начинаются. В виде классического графа врядли получится
путь представить.
Разве что использовать следующую модификацию волнового поиска кратчайшего
пути:
"Разбегаться" по окружности во все стороны сразу, увеличивая постоянно время,
то есть кождый раз получая область, которую можно достигнуть за время t+dt.
Область можно представить ограниченной дугами эллипсов. dt можно брать равной
min(tc), где tc - минимальное время достижения любой точки, не покрытой на
данный момент областью достигнутого, или точки касания.
Либо извращаться с вариантом графа, в котором вершины - вершины
многоугольников, где вес каждого звена также придется определять нетривиально,
учитывая изменения маршрута на пересечениях со сторонами многоугольников.
Send Email to vovanius2000<yxo>mail. ru
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
