Скачать: CL | DM;

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

← →
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]

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

---

← →
TUser ©   (2004-08-19 14:08) [4]

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

---

← →
antonn ©   (2004-08-19 17:42) [5]

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

---

Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.46 MB
Время: 0.022 c