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

我目前有这个算法，它可以正常工作。我这样运行它：

resolve(0, 10, Path).

我确定该算法正在按应有的方式运行，它达到了目标状态，尽管Path的值为

Path = []

这不是应该发生的事情。路径应该包含我的算法通过的“状态”序列。可能是什么问题？

Answer 1

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

这里不需要累加器来获得线性时间。

Answer 2

我相信您想要构建路径的方式存在问题。您可能想要重写它，以便在谓词的头部构建它。像这样的东西：

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

第一个子句结束递归：从状态 K 转到状态 K，您返回 [] 作为路径，因为您已经处于目标状态。第二个子句构建路径，它获取下一个状态并递归调用解析，在递归完成时构建您遍历的路径。

Answer 3

谓词中NextPath的术语应该是？appendNewPath

目前没有任何其他用法NextPathso Pathmust be binding to[]因为NextPath能够完全绑定到[CurrentState].