在Prolog中查找图中两个节点之间的最短路径 [英] Find the shortest path between two nodes in a graph in Prolog

问题描述

我想找到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中查找图中两个节点之间的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！