Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: поиск пути  (Прочитано 9132 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Mfcer__
Команда клуба

ru
Offline Offline

« : 09-09-2004 23:18 » 

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

т.к. форума алгоритмы не нашел пишу в общий
Записан
Serega
Гость
« Ответ #1 : 10-09-2004 06:50 » 

Нашел описание
Записан
Mfcer__
Команда клуба

ru
Offline Offline

« Ответ #2 : 10-09-2004 23:09 » 

если кто - нибудь в курсе можете объяснить за чем нужны 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

 
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #3 : 11-09-2004 06:02 » 

Цитата

// что означает 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
Гость
« Ответ #4 : 11-09-2004 07:29 » 

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

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

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

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

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

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


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

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

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

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

ru
Offline Offline

« Ответ #5 : 11-09-2004 22:43 » 

Спасибо всем огромное  Ага
Записан
Mfcer__
Команда клуба

ru
Offline Offline

« Ответ #6 : 13-09-2004 00:02 » 

Цитата

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

Возникли вопросы:
Как расчитать стоимость пути?
И вообще что такое эвристика и как она в данном случае используется?
Записан
Serega
Гость
« Ответ #7 : 13-09-2004 10:16 » new

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

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines