3

開始と終了の間のすべての都市を与える述語ルーティングが必要です。例えば：

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

誰かが私を正しい方向に向けてくれますか...

4

3 に答える 3

4

グラフが非循環的であることが (定義により) 確実な場合は、Prolog の深さ優先検索を利用してルールを単純化できます。

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

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

これは、バックトラッキングで利用可能なすべてのパスを見つけます:

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

リスト構築の最初と 2 番目のパターンの違いに注意してください: [FromCity, ToCity]vs [FromCity|Connections]。ルールが成功すると、これConnectionsは になりますが、 はアトムになります。listToCity

グラフにサイクルが含まれている場合、このコードはループします。この問題を処理する単純なスキーマについては、別の回答を参照できます。

于 2012-11-01T07:22:55.597 に答える