Prologの簡素化された巡回セールスマン

Question

私は同様の質問を調べましたが、私の問題に関連するものは何も見つかりません。私は、からのパスを見つける「ループ」のアルゴリズムまたはセットを見つけるのに苦労しています 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).

Answer 1

私は、あなたが取り組んでいることをどのように達成できるかを実証しようとしました。あなたの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/6 ：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（中間、終了）を解くことができることを示しています。

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.

それがあなたに役立つことを願っています。

Answer 2

純粋な部分を不純なものから分離してください（i/o、 write/1, nl/0 だけでなく、 (==)/2 と (\==)/2）。それらがあなたの純粋なコードと完全に絡み合っている限り、あなたはあまり期待することはできません。

おそらく、出発点、エンドポイント、その間のパスの間の関係が必要です。

その経路が非環式である必要があります または、サイクルを許可しますか?

その要素を確保するため X リストには発生しません Xs 目標を使用します maplist(dif(X),Xs).これを素晴らしい関係にするために、これ以上の補助的な述語は必要ありません！

Answer 3

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