Кратчайший путь от т.А к т.Б

← →
mr_black © (2004-08-19 12:37) [0]

Уважаемый All!!!
Хелп плзззз!!
Бьюсь над прогой уже месяц а кроме тупого подхода не чё не могу придумать!!! :-(
Нужен алгоритм или код проги!
Задача следующая: Нарисовать кратчайший путь между точкой А и точкой Б, обходя препятствия (угол обхода прямой)! Эта задача решена в таких прогах как AutoCAD, Electric WorkBench, PCAD. В общем видишь как они работают а кода та нету да и алгоритма тоже!
Так что народ помогите ПЛЗ!!!
;-(

← →
wicked © (2004-08-19 12:45) [1]

http://algolist.manual.ru - там есть если и не такое, то подобное...

← →
TUser © (2004-08-19 13:43) [2]

Я бы решал динамически. Сначала находим путь из А во все точки, с которыми она рядом. Потом берем следующий слой точек, для каждой из них находим кратчайший путь (путь до найденных ранее точек + 1 - миниманое из этого). И так пока не дойдем до точки Б.

В принципе, это называется алгоритм Дейкстры - см. Ахо, Хопкрофт, Ульман. Структуры данных и алгоритмы. Там это описано в главе про графы.

← →
WondeRu © (2004-08-19 13:56) [3]

Я реализовывал такую муть на Волновом алгоритме! Яндекс поможет!)

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

А вот и примерчик:
http://delphi.mtu-net.ru/zip/path.zip

Кратчайший путь от т.А к т.Б Найти похожие ветки