Ширина в прологе - PullRequest
Новая
       20

Ширина в прологе

9 голосов
/ 20 апреля 2009

Какова общая идея использовать ширину в первую очередь по умолчанию в схеме поиска по глубине в Прологе?

Не брать бесконечные ветви?

Есть ли какой-нибудь общий способ использовать ширину в Прологе? Я гуглил и не нашел слишком много полезной информации для новичка.

Ответы [ 3 ]

7 голосов
/ 22 июля 2009

Я кое-что узнал как " поиск по повестке дня ". Проходя по дереву (данных, отношений, правил, ...), вы поддерживаете «повестку дня» (список) того, что делать дальше. Когда вы входите в узел, вы помещаете его дочерние элементы в повестку дня, а затем переходите к первому элементу повестки дня, который вы открываете. Таким образом, если вы добавите новые пункты в конец повестки дня, вы получите широту. Если вы поставите их перед повесткой дня, вы получите глубину.

Это легко реализовать с помощью Пролога.

РЕДАКТИРОВАТЬ: я мог бы также дать подсказку реализации здесь. Это очень простая реализация алгоритма поиска по повестке дня. 

agenda_search([N|T],Mode):-
    doWithNode(N),           % do whatever you do the searching for
    getNodeChildren(N,C),
    (Mode=bf ->              % bf or df (depth-first)
        append(T,C,A);
        append(C,T,A)),
    agenda_search(A,Mode).

Он основан на внешних предикатах doWithNode, обозначающих действие, которое вы хотите выполнить с каждым узлом (например, сравнить данные узла с поисковым термином, сериализовать содержимое узла, asf.). И getNodeChildren, который свяжет список дочерних элементов данного узла с C (т. Е. Этот предикат фактически знает древовидную структуру и как найти дочерние узлы). Конечно, предикату doWithNode могут потребоваться дополнительные параметры для выполнения своей работы, которые также отображаются в списке аргументов agenda_search.

Вы можете вызвать его так: 

agenda_search([RootNode], bf)   % for breadth-first search

и 

agenda_search([RootNode], df)   % for depth-first search

На этой веб-странице я также нашел объяснение поиска по повестке дня . Хорошая вещь с поиском по повестке дня состоит в том, что вы можете легко переключаться между двумя вариантами df и bf и играть с результатами. Алгоритм достаточно хорошо работает с памятью, так как программа, узлы которой еще предстоит исследовать, захватывает только (более или менее) небольшую долю узлов в дереве за один раз (так называемая череда).

7 голосов
/ 21 апреля 2009

Преимущество ширины в том, что вы найдете все решения. С первой глубиной вы можете застрять в бесконечной ветви.

Недостатком является то, что в ширину используется много памяти, поэтому он обычно не используется для выполнения.

Если вы хотите использовать его, вам нужно явно реализовать его с какой-то очередью.

Редактировать: Если вы хотите использовать преимущества поиска в ширину без использования большого количества памяти, вы можете использовать итеративное углубление. Это поиск в глубину с ограничением по глубине, который вы последовательно увеличиваете. Это приводит к некоторым дублирующим вычислениям, но если ваше пространство поиска не имеет длинных линейных растяжений без ветвления, тогда это дублирование невелико.

4 голосов
/ 22 апреля 2010

Код повестки дня должен работать нормально. Для эффективности вы можете рассмотреть возможность использования другой структуры данных; действительно, в режиме ширины-первого весь список узлов (T) будет пересматриваться при добавлении (T, C, A). Например, вы можете использовать библиотечный модуль (очереди) из SICStus. Поиск в ширину тогда будет выглядеть следующим образом (параметризованный предикатами start / 1, предикатом-наследником s / 2 и предикатом цели target / 1). Обратите внимание, я также добавил проверку цикла. 

bfs(Res) :- start(Start), empty_queue(EQ),
  queue_append(EQ,[e(Start,[])],Q1),
  bfs1(Q1,Res).

bfs1(Queue,Res) :- queue_cons(e(Next,Path),NQ,Queue),
   bfs2(Next,Path,NQ,Res).

bfs2(H,Path,_NQ,Res) :- goal(H), reverse([H|Path],Res).
bfs2(H,Path,NQ,Res) :-  
              findall(e(Succ,[H|Path]),
                      (s(H,Succ),\+ member(Succ,Path)),AllSuccs),
              queue_append(NQ,AllSuccs,NewQueue),
              bfs1(NewQueue,Res).

(Вы также можете попытаться заменить / дополнить компонент Path лучшей структурой данных; например, AVL-деревья.) Пример решаемой проблемы: 

start(env(0,0)).
s(env(X,Y),env(X1,Y)) :- X1 is X+1.
s(env(X,Y),env(X,Y1)) :- Y1 is Y+1.
goal(env(3,3)).

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

...