查找所有可能的路径而不用重访

我需要一个谓词路由，它可以为所有城市提供从开始&结束的所有城市。例如：查找所有可能的路径而不用重访

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]

我试过这个，并不断回来。

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] 
... 
..

可有一个人请点我在正确的方向...

来源

2012-11-01 Kickaha

如果确定（定义），你的图形是无环，你可以简化你的规则，利用Prolog深度优先搜索：

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

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

这个找到所有ava ilables上回溯路径：

?- 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] VS [FromCity|Connections]。这是因为Connections将是list，而ToCity将成为原子，当规则成功时。

如果您的图形包含循环，此代码将循环。您可以参考another answer获取处理此问题的简单模式。

来源

2012-11-01 07:22:55 CapelliC

您好，我有一个类似的问题，但我想用“写”函数写出来里面的路径所以我将不得不在函数中调用是开始和结束有没有什么办法来配置您的示例以使其工作？ – Fjodor

@Fjodor：由于回溯，你无法可靠地写出路径。尝试在递归调用后写入（连接） – CapelliC

这是我的解决方案，适用于有向图或无向图，有或没有周期。

它也试图找到所有路径，而不需要重新访问。

c(1,2). 
% ... c(X,Y) means X and Y are connected 

d(X,Y):- c(X,Y). 
d(X,Y):- c(Y,X). 
% Use d instead of c to allow undirected graphs 

findPathHelper(_, Begin, [], End):- d(Begin, End). 
findPathHelper(Front, Begin, [Next|NMiddle], End):- 
    not(member(Begin,Front)), 
    d(Begin, Next), 
    append([Front,[Begin]], NFront), 
    findPathHelper(NFront, Next, NMiddle, End). 

findPath(Start, End, Path):- 
    findPathHelper([], Start, Middle, End), 
    append([[Start],Middle,[End]], Path).

来源

2015-12-03 21:38:14 VillasV

如何继续如下？

首先，我们选择一个比path更好的谓词名称。 edge怎么样？

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

如上定义，edge/2显然不是symmetric，否则下面的查询不会成功！

?- edge(X, Y), \+ edge(Y, X). 
    X = chicago , Y = atlanta 
; X = chicago , Y = milwaukee 
; X = milwaukee, Y = detroit 
; X = milwaukee, Y = newyork 
; X = chicago , Y = detroit 
; X = detroit , Y = newyork 
; X = newyork , Y = boston 
; X = atlanta , Y = boston 
; X = atlanta , Y = milwaukee.

接下来，我们定义connected_to/2作为edge/2的对称闭：

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

最后，我们使用meta-predicate path/4连同connected_to/2：

?- path(connected_to, Path, From, To). 
; From = To     , Path = [To] 
; From = chicago, To = atlanta, Path = [chicago,atlanta] 
; From = chicago, To = boston , Path = [chicago,atlanta,boston] 
; From = chicago, To = newyork, Path = [chicago,atlanta,boston,newyork] 
...

所以...做的最一般查询path/4（含connected_to/2）普遍终止？

 
?- path(connected_to, Path, From, To), false. 
false.         % terminates universally

最后，让我们计算的不同接地路径总数：

?- setof(P, From^To^(path(connected_to,P,From,To),ground(P)), _Ps), 
    length(_Ps, N_Ps). 
N_Ps = 244.

来源

2015-12-03 22:48:21 repeat

查找所有可能的路径而不用重访

回答

相关问题