无需重新访问即可找到所有可能的路径 [英] Find all possible paths without revisiting

问题描述

我需要一个谓词路由，它给出了 start 和 amp; 之间的所有城市.结尾.例如:

I need a predicate routing which gives all the cities between start & end. For example:

path(chicago,atlanta).
path(chicago,milwaukee).
path(milwaukee,detroit).
path(milwaukee,newyork).
path(chicago,detroit).
path(detroit, newyork).
path(newyork, boston).
path(atlanta,boston).
path(atlanta, milwaukee).

?- routing(chicago,newyork,X).
X=[chicago,milwaukee,newyork];
X=[chicago,detroit,newyork];
X=[chicago,milwaukee,detroit,newyork];
X=[chicago,atlanta,milwaukee,newyork];
X=[chicago,atlanta,milwaukee,detroit,newyork]

我已经尝试过这个，并且会继续回到它.

I have tried this, and keep coming back to it.

routing(FromCity,ToCity,[FromCity|ToCity]) :-
  path(FromCity,ToCity).

routing(FromCity,ToCity,[FromCity|Connections]) :- 
  path(FromCity,FromConnection), 
  path(FromConnection,ToConnection),
  path(ToConnection,ToCity),
  routing(ToConnection,ToCity,Connections).

routing(FromCity,ToCity,[]).

但它只是不断地给予

X=[chicago,milwaukee,newyork];
X=[chicago,chicago,newyork];
X=[chicago,chicago,chicago,newyork]
...
..

有人可以指出我正确的方向吗...

Can some one please point me in the right direction ...

推荐答案

如果你确定(根据定义)你的图是无环的，你可以简化你的规则，利用 Prolog 深度优先搜索:

If you are sure (by definition) that your graph is acyclic, you can simplify your rule, exploiting Prolog depth first search:

routing(FromCity, ToCity, [FromCity, ToCity]) :-
  path(FromCity, ToCity).

routing(FromCity, ToCity, [FromCity|Connections]) :- 
  path(FromCity, ToConnection),
  routing(ToConnection, ToCity, Connections).

这会找到回溯的所有可用路径:

This find all availables paths on backtracking:

?- routing(chicago,newyork,X).
X = [chicago, atlanta, milwaukee, newyork] ;
X = [chicago, atlanta, milwaukee, detroit, newyork] ;
X = [chicago, milwaukee, newyork] ;
X = [chicago, milwaukee, detroit, newyork] ;
X = [chicago, detroit, newyork] ;
false.

注意列表构建的第一种和第二种模式之间的区别:[FromCity, ToCity] 与 [FromCity|Connections].这是因为当规则成功时，Connections 将是一个 list，而 ToCity 将是一个原子.

Note the difference between the first and second pattern of list construction: [FromCity, ToCity] vs [FromCity|Connections]. This because Connections will be a list, while ToCity will be an atom, when the rule will succeed.

如果您的图表包含循环，则此代码将循环.您可以参考另一个答案，了解处理此问题的简单架构.

If your graph contains cycles, this code will loop. You can refer to another answer for a simple schema that handles this problem.

这篇关于无需重新访问即可找到所有可能的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！