Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Prolog
Перезагрузить страницу Детали А*алгоритма
Ответ
 
Опции темы Опции просмотра
  (#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
Ответить с цитированием
  (#2 (permalink)) Старый
tentul tentul вне форума
Member
 
Сообщений: 124
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2005
По умолчанию 19.10.2005, 01:34

Это код, который опубликован по ссылке за прошлый год

Код:
aastar([[_,G,Node|Path]|_],[Node|Path],G):-
   final_state(Node).
aastar ([Path|Paths],Sol,G):-
   findall(NewPath,select_next_node(Path,NewPath),NewPaths),
   insert_each_path(NewPaths,Paths,Paths2),
   aastar(Paths2,Sol,G).

select_next_node([F,G,Node|Path],[F1,G1,Node1,F,G,Node|Path]):-
   succesor(Node,Node1),
   cost(Node,Node1,C),
   G1=G+C,
   heuristic(Node1,E),
   F1=G1+E,
   not(member(Node1,[Node|Path])).

select_next_node([E,Node|Path],[E1,Node1,E,Node|Path]):-
   succesor(Node,Node1),
   heuristic(Node1,E1),
   not(member(Node1,[Node|Path])).

insert_each_path([],Paths,Paths).
insert_each_path([Path|Paths],Paths2,Paths3):-
   inserare_1_Path(Path,Paths2,Paths4),
   insert_each_path(Paths,Paths4,Paths3).

insert_1_path(Path,[],[Path]).
insert_1_path([E|Path],[[E2|Path2]|Paths],[[E|Path],[E2|Path2]|Paths2]):-
   E<=E2.
insert_1_path([E|Path],[[E2|Path2]|Paths],[[E2|Path2]|Paths2]):-
   E>E2,
   insert_1_path([E|Path],Paths,Paths2).
У меня несколько вопросов по коду. Объясните пожалуйста.

aastar - главный предикат. G - мы тащим на протяжении всей рекурсии (глубина пути-ответа), только чтобы вывести его в самом окончании вместе с ответом? Эта переменная получает значение ведь только в самом конце рекурсии.

Код:
aastar([[_,G,Node|Path]|_],[Node|Path],G):-
при формировании пути-ответа мы добавляем ветвь Node без 'F,G'
Но путь у нас состоит из структур F,G,Node - [...F1,G1,Node1,F2,G2,Node2...] - и в ответе эти ненужные оценки F,G у нас будут отсутствовать только для последнего хода, а для остальных состояний останется мусор . Хотя в принципе можно сделать еще предикат сверху, который из этого ответа-списка будет вытягивать каждый третий элемент.

Дальше идут предикаты select_next_node
Причем первое объявление для структуры пути F,G,Node, а второй для E,Node - уже странность.

В aastar мы передаем список путей. Для первого из них (по идее самого оптимального) мы findall'ом собираем все возможные переходы, и дополняем этот "первый самый оптимальный" путь. Получаем список путей NewPaths.

Потом идет таинственный предикат insert_each_path. Он как-то по аргументу F из структуры F,G,Node вставляет этот путь в список путей Paths. (По одному выполняет вставку предикат insert_1_path )
Он рекурсивно "копирует" второй аргумент (список путей) в третий. Но если оценка 'E' первого аргумента (просто 1 путь) <= оценки очередного пути из второго аргумента, то мы прекращаем рекурсию и добавляем этот первый аргумент-путь к третьему аргументу.
У меня это не укладывается в голове, просто не получается представить
Вот имеет такие аргументы
Код:
insert_1_path([x], [[a],[b],[c],[d]], List)
Пусть оценка последнего состояния в списке [x] меньше только оценки списка [c], и больше чем оценка остальных. или так не может быть и этот список списков a,b,c,d уже будет предварительно отсортирован?
Что мы получим в переменной List?

В итоге после строки предикака aastar
Код:
insert_each_path(NewPaths,Paths,Paths2),
в Paths2 мы наверное будем иметь список путей - "первый самый оптимальный", дополненый всеми возможными допустимыми переходами (NewPaths) + список путей Paths (ничем не дополненые), все отсортированы по оптимальности (и я так понимаю не все пути из NewPaths будут присутствовать). Выполнение предиката aastar сродни тому, что мы передвинулись вглубь на 1 ярус.
И текущим "фронтом" уже будет этот полученый список путей, который передаем рекурсивно.
Так продолжается пока самым последним состоянием в самом первом пути на текущем фронту (а выстроены они же оптимально) не будет final_state

Я так разжовываю объяснение больше для себя, пытаюсь понять. Укажите мне, где я в мыслях неправ

А Пролог все интереснее и чудесатее %)
Ответить с цитированием
  (#3 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,861
Сказал(а) спасибо: 2
Поблагодарили 287 раз(а) в 287 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 20.10.2005, 11:47

Цитата:
Хочу выслушать критику на мой предикат
Критика:
1) Если Вы хотите на Прологе рекурсивно обрабатывать ВЕСЬ список, а не его часть, то вычислять длину списка не надо, т.к. любая рекурсия содержит как минимум два клоза: в первом клозе от этого списка отщепляется голова (первый элемент) и совершаются манипуляции над ней, а если список пуст, то Пролог сам перейдёт ко второму клозу, где описано условие останова рекурсии.
2) С помощью find_last(...) Вы ищете последний элемент и делаете его первым. Так делать можно, но это НЕэффективно. Сами подсчитайте: Пусть n - длина списка. Чтобы дойти до последнего элемента надо оторвать (n-1) голов. Потом длина списка станет на единицу меньше и для получения последнего элемента Вам потребуется (n-2) прохода. И так далее до тех пор, пока в списке не останется один элемент. Итого будет совершено (n-1)(n-2)/2 операций.
3) В предикате rvrs(List,Res,Count) отсечение надо поставить перед рекурсивным вызовом, а не после, где оно уже не имеет смысла.

Пояснения к эффективному реверсу.
Если заталкивать элементы исходного списка в пустой стек, то на дне рекурсии мы получим реверсивный список. Для того, чтобы нам этот реверсивный список вытащить со дна на поверхность, надо воспользоваться ещё одной переменной, которую придётся протащить как нить Ариадны без изменений на дно рекурсии, а там ей передать реверсивный список. При возвращении со дна рекурсии на поверхность Пролог сам вытащит реверсивный список за эту спасительную ниточку.
Вот эта прога:
Код:
реверс(Список,Реверс):-рев(Список,[],Реверс). 
рев([А|Список],Стек,Реверс):-рев(Список,[А|Стек],Реверс).
рев([],Реверс,Реверс).
Ответить с цитированием
  (#4 (permalink)) Старый
tentul tentul вне форума
Member
 
Сообщений: 124
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2005
По умолчанию 20.10.2005, 15:44

Спасибо
Я не додумался:)
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Подскажите совместимы ли детали! Ace1 Материнские платы 1 07.12.2011 00:17
Посоветуйте детали imported_kentt Подбор комплектующих 3 04.05.2009 21:19
Подходят ли детали от DDR1 к материнке DDR2 или DDR3?)) Skotinka Подбор комплектующих 1 07.10.2008 12:45
Технические детали hobl Prolog 4 25.01.2008 19:44
Задача по детали Julli Prolog 0 10.01.2008 21:21
Продолжение алгоритма Евклида Dill Delphi 0 22.05.2006 00:29
Выделение детали прямоугольником ik C++ Builder 5 21.03.2006 09:06
В чем суть алгоритма А Anton Y. Yakovlev Алгоритмы 6 24.09.2005 13:32



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов