Показать сообщение отдельно
  (#1 (permalink)) Старый
tentul tentul вне форума
Member
 
Сообщений: 124
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2005
По умолчанию Детали А*алгоритма - 19.10.2005, 00:48

Опять я. :)
Вот здесь http://www.hardforum.ru/t53222 я увидел листинг кода. Из теории знаю, что оценочная в А*-алгоритме состоит из суммы g(i)+h(i).
g(i) - стоимость пройденого пути, можно принять как глубину вершины в графе. h(i) - сложнее подобрать, оценочная функция пути от текущего состояния к цели (не стоимость).
В лекции написано, что при h=0 А*-алгоритм вырождается в поиск в ширину.
Я хочу понять как действует этот алгоритм. Мы начинаем рассматривать текущий фронт, и из каждой вершины пытаемся перейти на 1 уровень вглубь, новые вершины анализируем, и по оценочной функции выбираем те, что лучше (а не все, как в поиске в ширину). Так получим одну или несколько вершин нового фронта. И так продвигаемся дальше. Но если действуя так мы попадем в тупик? Например оценочная функция была не совсем удачной. Откатит ли Пролог назад, и начнем ли мы продвижение вглубь опять с самого последнего разветвления, где мы выбрали переход, который "лучше" по f(i) , но привел в тупик?

Я привел картинку, где есть несколько тупиков, и Пролог будет несколько раз откатываться назад. Я все верно понял в алгоритме?

http://webfile.ru/581394 - 77 kb
Ответить с цитированием
Ads