Vendedor de viaje simplificado en Prolog

Question

He revisado las preguntas similares pero no puedo encontrar nada relevante para mi problema. Estoy luchando por encontrar un algoritmo o un conjunto de 'bucles' que encuentren un camino de CityA a CityB, usando una base de datos de

distance(City1,City2,Distance)

hechos. Lo que he logrado hacer hasta ahora está a continuación, pero siempre retrocede a write(X), y luego se completa con la iteración final, que es lo que quiero que haga, pero solo hasta cierto punto.

Por ejemplo, no quiero que imprima los nombres de la ciudad que sean callejones sin salida o que usen la iteración final. Quiero que básicamente haga un camino desde CityA a CityB, escribiendo el nombre de las ciudades a las que va en el camino.

¡Espero que alguien pueda ayudarme!

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

Traté de demostrar cómo puedes lograr en qué estás trabajando para que puedas entender mejor cómo funciona. Entonces, dado que tu OP no estaba muy completo, ¡me tomé algunas libertades! Aquí están los hechos con los que estoy trabajando:

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

Aquí está el predicado que llamaremos para encontrar nuestros caminos, get_road/4. Básicamente llama al predicado de trabajo, que tiene dos acumuladores (uno para los puntos ya visitados y otro para la distancia que pasamos).

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

Aquí está el predicado de trabajo,
get_road/6 : get_road ( +start, +fin, +waypoints, +distanceAcc, -wisitado, -totalDistance):
La primera cláusula dice que si hay un camino entre nuestro primer punto y nuestro último punto, podemos terminar aquí.

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

La segunda cláusula dice que si hay un camino entre nuestro primer punto y un punto intermedio, podemos tomarlo y luego resolver get_road (intermedio, final).

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

El uso es el siguiente:

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

Y rendimientos:

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

Espero que te sea útil.

Answer 2

Por favor, separe la parte pura del impuro (E/S, como write/1, nl/0 pero también (==)/2 y (\==)/2). Mientras estén completamente entrelazados con su código puro, no puede esperar mucho.

Probablemente desee una relación entre un punto de partida, un punto final y una ruta intermedia.

Debería ese camino ser acíclico o permites ciclos?

Para garantizar que un elemento X no ocurre en una lista Xs Usa el objetivo maplist(dif(X),Xs).¡No necesita más predicados auxiliares para que esta sea una buena relación!

Answer 3

Debe devolver una lista exitosa como una variable de salida en All_Possible_Paths. Luego escriba esa lista. No hagas ambas cosas en el mismo procedimiento.