Uprzejmy podróżujący sprzedawca w Prologu

Question

Przejrzałem podobne pytania, ale nie znalazłem niczego, co byłoby istotne dla mojego problemu. Mam trudności ze znalezieniem algorytm lub zestaw „pętli”, że znajdzie drogę od CityA do CityB, wykorzystując bazę

distance(City1,City2,Distance) 

faktów. To, co udało mi się zrobić do tej pory, jest poniżej, ale zawsze cofa się pod numerem write(X),, a następnie kończy się ostatnią iteracją, która jest tym, co chcę, ale tylko w pewnym stopniu.

Na przykład nie chcę, aby wydrukował nazwy miast będących ślepymi zaułkami lub używał końcowej iteracji. Chcę, żeby to była ścieżka od CityA do CityB, pisząc nazwy miast, do których się udaje na ścieżce.

Mam nadzieję, że ktoś może mi pomóc!

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

Próbowałem pokazać, w jaki sposób możesz osiągnąć to, nad czym pracujesz, abyś mógł lepiej zrozumieć, jak działa. Ponieważ twój OP nie był bardzo kompletny, skorzystałem z pewnych swobód! Oto fakty pracuję z:

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

tutaj jest orzecznikiem będziemy nazywać znaleźć nasze ścieżki, get_road/4. Zasadniczo wywołuje on działający predykat, który ma dwa akumulatory (jeden dla punktów już odwiedzonych i jeden dla dystansu, przez który przeszliśmy).

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

Oto orzeczenie roboczego,
get_road/6: get_road (+ start + End, + Punkty, + DistanceAcc, -Visited, -TotalDistance):
Pierwsza klauzula mówi, że jeśli istnieje droga między naszym pierwszym punktem a naszym ostatnim punktem, możemy zakończyć tutaj.

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

Druga klauzula mówi, że jeśli nie jest to droga pomiędzy naszym pierwszym punktem a punktem pośrednim, możemy wziąć go, a następnie rozwiązać get_road (półprodukt, koniec).

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

użycia jest następujący:

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

a rentowności:

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

Mam nadzieję, że będzie pomocne dla Ciebie.

Answer 2

Powinieneś zwrócić udaną listę jako zmienną Out w all_possible_paths. Następnie zapisz tę listę. Nie rób obu w tej samej procedurze.

Answer 3

Rozdziel czystą część z zanieczyszczonego (I/O, takie jak write/1, nl/0 ale także (==)/2 i (\==)/2). Dopóki są one całkowicie splecione z czystym kodem, nie można oczekiwać wiele.

Prawdopodobnie potrzebujesz relacji między punktem początkowym, punktem końcowym i ścieżką pomiędzy.

Czy ta ścieżka powinna być acykliczna , czy może zezwolić na cykle ?

Aby upewnić się, że elementem X nie występuje na liście Xs użyć cel maplist(dif(X),Xs). Nie potrzeba żadnych dodatkowych predykatów pomocnicze, aby ten miły relacja!