Prologのセールスマン簡素化

Question

私は同様の質問を見てきましたが、私の問題に関連するものは見つかりませんでした。私は

distance(City1,City2,Distance) 

事実のデータベースを使用して、CityAからCityBへのパスを見つける「ループ」のアルゴリズムまたはセットを見つけるのに苦労しています。私がこれまでにやったことは以下の通りですが、それはいつも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つは距離をとっています）。ここで

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

は、作業述語、
get_road/6です：get_road（+スタート、+終了、+ウェイポイント、+ DistanceAcc、-Visited、-TotalDistance）：
最初の句があればということ伝えます私たちの最初の点と最後の点の間に道があり、ここで終えることができます。

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

第二句は、我々の最初の点と中間点との間に道路がある場合、我々はそれを取ると、その後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

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

Answer 3

不純から純粋な部分を分離してください（I/O、write/1、nl/0も(==)/2と(\==)/2など）。それらが完全にあなたの純粋なコードと織り交ぜられている限り、あなたはあまり期待できません。

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

このパスは非循環型であるべきですか またはサイクル を許可しますか？

ゴールmaplist(dif(X),Xs). を使用する要素XがリストXsでは生じないことを確実にするために、あなたは、この素敵な関係を作るために任意のさらなる補助述語を必要としません！