поиск пути

[Mfcer__]

Интересует любая информация о алгоритме A* (А звездочка) поиска пути, исходники, реализации, желательно на С/C++.
Вообще плюсы или минусы этого алгоритма, где лучше применять.

т.к. форума алгоритмы не нашел пишу в общий

[Serega]

Нашел описание

[Mfcer__]

если кто - нибудь в курсе можете объяснить за чем нужны closed и open списки, как оин используются

достал псевдно код
помогите в нем разобраться а то совсем запутался

Код:

Listing 3.


priorityqueue Open
list Closed


AStarSearch
 // что означает s.g и s.h ???
   s.g = 0  // s is the start node
   s.h = GoalDistEstimate) s :
   s.f = s.g + s.h
   s.parent = null
   push s on Open
   while Open is not empty
      pop node n from Open  // n has the lowest f
      if n is a goal node 
         construct path 
         return success
      for each successor n' of n
         newg = n.g + cost)n,n':
         if n' is in Open or Closed,
          and n'.g <= newg
           skip
         n'.parent = n
         n'.g = newg
         n'.h = GoalDistEstimate) n' :
         n'.f = n'.g + n'.h
         if n' is in Closed
            remove it from Closed
         if n' is not yet in Open
            push n' on Open
      push n onto Closed
   return failure // if no path found 

 

[Алексей++]

// что означает s.g и s.h

это скорее всего структура вроде (насчёт типов членов не уверен)

struct F
{
   int f;
   int g;
   int h;
   int parent;
};


насчёт работы алгоритма - если без оценки ценности узлов, то поиск пути сводится к:

N=0 (это номер шага);
1) имеется узел-начало и узел конец (к1 и к2);
2) в стек помещается к1
3) из стека извлекается узел кi
4) проверяется возможность сделать шаг длиной в один узел от узла кi
5) все соседние узлы, куда можно шагнуть, помечаются числом N и ,помещаются в стек. Если один из узлов это к2, то нашли. Конец.
6) N=N+1. Идём в п.3)

в итоге, пометки узлов таковы, что если, начиная с узла к2, можно найти цепочку пути по всё уменьшающимся значениям меток - к2,9,8,7,6...1,к1

[Serega]

если кто - нибудь в курсе можете объяснить за чем нужны closed и open списки, как оин используются

В волновом алгоритме узлы делятся на 3 группы:
1. узлы в которых мы еще не бывали (белые)
2. узлы в которых уже побывали но обошли не всех потомков (серые)
3. узлы все потомки которых уже обошли - обработанные (черные)

Для работы потребуется очередь:
 - очередь серых узлов (очередь обработки)

Принцип работы алгоритма:

Код:

1. Начало{
 - заходим в белый узел 
 - помечаем его серым и добавляем в очередь

2. Основной цикл )пока очередь не пуста:{
 - выбираем узел из очереди )если это целевой узел выходим из цикла:
 - помечаем всех белых потомков серым, указываем что предок - текущий узел, добавляем в очередь
 - метим узел черным

3. Результат{
 - получили список предшествования по которому строим кратчайший путь )целевой узел знает своего предка и т.д. до стартового узла:

Так ищется кратчайший путь в невзвешенном графе

Для взвешенного графа алгоритм нужно немного изменить, появляется стоимость пути и меняется основной цикл:

Код:

 - выбираем узел из очереди )если это целевой узел выходим из цикла:
 - обходим всех потомков )включая серые и черные:{
     - белые метим серым, предок - текущий узел, в очередь
     - для серых и черных если стоимость пути из текущего узла меньше{ предок - текущий узел
 - метим узел черным

Алгоритм А* отличается тем, что для выбора порядка обхода вершин используется эвристика и стоимость считается как сумма пройденного пути и эвристики.
Для этого в качестве очереди обрабатываемых узлов используется очередь с приоритетами и немного меняется основной цикл алгоритма:

Код:

 - выбираем узел из очереди )если это целевой узел выходим из цикла:
 - обходим всех потомков )включая серые и черные:{
     - белые метим серым, предок - текущий узел, в очередь
     - для серых если стоимость пути из текущего узла меньше{ предок - текущий узел
     - для черных если стоимость пути из текущего узла меньше{ предок - текущий узел, 
       метим серым и в очередь )если эвристика зависит от того, как мы в этот узел пришли:
 - метим узел черным

В твоем примере Open это очередь серых узлов, Closed - очередь черных

[Mfcer__]

Спасибо всем огромное  

[Mfcer__]

 - обходим всех потомков (включая серые и черные):
     - белые метим серым, предок - текущий узел, в очередь
     - для серых если стоимость пути из текущего узла меньше: предок - текущий узел
     - для черных если стоимость пути из текущего узла меньше: предок - текущий узел,
       метим серым и в очередь (если эвристика зависит от того, как мы в этот узел пришли)
 - метим узел черным

Возникли вопросы:
Как расчитать стоимость пути?
И вообще что такое эвристика и как она в данном случае используется?

[Serega]

Эвристика это приближенная оценка, в данном случае оценка оставшегося пути
Стоимость пройденного пути складывается из стоимости переходов между узлами
Я же дал ссылку, там есть и описание возможных эвристик