如何处理Prolog图遍历中的路径 [英] How to handle a path in Prolog graph traversal
本文介绍了如何处理Prolog图遍历中的路径的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我用Prolog写过
edge(x, y).
edge(y, t).
edge(t, z).
edge(y, z).
edge(x, z).
edge(z, x).
path(Start, End, Path) :-
path3(Start, End, [Start], Path).
path3(End, End, RPath, Path) :-
reverse(RPath, Path).
path3(A,B,Path,[B|Path]) :-
edge(A,B),
!.
path3(A, B, Done, Path) :-
edge(A, Next),
\+ memberchk(Next, Done),
path3(Next, B, [Next|Done], Path).
它也照顾循环图,当我尝试从同一节点遍历同一节点时,我得到了不规则的输出.
Its taking care of cyclic graphs as well, I am getting an irregular output when I try to traverse same node from same node.
例如:path(x,x,P).
预期输出应为:
eg: path(x,x,P).
expected output should be:
P = [x, z, t, y, x]
P = [x, z, y, x]
P = [x, z, x]
但是,我得到的输出是
p = [x] ------------> wrong case
P = [x, z, t, y, x]
P = [x, z, y, x]
P = [x, z, x]
如何摆脱这种不必要的情况. 谢谢
How can I get rid of this unwanted case. Thanks
推荐答案
?- path(edge,Path,x,Last), edge(Last,x).
Last = z, Path = [x,y,t,z]
; Last = z, Path = [x,y,z]
; Last = z, Path = [x,z]
; false.
好的!以上三个答案正是OP希望在问题中得到的.
Alright! Above three answers are exactly what the OP wished for in the question.
只是为了好玩,让我们看看基于edge/2
的所有可能路径!
Just for fun let's look at all possible paths based on edge/2
!
?- path(edge,Path,From,To).
From = To , Path = [To]
; From = x, To = y, Path = [x,y]
; From = x, To = t, Path = [x,y,t]
; From = x, To = z, Path = [x,y,t,z]
; From = x, To = z, Path = [x,y,z]
; From = y, To = t, Path = [y,t]
; From = y, To = z, Path = [y,t,z]
; From = y, To = x, Path = [y,t,z,x]
; From = t, To = z, Path = [t,z]
; From = t, To = x, Path = [t,z,x]
; From = t, To = y, Path = [t,z,x,y]
; From = y, To = z, Path = [y,z]
; From = y, To = x, Path = [y,z,x]
; From = x, To = z, Path = [x,z]
; From = z, To = x, Path = [z,x]
; From = z, To = y, Path = [z,x,y]
; From = z, To = t, Path = [z,x,y,t]
; false.
这篇关于如何处理Prolog图遍历中的路径的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文