«Возвращение» списка из предиката в Прологе - PullRequest
Новая
       9

«Возвращение» списка из предиката в Прологе

3 голосов
/ 06 октября 2010 
resolve(K, K, _) :- writeln('finished'). %goal state

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

В настоящее время у меня есть этот алгоритм, и он работает как надо.Я запускаю его так: 

resolve(0, 10, Path).

Я точно знаю, что алгоритм работает должным образом, он достигает состояния цели, хотя значение Path равно 

Path = []

что не должно случиться.Путь должен содержать последовательность «состояний», в которых прошел мой алгоритм.В чем может быть проблема?

Ответы [ 3 ]

5 голосов
/ 07 октября 2010

Для описания списка проще всего использовать нотацию DCG: 

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

Вы также можете сделать это вручную: 

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

Здесь нет необходимости в аккумуляторах для получения линейного времени.

1 голос
/ 06 октября 2010

Я считаю, что есть проблема в том, как вы хотите построить Путь.Возможно, вы захотите переписать его, чтобы встроить его в заголовок вашего предиката.Примерно так: 

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

Первое предложение завершает рекурсию: чтобы перейти из состояния K в состояние K, вы возвращаете [] в качестве пути, поскольку вы уже находитесь в состоянии цели.Во втором предложении строится путь, он получает следующее состояние и вызывает рекурсивное разрешение, создавая путь, пройденный вами после завершения рекурсии.

0 голосов
/ 06 октября 2010

Должен ли термин NextPath в вашем предикате append быть NewPath?

В настоящее время нет никакого другого использования NextPath, поэтому Path должен быть привязан к [], потому что NextPath может полностью привязаться к [CurrentState].

...