"Retour" une liste d'un prédicat dans Prolog

Question

resolve(K, K, _) :- writeln('finished'). %goal state 

resolve(CurrentState, GoalState, Path) :- 
    suc(_, CurrentState, NextState, GoalState), 
    append(Path, [CurrentState], NextPath), 
    resolve(NextState, GoalState, NewPath). 

J'ai actuellement cet algorithme, et il fonctionne comme il se doit. Je courais comme ceci:

resolve(0, 10, Path). 

Je sais avec certitude que l'algorithme fonctionne comme il se doit, il arrive à l'état de but, bien que la valeur de l » Path est

Path = [] 

qui n'est pas Que devrait-il se passer? Chemin doit contenir la séquence des "états" dans lesquels mon algorithme a passé. Quel pourrait être le problème?

Answer 1

Il est plus facile d'utiliser la notation DCG pour décrire la liste:

path(State0, Target) --> 
    ( { State0 == Target } -> [] 
    ; { suc(_, State0, State1, Target) }, 
     [State1], 
     path(State1, Target) 
    ). 

Vous pouvez aussi le faire manuellement:

path(State0, Target, Path) :- 
    ( State0 == Target -> Path = [] 
    ; suc(_, State0, State1, Target), 
     Path = [State1|Rest], 
     path(State1, Target, Rest) 
    ). 

Il n'y a pas besoin d'accumulateurs ici pour obtenir le temps linéaire.

Answer 2

Est-ce que le terme NextPath dans votre append est NewPath?

Actuellement il n'y a pas d'autre utilisation de NextPath si Path doit lier à [] car NextPath est capable de se lier pleinement à [CurrentState].

Answer 3

Je crois qu'il y a un problème dans la façon dont vous voulez construire le Chemin. Vous pourriez vouloir le réécrire afin de le construire dans la tête de votre prédicat. Quelque chose comme ceci:

resolve(K, K, []) :- writeln('finished'). %goal state 
resolve(CurrentState, GoalState, [CurrentState|Path]) :- 
    suc(_, CurrentState, NextState, GoalState), 
    resolve(NextState, GoalState, Path). 

La première clause se termine la récursion: aller de l'état K à dire K vous revenez [] comme le chemin que vous êtes déjà dans l'état de l'objectif. La deuxième clause construit le chemin, il obtient l'état suivant et les appels se résolvent de façon récursive, en construisant le chemin que vous avez traversé lorsque la récursion se termine.