path - 使用prolog寻找路径

Question

我想知道是否有从一个点到另一个点的路径。

例如，2 -> 4 -> 7 1 -> 3 -> 2 -> 9 5 -> 1 -> 6 -> 8

这些是路径。我想写一个谓词路径（开始，结束），弧由一组弧（From，To）事实表示。

例如，当给出 path(1, 7) 时，它必须返回 true。当给出 path(6, 1) 时，这必须返回 false。因为弧是有方向的。

Answer 1

1. If there is an arc between X and Y, then Path=arc(X,Y). That is, if arc(X,Y) then path(X,Y)). Or, in Prolog this is:

   path(X,Y,[arc(X,Y)]) :- arc(X,Y).

2. Otherwise, if there is an arc between X and some other node Z, and there is a path from Z to Y, then there is a path from X to Y too. That is, if arc(X,Z) and path(Z,Y) then path(X,Y). In Prolog this is:

   path(X,Y,[arc(X,Z)|P]) :- arc(X,Z),path(Z,Y,P).

Taken from this site.

You could also bundle this into one predicate that simply takes a list of arcs and recursively searches for a path

Answer 2

Try to answer splitting the problem in elementary problems.

path(From, To) :-
  arc(From, Intermediate),
  path(Intermediate, To).

But, do you see where path should stop? And if there are cycles, what happens?

What's miss it's the trivial case, stating that path(X, X) it's always true. Add to above rule:

path(To, To).

Maybe it's clearer if we write a single rule, using If Then Else

path(From, To) :-
  (   From \= To
  ->  arc(From, Intermediate),
      path(Intermediate, To)
  ;   true
  ).