深度优先搜索算法 Prolog

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.

我有点理解正在发生的事情，但我找不到或想出一些可以与之配合使用的事实。

请帮忙。即使只是一组非常简单的事实，我也需要一个起点。

提前感谢您的帮助。

- Sean Gray

---

这是一个通用的解决方案，适用于此问题。您只需说closure0(mov,Start,Finis)即可。 - false

请像其他谓词一样缩进 go。 - vmg

我可能没有正确地提问，因为我不理解“false”的答案。 - Sean Gray

@SeanGray：请提供整个程序，包括一些关于mov/2的事实。否则，你的代码仍然是假设性的。 - false

这是我要问的问题:D，我想知道我可以使用哪些事实。 - Sean Gray

基本上，你没有要遍历的“树”。此外，你的算法中也没有对核心谓词的实现。显然，想到这个算法的人打算使用堆栈和适当的方法。我敢打赌这是你的作业，需要你填补这些空缺。祝你好运。 - vmg

Answer 1

以下是在Prolog代码中使用DFS的示例。

% 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).

为了测试这段代码，前往Swish SWI Prolog并将其粘贴到终端中。

然后查询代码，并在右侧键入：solve(a, Sol)

解决方案将是：Sol = [j, e, b, a]

您可以通过输入以下内容来调试此代码：trace，(solve(a, Sol))。

以下是Prolog代码中使用的BFS示例

前往swish并使用与之前相同的步骤进行查询

解决方案将是：Sol = [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:

使用此图表可帮助您理解树形结构。

- dave o grady

Answer 2

您只需创建描述图中有效移动的事实。

例如，如果您有节点A、B、C和D，则图上的每条边都将有一个mov()事实。如果A连接到B和C，并且B连接到D，则您的事实将是

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

基本上，对于从一个节点到另一个节点的每条路径，绘制一张图并写出类似上面的事实。

- ABigFatJerk