Breadth First Search in Prolog

Question

Я новичок в Prolog и в настоящее время реализую алгоритмы поиска DFS (поиск по глубине) и BFS (поиск по ширине). Моя DFS отлично работает как код ниже, но BFS заканчивается и прерывается, когда он достигает листового узла (он не отступает и продолжает поиск). Я также прочитал некоторый пример кода об этом, но есть некоторые функции, которые они не определяют как s (Node, NewNode) ... так что это трудно понять, или версия использует Queue слишком сложно.

Вот мой код: Некоторые функции заземления:

%connected(+Start, +Goal, -Weight) 
connected(1,7,1). 
connected(1,8,1). 
connected(1,3,1). 
connected(7,4,1). 
connected(7,20,1). 
connected(7,17,1). 
connected(8,6,1). 
connected(3,9,1). 
connected(3,12,1). 
connected(9,19,1). 
connected(4,42,1). 
connected(20,28,1). 
connected(17,10,1). 

connected2(X,Y,D) :- connected(X,Y,D). 
connected2(X,Y,D) :- connected(Y,X,D). 

next_node(Current, Next, Path) :- 
    connected2(Current, Next, _), 
    not(member(Next, Path)). 

ДФС реализации:

depth_first(Goal, Goal, _, [Goal]). 
depth_first(Start, Goal, Visited, [Start|Path]) :- 
    next_node(Start, Next_node, Visited), 
    write(Visited), nl, 
    depth_first(Next_node, Goal, [Next_node|Visited], Path). 

BFS реализации:

breadth_first(Goal, Goal, _,[Goal]). 
breadth_first(Start, Goal, Visited, Path) :- 
    findall(X, 
      (connected2(X,Start,_),not(member(X,Visited))), 
      [T|Extend]), 
    write(Visited), nl, 
    append(Visited, [T|Extend], Visited2), 
    append(Path, [T|Extend], [Next|Path2]), 
    breadth_first(Next, Goal, Visited2, Path2). 

Путь что-то вроде очереди список. Например, когда ДФС вызов:

?- depth_first(1, 28, [1], P). 

BFS:

?- breadth_first(1, 28, [1], []). 

Answer 1

Во-первых, обычное понятие s(A,B) это так же, как ваш connect2(A,B,_).

Вы должны сделать свой интерфейс предикаты Явный:

depth_first(Start, Goal, Path):- 
    depth_first(Start, Goal, [Start], Path). 

Сохранение очереди в BFS не сложно вообще. Вместо того, чтобы Visited, есть VisitedLists очереди (POP спереди, добавить в конце, таким образом FIFO):

consed(A,B,[B|A]). 

bfs(Goal, [Visited|Rest], Path) :-      % take one from front 
    Visited = [Start|_],    
    Start \== Goal, 
    findall(X, 
     (connected2(X,Start,_),not(member(X,Visited))), 
     [T|Extend]), 
    maplist(consed(Visited), [T|Extend], VisitedExtended),  % make many 
    append(Rest, VisitedExtended, UpdatedQueue),  % put them at the end 
    bfs(Goal, UpdatedQueue, Path). 

Когда цель достигнута, Path инстанциируется:

bfs(Goal, [[Goal|Visited]|_], Path):- 
    reverse([Goal|Visited], Path). 

Вызов интерфейс должен быть соответственно.