Дейкстра & A*
От: m01ska  
Дата: 26.07.05 07:59
Оценка:
Уважаемые...

подскажите пожайлуста чем отличается алгоритм A* от Дейкстры...
второй день ищу не могу найти описание A*
причем на руках Корман, Седжвик и ещё Ахо....
может у него есть ещё какое-то название...

Заранее спасибо!
Re: Дейкстра & A*
От: FreshMeat Россия http://www.rsdn.org
Дата: 26.07.05 08:13
Оценка:
Здравствуйте, m01ska, Вы писали:

M>подскажите пожайлуста чем отличается алгоритм A* от Дейкстры...

M>второй день ищу не могу найти описание A*
M>причем на руках Корман, Седжвик и ещё Ахо....
M>может у него есть ещё какое-то название...

Набираешь в гугле поиск пути "A*" и получаешь по первым трем ссылкам отличный результат:
http://www.policyalmanac.org/games/aStarTutorial_rus.htm
http://pmg.org.ru/ai/
http://pmg.org.ru/ai/stout.htm

На рсдн его уже несколько раз обсуждали http://gzip.rsdn.ru/search/?q=%22A*%22+%EF%F3%F2%FC&mode=rank&group=15
Будут конкретные вопросы, задавай.
Удачи!
Хорошо там, где мы есть! :)
Re: Дейкстра & A*
От: Mab Россия http://shade.msu.ru/~mab
Дата: 26.07.05 08:16
Оценка:
M>подскажите пожайлуста чем отличается алгоритм A* от Дейкстры...
M>второй день ищу не могу найти описание A*
M>причем на руках Корман, Седжвик и ещё Ахо....
M>может у него есть ещё какое-то название...
Можно посмотреть вот такую статью:
Goldberg, Harrelson — Computing the Shortest Path, A-star Search Meets Graph Theory
Думаю, она есть в открытом доступе, если нет, могу прислать.

В алгоритме A* применяется поиск кратчайших путей относительно не исходной функции длин, а полученной в результате потенциального преобразования. Двойственно-допустимые потенциалы, которые при этом используются, выбираются пользователем из некоторых эвристических соображений (как определенным образом согласованные оценки расстояния).
Re: Дейкстра & A*
От: minorlogic Украина  
Дата: 26.07.05 18:20
Оценка:
Здравствуйте, m01ska, Вы писали:

M>Уважаемые...


M>подскажите пожайлуста чем отличается алгоритм A* от Дейкстры...

M>второй день ищу не могу найти описание A*
M>причем на руках Корман, Седжвик и ещё Ахо....
M>может у него есть ещё какое-то название...

M>Заранее спасибо!


Если кратко и по русски , то в Дейкстре все перебираемые узлы графа равноценны и перебераются волной. А в А Стар выбирается наиболее МНОГООБЕЩАЮЩИЙ узел ( по эвристике , например самый близкий к финальной точке).
Ищу работу, 3D, SLAM, computer graphics/vision.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.