已知path(X,Y,Path): X,Y为两点，X,Y两点间路径显示为Path,求:

1:用深度优先搜索(DFS)执行这个【path】,用prolog编写并测试
2:用宽度优先搜索(BFS)执行这个【path】,用prolog编写并测试
3:注释这两种不同的用法中所用的【路径的数量】

用以下图像来检测code
edge(a,b). edge(b,c). edge(b,d). edge(d,e). edge(d,f).
edge(a,g). edge(g,h). edge(h,i). edge(f,i).

PS：最好用GNU prolog

题目是我自己翻译的 原版为英文

We will represent a search tree (or any graph) using the edges of the tree. For
instance, the tree
a —- b —- c and a – d – e
will be represented in prolog as
edge(a,b). edge(b,c). edge(a,d). edge(d,e).

Given two vertices X, Y rule path(X,Y,Path) determines a path from X to Y (if
one exists) and reports it in Path.

1. Write and test in prolog a set of rules that implement path using depth
first search
2. Write and test in prolog a set of rules that implement path using breadth
first search.
3. Comments on different usages of path, and the number of paths that will
be reported in presence of cycles in the graph.

Use the graph below for testing the code.

edge(a,b). edge(b,c). edge(b,d). edge(d,e). edge(d,f).
edge(a,g). edge(g,h). edge(h,i). edge(f,i).
1

树定义为许多edge(A,B)看起来很简单了，DFS就是：

代码:


dfs(Node) :-
    write('Visit node '), write(Node), nl,
    edge(Node, NextNode),
    dfs(NextNode).


BFS需要用列表，将每一层端点先收集在一个独一列表中，走访、并且将此列表的下一层端点收集到另一个独一列表中。方法大概是先知道第一层就可以求第二层，再由第二层可以找到第三层：

代码:


bfs(Node) :- bfs1([Node]).
bfs1(List) :-
    foreach(member(N,List), (write('Visit node '),write(N),nl)),
    bagof(Ns, (member(N,List),bagof(Nxt,edge(N,Nxt),Ns)), Nss),
    lists:flatten(Nss, Nss1),
    bfs1(Nss1).


---

後补充：但是，看到第三子题目，发现这个问题要把edge想成可能有不同的方向，那麽，程序写法就不会只有以上那麽简单。

yauhsien 写道:树定义为许多edge(A,B)看起来很简单了，DFS就是：

代码:


dfs(Node) :-
    write('Visit node '), write(Node), nl,
    edge(Node, NextNode),
    dfs(NextNode).


BFS需要用列表，将每一层端点先收集在一个独一列表中，走访、并且将此列表的下一层端点收集到另一个独一列表中。方法大概是先知道第一层就可以求第二层，再由第二层可以找到第三层：

代码:


bfs(Node) :- bfs1([Node]).
bfs1(List) :-
    foreach(member(N,List), (write('Visit node '),write(N),nl)),
    bagof(Ns, (member(N,List),bagof(Nxt,edge(N,Nxt),Ns)), Nss),
    lists:flatten(Nss, Nss1),
    bfs1(Nss1).


---

後补充：但是，看到第三子题目，发现这个问题要把edge想成可能有不同的方向，那麽，程序写法就不会只有以上那麽简单。

第三题不需要code
是手写测试两种方法结果的报告
只需要把前两题的code写好就可以

wowsfsf 写道:

yauhsien 写道:

---

後补充：但是，看到第三子题目，发现这个问题要把edge想成可能有不同的方向，那麽，程序写法就不会只有以上那麽简单。

第三题不需要code
是手写测试两种方法结果的报告
只需要把前两题的code写好就可以

第三子题仔细看，并不是你所提「路径数量」而已，而是除了要交待路径用法的差别之外，还要能找到有多少个路径构成循环路线。并不是只有前二子题的总结而已，而是可能你原本写完了前二题，见到第三题则发现要把前二题擦掉、重新思考。

他给你的路线，a到i之间有个相当大的循环，并不是树，不过边的定义方式搭配我的写法恰好不会让循环路线造成问题。

yauhsien 写道:

wowsfsf 写道:

yauhsien 写道:

---

後补充：但是，看到第三子题目，发现这个问题要把edge想成可能有不同的方向，那麽，程序写法就不会只有以上那麽简单。

第三题不需要code
是手写测试两种方法结果的报告
只需要把前两题的code写好就可以

第三子题仔细看，并不是你所提「路径数量」而已，而是除了要交待路径用法的差别之外，还要能找到有多少个路径构成循环路线。并不是只有前二子题的总结而已，而是可能你原本写完了前二题，见到第三题则发现要把前二题擦掉、重新思考。

他给你的路线，a到i之间有个相当大的循环，并不是树，不过边的定义方式搭配我的写法恰好不会让循环路线造成问题。

那么结合第三题
你的算法也可行吗

wowsfsf 写道:
那么结合第三题
你的算法也可行吗

前面我已先回答你，不行。

yauhsien 写道:

wowsfsf 写道:
那么结合第三题
你的算法也可行吗

前面我已先回答你，不行。

那这三题该怎么做呢

wowsfsf 写道:题目是我自己翻译的 原版为英文

We will represent a search tree (or any graph) using the edges of the tree. For
instance, the tree
a —- b —- c and a – d – e
will be represented in prolog as
edge(a,b). edge(b,c). edge(a,d). edge(d,e).

Given two vertices X, Y rule path(X,Y,Path) determines a path from X to Y (if
one exists) and reports it in Path.

1. Write and test in prolog a set of rules that implement path using depth
first search
2. Write and test in prolog a set of rules that implement path using breadth
first search.
3. Comments on different usages of path, and the number of paths that will
be reported in presence of cycles in the graph.

Use the graph below for testing the code.

edge(a,b). edge(b,c). edge(b,d). edge(d,e). edge(d,f).
edge(a,g). edge(g,h). edge(h,i). edge(f,i).
1

先帮着把原文译出，原文说：有一种表达树的方法是用edge/2表示 (注：这在P99练习题中也有提到) ，那麽，像 a-b-c 或 a-d-e 写在Prolog程序就是

代码:

edge(a,b). edge(b,c). edge(a,d). edge(d,e).

现在有一个图已经定义为

代码:

edge(a,b). edge(b,c). edge(b,d). edge(d,e). edge(d,f).
edge(a,g). edge(g,h). edge(h,i). edge(f,i).

(注：仔细看，这是一个环状的图)
要求写Prolog程序规格为 path/3 ，假如写了 ?- path(X, Y, Path) 就是去找 X 到 Y 有没有路径，如果有路径，就把路径回报到 Path 这个参数。

问题一：用DFS方式写 path/3 。
问题二：用BFS方式写 path/3 。
问题三：说说以上二个方法找到的路径的不同用途 (注：我英文有点烂，突然看不懂「说说路径的不同用途」什麽意思) 并且告诉我们有多少路径带有回路。

---

先填第一题的作法，观念是在一个图中可以把任何一个点当做出发点，对这个出发点来说，它这边或那边的邻点都算是它搜寻树的下一层。所以我会先做个 adjacent/2 找一个点的邻点：

代码:

adjacent(Node, Nodes) :-
   bagof(A, (edge(Node,A); edge(A,Node)), Nodes).

然後 path/3 照着一般Prolog递归运行，基本就是DFS。但是遇到图中有回路会弄出无限递归，所以不能这样做。我打算用到 path/4 辅助， path(-Node1, -Node2, +PassPath, +Path) ，从 Node1 到 Node2 之间找路径，如果找到路径就暂时先加到 PassPath ，之後如果在找邻点时，可以核对邻点是否曾经在 PassPath 中出现过，并且只考虑从未出现过的邻点。用 PassPath 当历史纪录，可以避免重复搜索到回路上的点。

所以，问题一的答案，我这样写：

代码:

edge(a,b). edge(b,c). edge(b,d). edge(d,e). edge(d,f). edge(f,i).
edge(a,g). edge(g,h). edge(h,i).
adjacent(Node, Nodes) :-
   bagof(A, (edge(Node,A); edge(A,Node)), Nodes).
diffSet(List, AnotList, DiffList) :-
   bagof(M, (member(M,List), not(member(M,AnotList))), DiffList).
path(X, Y, Path) :-
   path(X, Y, [], Path).
path(X, X, PassPath, Path) :- lists:reverse([X|PassPath], Path).
path(X, Y, PassPath, Path) :- X \= Y,
   adjacent(X, Neighbors),
   diffSet(Neighbors, PassPath, Neighbors1),
   member(P,Neighbors1),
   path(P,Y,[X|PassPath],Path).

---

至於第二题的BFS，我还不知道答案的 Path 长成什麽样子。有人知道吗？

---

第三题要找回路的路径有多少数目，也可以写程序解决：

代码:


pathCircle(Pair) :-
   (edge(X,_), edge(_,Y); edge(_,X), edge(Y,_)), X \= Y,
   bagof(Path, path(X, Y, Path), Ps),
   length(Ps, N),
   N > 1,
   Pair = [X,Y].
numCircle(N) :-
   setof(Pair, pathCircle(Pair), Ps),
   write(Ps),
   length(Ps, N).

结果是

代码:

?- numCircle(N).
[[a,b],[a,c],[a,d],[a,e],[a,f],[a,g],[a,h],[a,i],[b,a],[b,d],[b,e],[b,f],[b,g],[b,h],[b,i],[c,a],[c,d],[c,f],[c,g],[c,h],[d,a],[d,b],[d,c],[d,f],[d,g],[d,h],[d,i],[e,a],[e,b],[e,f],[e,g],[e,h],[f,a],[f,b],[f,c],[f,d],[f,e],[f,g],[f,h],[f,i],[g,a],[g,b],[g,c],[g,d],[g,e],[g,f],[g,h],[g,i],[h,a],[h,b],[h,c],[h,d],[h,e],[h,f],[h,g],[h,i],[i,a],[i,b],[i,d],[i,f],[i,g],[i,h]]
N = 62.

BFS搜索路径：

代码:


enqueue(Queue, List, Result) :-
   append(Queue, List, Result).
pathBFS(X, Y, Path) :-
   InitPath = [X],
   Queue = [InitPath],
   pathBFS(Queue, Y, [], PathList),
   member(Path, PathList).
pathBFS([], _, Accu, PathList) :-
   findall(Path ,
         (member(RevPath,Accu), lists:reverse(RevPath,Path)),
         PathList).
pathBFS([[H|Rest]|Queue], Target, Accu, Result) :-
   Path = [H|Rest],
   adjacent(H, Neighbors),
   findall([N|Path] ,(member(N,Neighbors), not(member(N,Path))), NPaths),
   enqueue(Queue, NPaths, Queue1),
   findall([T|TRest], (member([T|TRest],NPaths), T = Target), APaths),
   append(APaths, Accu, Accu1),
   pathBFS(Queue1, Target, Accu1, Result).

关键部份：

1. BFS部份，见pathBFS/4和enqueue/3的处理，并可参考维基百科 http://en.wikipedia.org/wiki/Breadth-first_search 。Queue是路径的集合。
   
2. 回路侦测部份，是用Queue当作历史纪录，排除已访问的邻点。
   

wowsfsf 写道:

yauhsien 写道:树定义为许多edge(A,B)看起来很简单了，DFS就是：

代码:


dfs(Node) :-
    write('Visit node '), write(Node), nl,
    edge(Node, NextNode),
    dfs(NextNode).


BFS需要用列表，将每一层端点先收集在一个独一列表中，走访、并且将此列表的下一层端点收集到另一个独一列表中。方法大概是先知道第一层就可以求第二层，再由第二层可以找到第三层：

代码:


bfs(Node) :- bfs1([Node]).
bfs1(List) :-
    foreach(member(N,List), (write('Visit node '),write(N),nl)),
    bagof(Ns, (member(N,List),bagof(Nxt,edge(N,Nxt),Ns)), Nss),
    lists:flatten(Nss, Nss1),
    bfs1(Nss1).


---

後补充：但是，看到第三子题目，发现这个问题要把edge想成可能有不同的方向，那麽，程序写法就不会只有以上那麽简单。

第三题不需要code
是手写测试两种方法结果的报告
只需要把前两题的code写好就可以

可以把这个bfs换成gnu prolog的code吗

wowsfsf 写道:可以把这个bfs换成gnu prolog的code吗

gnu prolog的基本谓词应该跟SWI prolog差不多，你可以试一下。