9

同様の質問に目を通しましたが、私の問題に関連するものは何も見つかりません。のデータベースを使用して、からCityAへのパスを見つけるアルゴリズムまたは「ループ」のセットを見つけるのに苦労していますCityB

distance(City1,City2,Distance)

事実。これまでになんとかできたことは以下のとおりですが、常にバックトラックしwrite(X),て最終的な反復で完了します。これは、私がやりたいことですが、ある程度だけです。

たとえば、行き止まりになっている都市名を出力したり、最終的な繰り返しを使用したりしたくありません。基本的に からCityAまでのパスを作成CityBし、そのパス上に移動先の都市の名前を書きます。

誰かが私を助けてくれることを願っています！

all_possible_paths(CityA, CityB) :-
    write(CityA),
    nl,
    loop_process(CityA, CityB).

loop_process(CityA, CityB) :- 
    CityA == CityB.
loop_process(CityA, CityB) :-
    CityA \== CityB,
    distance(CityA, X, _),
    write(X),
    nl,
    loop_process(X, CityB).
4

3 に答える 3

8

どのように機能するかをよりよく理解できるように、取り組んでいることをどのように達成できるかを実証しようとしました。あなたのOPはあまり完全ではなかったので、私はいくつかの自由を取りました! ここに私が取り組んでいる事実があります:

road(birmingham,bristol, 9).
road(london,birmingham, 3).
road(london,bristol, 6).
road(london,plymouth, 5).
road(plymouth,london, 5).
road(portsmouth,london, 4).
road(portsmouth,plymouth, 8).

これが、パスを見つけるために呼び出す述語get_road/4です。これは基本的に、2 つのアキュムレータ (1 つは既に訪れたポイント用、もう 1 つは通過した距離用) を持つ作業述語を呼び出します。

get_road(Start, End, Visited, Result) :-
    get_road(Start, End, [Start], 0, Visited, Result).

get_road (+Start, +End, +Waypoints, +DistanceAcc, -Visited,
-TotalDistance ) :
最初の節は、最初の地点と最後の地点の間に道路がある場合、ここで終了できます。

get_road(Start, End, Waypoints, DistanceAcc, Visited, TotalDistance) :-
    road(Start, End, Distance),
    reverse([End|Waypoints], Visited),
    TotalDistance is DistanceAcc + Distance.

2 番目の節は、最初のポイントと中間ポイントの間に道路がある場合、それを取得して get_road(intermediate, end) を解決できることを示しています。

get_road(Start, End, Waypoints, DistanceAcc, Visited, TotalDistance) :-
    road(Start, Waypoint, Distance),
    \+ member(Waypoint, Waypoints),
    NewDistanceAcc is DistanceAcc + Distance,
    get_road(Waypoint, End, [Waypoint|Waypoints], NewDistanceAcc, Visited, TotalDistance).

使用方法は次のとおりです。

?- get_road(portsmouth, plymouth, Visited, Distance).

そして利回り：

Visited = [portsmouth, plymouth],
Distance = 8 ;
Visited = [portsmouth, london, plymouth],
Distance = 9 ;
Visited = [portsmouth, plymouth, london, plymouth],
Distance = 18 ;
false.

お役に立てば幸いです。

于 2011-11-29T22:57:33.013 に答える
4

純粋な部分を不純な部分から分離してください（I / O、のようwrite/1に、だけでなく、nl/0も）。それらがあなたの純粋なコードと完全にインターレースされている限り、あなたは多くを期待することはできません。(==)/2(\==)/2

おそらく、開始点、終了点、およびそれらの間のパスの間の関係が必要です。

そのパスは非周期的である必要がありますか、それともサイクルを許可しますか？

要素Xがリストに含まれないようにするにXsは、目標を使用しmaplist(dif(X),Xs). ます。これを適切な関係にするために、これ以上の補助述語は必要ありません。

于 2011-11-29T22:43:56.270 に答える
1

成功したリストを all_possible_paths の Out 変数として返す必要があります。次に、そのリストを書き出します。同じ手順で両方を実行しないでください。

于 2011-11-29T22:10:35.187 に答える