и вновь прога...

From

Vovanius Uryvaeff (2:5020/175.2)

To

Timoshkevich Denis

Date

2002-11-12T19:27:01Z

Area

RU.ALGORITHMS

From: "Vovanius Uryvaeff" <micro-s@vniiofi.ru>

Sun Nov 10 2002 23:46, Timoshkevich Denis wrote to Egor Tsygvintsev:

 ET>>      Хай, All

 ET>>   помогите, плиз, написать прогу (на пасе) по этой задаче. хохма во
 ET>> входных данных:

 ET>>   Дана карта местности, разбитая на участки разной проходимости,
 ET>> причем области разной проходимости это непересекающиеся многоугольники
 ET>> заданные своими вершинами. Необходимо проложить маршрут из точки А в
 ET>> точку В требующий минимального времени.

 TD> Строиш граф по следующиму принципу:
 TD> многоугольники это вершины, а ребра показывают смежность фигур.

Это ты что-то загнул... Твой вариант годится, когда есть ограниченное кол-во
тропинок, и в каждом многоугольнике есть неболее одного перекрестка.
На самом-же деле путь должен представлять собой ломаную, вершины которой
находятся на вершинах многоугольника, либо их границах.
А вот здесь заскоки начинаются. В виде классического графа врядли получится
путь представить.
Разве что использовать следующую модификацию волнового поиска кратчайшего
пути:
"Разбегаться" по окружности во все стороны сразу, увеличивая постоянно время,
то есть кождый раз получая область, которую можно достигнуть за время 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)