深度優先搜索算法序言

Question

我希望你能幫助我。

我想了解在Prolog的深度優先搜索算法和我所遇到下面的代碼

go(Start, Goal) :- 
    empty_stack(Empty_been_list), 
    stack(Start, Empty_been_list, Been_list), 
    path(Start, Goal, Been_list). 

% path implements a depth first search in PROLOG 

% Current state = goal, print out been list 
path(Goal, Goal, Been_list) :- 
    reverse_print_stack(Been_list). 

path(State, Goal, Been_list) :- 
    mov(State, Next), 
    % not(unsafe(Next)), 
    not(member_stack(Next, Been_list)), 
    stack(Next, Been_list, New_been_list), 
    path(Next, Goal, New_been_list), !. 

reverse_print_stack(S) :- 
    empty_stack(S). 
reverse_print_stack(S) :- 
    stack(E, Rest, S), 
    reverse_print_stack(Rest), 
    write(E), nl. 

我有點明白是怎麼回事，但我不能爲我的生活中找到或發明一些我可以使用的事實。

請幫忙。即使它的一個非常簡單的事實中，我只需要在某處開始

預先感謝您

Answer 1

你只需要作出這樣的描述在圖中的有效移動的事實。例如，如果有節點A，B，C和D，圖上的每條邊都有一個mov（）事實。如果A具有邊緣，以B和C，以及B具有一個邊緣到d，你的事實將是

mov(A, B). 
mov(A, C). 
mov(B, D). 

基本上，繪製的曲線圖，寫像上述事實爲從到另一節點的節點的每一條路徑。

Answer 2

以下是在序言代碼

% solve(Node, Solution): 
 
% Solution is an acyclic path (in reverse order) between Node and a goal 
 

 
solve(Node, Solution) :- 
 
    depthfirst([], Node, Solution). 
 

 
% depthfirst(Path, Node, Solution): 
 
% extending the path [Node | Path] to a goal gives Solution 
 

 
depthfirst(Path, Node, [Node | Path]) :- 
 
    goal(Node). 
 

 
depthfirst(Path, Node, Sol) :- 
 
    s(Node, Node1), 
 
    \+ member(Node1, Path),    % Prevent a cycle 
 
    depthfirst([Node | Path], Node1, Sol). 
 

 
depthfirst2(Node, [Node], _) :- 
 
    goal(Node). 
 

 
depthfirst2(Node, [Node | Sol], Maxdepth) :- 
 
    Maxdepth > 0, 
 
    s(Node, Node1), 
 
    Max1 is Maxdepth - 1, 
 
    depthfirst2(Node1, Sol, Max1). 
 

 

 
goal(f). 
 
goal(j). 
 
s(a,b). 
 
s(a,c). 
 
s(b,d). 
 
s(b,e). 
 
s(c,f). 
 
s(c,g). 
 
s(d,h). 
 
s(e,i). 
 
s(e,j).

用於爲了在對沙沙SWI序言來測試該代碼頭並粘貼到終端DFS的示例。

然後查詢上的右手側的碼和類型：解決（一，溶膠）

該解決方案將是：溶膠= [J，E，B，A]

可以調試代碼通過鍵入：trace，（solve（a，Sol））。

以下是BFS的一個例子在序言代碼

頭中使用到沙沙並使用相同的步驟

溶液之前將查詢它：溶膠= [F，C，A]

% solve(Start, Solution): 
 
% Solution is a path (in reverse order) from Start to a goal 
 

 
solve(Start, Solution) :- 
 
    breadthfirst([ [Start] ], Solution). 
 

 
% breadthfirst([ Path1, Path2, ...], Solution): 
 
% Solution is an extension to a goal of one of paths 
 

 
breadthfirst([ [Node | Path] | _], [Node | Path]) :- 
 
    goal(Node). 
 

 
breadthfirst([Path | Paths], Solution) :- 
 
    extend(Path, NewPaths), 
 
    append(Paths, NewPaths, Paths1), 
 
    breadthfirst(Paths1, Solution). 
 

 
extend([Node | Path], NewPaths) :- 
 
    bagof([NewNode, Node | Path], 
 
     (s(Node, NewNode), \+ member(NewNode, [Node | Path])), 
 
     NewPaths), 
 
    !. 
 

 
extend(Path, []).    % bagof failed: Node has no successor 
 
s(a,b). 
 
s(a,c). 
 
s(b,d). 
 
s(b,e). 
 
s(c,f). 
 
s(c,g). 
 
s(d,h). 
 
s(e,i). 
 
s(e,j). 
 
goal(j). 
 
goal(f).

希望這有助於理解DFS和BFS

使用此圖可幫助您瞭解樹