当前位置: 动力学知识库 > 问答 > 编程问答 >

path - Directed Graph In Prolog

问题描述:

can someone please elaborate upon the functionality/conditions of travel(A,B,Visited,Path) and travel(A,B,P,[B|P]) .. this code finds the path between path A and B in a graph

edge(a,b).

edge(b,c).

edge(b,d).

edge(c,d).

edge(d,b).

edge(e,f).

edge(e,g).

edge(e,h).

edge(h,i).

edge(i,g).

edge(b,e).

connectedEdges(X,Y) :- edge(X,Y).

connectedEdges(X,Y) :- edge(Y,X).

path(A,B,Path) :-

travel(A,B,[A],Q),

reverse(Q,Path).

travel(A,B,P,[B|P]) :-

connectedEdges(A,B).

travel(A,B,Visited,Path) :-

connectedEdges(A,C),

C \== B,

\+member(C,Visited),

travel(C,B,[C|Visited],Path).

网友答案:

Lets start with the first travel/4 rule:

travel(A,B,P,[B|P]) :- 
   connectedEdges(A,B).

"If points A and B are directly connected to each other, then we have found a direct sub-path, and hence can succeed by adding point B to the path which is unified with all the points we have visited thus far."

In other words, since we have solved a sub-problem (by finding a direct connection to 2 nodes), we can essentially state that P (all that we have visited so far), is the tail of the path list [B|P] (the total path is the last node we have visited .... the current destination node, prepended to all the previous nodes we've visited).


Now for the next travel/4 rule:

travel(A,B,Visited,Path) :-
   connectedEdges(A,C),           
   C \== B,
   \+member(C,Visited),
   travel(C,B,[C|Visited],Path).

It is important to note that this second rule will always be tried as an alternative, whether or not the first rule succeeded. Due to that fact of this implementation, the implication here is that this code can possibly find multiple paths (if more than one exists).

Anyway, in this second rule we find any nodes that are connected to A, other than B. Why?, this is because the first rule above already tried that; in this rule we're searching for alternatives. If that node C hasn't already been visited, we simply try to travel from that point (C) to our destination. Then we recursively query/call travel/4 yet again, until we've found a complete path(s).

Note again, that this implementation may find 0, 1, or more than 1 solution to a given query.


To recapitulate, the first rule is called to find direct connections between points. The second rule is called to find indirect connections between points.

分享给朋友:
您可能感兴趣的文章:
随机阅读: