Vereinfachte reisende Verkäufer im Prolog

Question

Ich habe die ähnlichen Fragen durchgesehen, kann aber nichts finden, was für mein Problem relevant ist. Ich kämpfe darum, einen Algorithmus oder eine Reihe von 'Loops' zu finden, die einen Weg finden werden CityA zu CityB, mit einer Datenbank von

distance(City1,City2,Distance)

Fakten. Was ich bisher geschafft habe, ist unten, aber es ist immer zurückgekehrt bei write(X), Und schließt dann mit der endgültigen Iteration ab, was ich tun möchte, aber nur in gewissem Maße.

Zum Beispiel möchte ich nicht, dass es städtische Namen ausdrucken, die Sackgassen sind, oder die endgültige Iteration verwenden. Ich möchte, dass es grundsätzlich einen Weg ausgeht CityA zu CityB, schreiben Sie den Namen der Städte, auf den es auf dem Weg geht.

Ich hoffe, jemand kann mir helfen!

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

Ich habe versucht zu demonstrieren, wie Sie das erreichen können, woran Sie arbeiten, damit Sie besser verstehen können, wie es funktioniert. Da Ihr OP nicht sehr vollständig war, habe ich einige Freiheiten genommen! Hier sind die Fakten, mit denen ich arbeite:

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

Hier ist das Prädikat, das wir anrufen werden, um unsere Wege zu finden. get_road/4. Grundsätzlich nennt es das funktionierende Prädikat, das zwei Akkumulatoren hat (eine für die bereits besuchten Punkte und eine für die Entfernung, die wir durchgemacht haben).

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

Hier ist das funktionierende Prädikat,
get_road/6 : get_road ( +Start, +Ende, +Wegpunkte, +DistanceAcc, -besucht, -Totaldistanz):
Die erste Klausel zeigt, dass wir hier enden können, wenn es eine Straße zwischen unserem ersten und unserem letzten Punkt gibt.

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

Die zweite Klausel zeigt, dass wir sie nehmen und dann Get_Road lösen können (Zwischenprodukt, Ende), wenn es eine Straße zwischen unserem ersten Punkt und einem Zwischenpunkt gibt.

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

Die Verwendung ist wie folgt:

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

Und liefert:

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

Ich hoffe, es wird Ihnen hilfreich sein.

Answer 2

Bitte trennen Sie den reinen Teil von der unreinen (i/o, wie write/1, nl/0 aber auch (==)/2 und (\==)/2). Solange sie vollständig mit Ihrem reinen Code verbunden sind, können Sie nicht viel erwarten.

Wahrscheinlich möchten Sie eine Beziehung zwischen einem Ausgangspunkt, einem Endpunkt und einem Weg dazwischen.

Sollte dieser Weg acyclisch sein oder erlauben Sie Zyklen?

Um sicherzustellen, dass ein Element X tritt nicht in einer Liste auf Xs Verwenden Sie das Ziel maplist(dif(X),Xs).Sie brauchen keine weiteren Hilfsprädikate, um dies zu einer schönen Beziehung zu machen!

Answer 3

Sie sollten eine erfolgreiche Liste als Out -Variable in All_Possible_Paths zurückgeben. Schreiben Sie dann diese Liste auf. Machen Sie nicht beides in derselben Prozedur.