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

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

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

Здравствуйте, 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
Будут конкретные вопросы, задавай.
Удачи!

M>подскажите пожайлуста чем отличается алгоритм A* от Дейкстры...
M>второй день ищу не могу найти описание A*
M>причем на руках Корман, Седжвик и ещё Ахо....
M>может у него есть ещё какое-то название...
Можно посмотреть вот такую статью:
Goldberg, Harrelson — Computing the Shortest Path, A-star Search Meets Graph Theory
Думаю, она есть в открытом доступе, если нет, могу прислать.

В алгоритме A* применяется поиск кратчайших путей относительно не исходной функции длин, а полученной в результате потенциального преобразования. Двойственно-допустимые потенциалы, которые при этом используются, выбираются пользователем из некоторых эвристических соображений (как определенным образом согласованные оценки расстояния).

Здравствуйте, m01ska, Вы писали:

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

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

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

Если кратко и по русски , то в Дейкстре все перебираемые узлы графа равноценны и перебераются волной. А в А Стар выбирается наиболее МНОГООБЕЩАЮЩИЙ узел ( по эвристике , например самый близкий к финальной точке).