深度优先搜索算法序言

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

使用此图可帮助您了解树