Vendedor ambulante simplificado en Prolog

Question

He revisado las preguntas similares pero no encuentro nada que sea relevante para mi problema. Estoy luchando para encontrar un algoritmo o conjunto de bucles '' que encontrarán un camino desde CityA a CityB, utilizando una base de datos de

distance(City1,City2,Distance) 

hechos. Lo que he logrado hacer hasta ahora está debajo, pero siempre retrocede al 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 se impriman nombres de ciudades que son callejones sin salida, o para usar la iteración final. Quiero que básicamente haga una ruta desde CityA hasta CityB, escribiendo el nombre de las ciudades a las que va en la ruta.

¡Espero que alguien me pueda ayudar!

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

Intenté demostrar cómo puede lograr lo que está trabajando para que pueda comprender mejor cómo funciona. ¡Como tu OP no era muy completo, me tomé algunas libertades! Estos son los hechos los que trabajo:

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í es 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 atravesamos).

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

Aquí es el predicado de trabajo,
get_road/6: get_road (+ Inicio, Fin +, + waypoints, + DistanceAcc, -Visited, -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 el primer punto y un punto intermedio, podemos tomar y luego resolvemos get_road (intermedia y 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). 

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 será útil para usted.

Answer 2

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

Answer 3

favor separar la parte puro de lo impuro (E/S, como write/1, nl/0 sino también (==)/2 y (\==)/2). Siempre y cuando estén completamente entrelazados con tu código puro no puedes esperar mucho.

Probablemente desea una relación entre un punto de inicio, un punto final y un camino intermedio.

¿Debería esa ruta ser acíclica o permitir ciclos ?

Para garantizar que un elemento X no se produce en una lista Xs utilizar el objetivo maplist(dif(X),Xs). que no es necesario ningún predicados auxiliares adicionales para hacer de esta una buena relación!