Viaggiare semplificata Salesman in Prolog
-
25-10-2019 - |
Domanda
Ho guardato attraverso le domande simili, ma non riesce a trovare tutto ciò che è rilevante per il mio problema. Sto lottando per trovare un algoritmo o un insieme di 'loop' che troveranno un percorso da CityA
a CityB
, utilizzando un database di
distance(City1,City2,Distance)
fatti. Quello che sono riuscito a fare finora è al di sotto, ma sempre Backtracks a write(X),
e poi completa con l'iterazione finale, che è quello che voglio fare, ma solo in una certa misura.
Per esempio, io non lo voglio per stampare tutti i nomi della città che sono vicoli ciechi, o di utilizzare l'iterazione finale. Voglio che fare fondamentalmente un percorso da CityA
a CityB
, scrivendo il nome delle città va a sulla strada.
Spero che qualcuno mi può aiutare!
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).
Soluzione
I tried to demonstrate how you can achieve what you're working on so that you can understand better how it works. So since your OP wasn't very complete, I took some liberties ! Here are the facts I'm working with :
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).
Here is the predicate we will call to find our paths, get_road/4. It basically calls the working predicate, that has two accumulators (one for the points already visited and one for the distance we went through).
get_road(Start, End, Visited, Result) :-
get_road(Start, End, [Start], 0, Visited, Result).
Here is the working predicate,
get_road/6 : get_road(+Start, +End, +Waypoints, +DistanceAcc, -Visited, -TotalDistance) :
The first clause tells that if there is a road between our first point and our last point, we can end here.
get_road(Start, End, Waypoints, DistanceAcc, Visited, TotalDistance) :-
road(Start, End, Distance),
reverse([End|Waypoints], Visited),
TotalDistance is DistanceAcc + Distance.
The second clause tells that if there is a road between our first point and an intermediate point, we can take it and then solve 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).
Usage is as follows :
?- get_road(portsmouth, plymouth, Visited, Distance).
And yields :
Visited = [portsmouth, plymouth],
Distance = 8 ;
Visited = [portsmouth, london, plymouth],
Distance = 9 ;
Visited = [portsmouth, plymouth, london, plymouth],
Distance = 18 ;
false.
I hope it will be helpful to you.
Altri suggerimenti
Please separate the pure part from the impure (I/O, like write/1
, nl/0
but also (==)/2
and (\==)/2
). As long as they are entirely interlaced with your pure code you cannot expect much.
Probably you want a relation between a starting point, an end point and a path in between.
Should that path be acyclic or do you permit cycles?
To ensure that an element X
does not occur in a list Xs
use the goal maplist(dif(X),Xs).
You do not need any further auxiliary predicates to make this a nice relation!
You should return a successful list as an Out variable in all_possible_paths. Then write out that list. Don't do both in the same procedure.