我想找到Prolog中两个节点之间的最短路径。 我想如何找到两个节点之间的所有路径，但不幸的是，下面的代码会进入循环：
arc （A，b）。 arc（b，a）。 arc（b，c）。 arc（c，b）。 arc（c，d）。 arc（d，c）。 path（X，Y，[arc（X，Y）]）： - arc（X，Y）。 path（X，Y，[arc（X，Z）| P]）： - arc（X，Z）， path（Z，Y，P）。代码运行：
？ - path（a，c，R）。 R = [arc（a，b），arc（b，c）]; R = [arc（a，b），arc（b，a），arc（a，b），arc（b，c）]; R = [arc（a，b），arc（b，a），arc（a，b），arc（b，a），arc（a，b），arc（b，c）] ....所以，我的问题是：如何获得所有路径无限循环？
在一天结束时，我会得到列表的长度并找到最小值。
请尽可能提供ISO Prolog解决方案。注意：这里是更新的代码，我仍然有问题。显然，当检查一个事实而不是一个原子时，成员谓词不起作用。 pre $ xxx（[]）。 path（X，Y，[arc（X，Y）]）： - arc（X，Y）。 path（X，Y，[arc（X，Z）| P]）： - arc（X，Z），xxx（L），member （X，Z），L） - > ！ （arc（Z，X），L） - > ！; （append（L，[arc（X，Z）]，R），retract（xxx（ _）），断言（XXX（R）），路径（Z，Y，P）））。
和我的成员谓词是：
构件（X，[X | T]）。 成员（X，[H | T]）： - 成员（X，T）。谢谢。
解决方案我们使用 meta-谓词 路径/ 4 结合您给出的 arc / 2 的定义：
？ - 路径（圆弧，路径，从，到）。 From = To，Path = [To] ; From = a，To = b，Path = [a，b] ; From = a，To = c，Path = [a，b，c] ; From = a，To = d，Path = [a，b，c，d] ; From = b，To = a，Path = [b，a] ; From = b，To = c，Path = [b，c] ; From = b，To = d，Path = [b，c，d] ; From = c，To = b，Path = [c，b] ; From = c，To = a，Path = [c，b，a] ; From = c，To = d，Path = [c，d] ; From = d，To = c，Path = [d，c] ; From = d，To = b，Path = [d，c，b] ; From = d，To = a，Path = [d，c，b，a] ;假。path / 4 的定义排除了所有周期。
要得到最短的路径，我们需要查看所有解决方案！
$ b为了说明这一点，我们来扩展你对 arc / 2 的定义：
arc（a，b）。 arc（b，a）。 arc（b，c）。 arc（a，c）。 ％（新） arc（b，d）。 ％（新） arc（c，b）。 arc（c，d）。 arc（d，c）。假设我们要从 a 到 d ，所以我们查询：
？ - 路径（弧，路径，a，d）。 Path = [a，b，c，d] ;路径= [a，b，d]％最短路径＃1 ;路径= [a，c，b，d] ;路径= [a，c，d]％最短路径＃2 ;假。在上面的查询中， 有两个不同的最短路径 c> a to d 。
为了获得两者，我们必须全部考虑路径---或者使用更智能的元谓语（留作家庭作业）。
I want to find the shortest path between two nodes in Prolog. I figured how to find all the paths between two nodes, but unfortunately the following code falls into loops:
arc(a,b). arc(b,a). arc(b,c). arc(c,b). arc(c,d). arc(d,c). path(X,Y,[arc(X,Y)]) :- arc(X,Y). path(X,Y,[arc(X,Z)|P]) :- arc(X,Z), path(Z,Y,P).The code run is:
?- path(a,c,R). R = [arc(a, b), arc(b, c)] ; R = [arc(a, b), arc(b, a), arc(a, b), arc(b, c)] ; R = [arc(a, b), arc(b, a), arc(a, b), arc(b, a), arc(a, b), arc(b, c)] ....So, my question is : How to get all paths without looping infinitely?
at the end of the day, i will get the length of the list and find the minimum.
Please if possible, give solutions that are ISO Prolog.
Note: here is the updated code, by I still have problem. Apparently the member predicate doesn't work when checking against a fact rather than an atom.
xxx([]). path(X,Y,[arc(X,Y)]) :- arc(X,Y). path(X,Y,[arc(X,Z)|P]) :- arc(X,Z) ,xxx(L) ,member(arc(X,Z),L)-> !; (member(arc(Z,X),L)-> !; (append(L,[arc(X,Z)],R),retract(xxx(_)),assert(xxx(R)),path(Z,Y,P))).and my member predicate is:
member(X,[X|T]). member(X,[H|T]) :- member(X,T).Thank you.
解决方案We use meta-predicate path/4 in combination with the definition of arc/2 that you gave:
?- path(arc,Path,From,To). From = To , Path = [To] ; From = a, To = b, Path = [a,b] ; From = a, To = c, Path = [a,b,c] ; From = a, To = d, Path = [a,b,c,d] ; From = b, To = a, Path = [b,a] ; From = b, To = c, Path = [b,c] ; From = b, To = d, Path = [b,c,d] ; From = c, To = b, Path = [c,b] ; From = c, To = a, Path = [c,b,a] ; From = c, To = d, Path = [c,d] ; From = d, To = c, Path = [d,c] ; From = d, To = b, Path = [d,c,b] ; From = d, To = a, Path = [d,c,b,a] ; false.The definition of path/4 excludes all cycles.
To get the shortest paths we need to look at all solutions!
To show this is actually so, let's expand your definition of arc/2 like this:
arc(a,b). arc(b,a). arc(b,c). arc(a,c). % (new) arc(b,d). % (new) arc(c,b). arc(c,d). arc(d,c).Let's say we want to "get all shortest paths from a to d", so we query:
?- path(arc,Path,a,d). Path = [a,b,c,d] ; Path = [a,b,d] % shortest path #1 ; Path = [a,c,b,d] ; Path = [a,c,d] % shortest path #2 ; false.In above query there are two distinct shortest paths from a to d.
To get both, we must look at all paths---or use a smarter meta-predicate (left as homework).
更多推荐
在Prolog中查找图中两个节点之间的最短路径
发布评论