prolog - 通过corecursion解决Prolog中的动态规划

Question

我想解决以下动态规划problem通过 corecursion在序言中。但是我坚持以递归方式进行广度优先搜索，我想实现它:

There is a building of n floors with an elevator that can only go up 2 floors at a time and down 3 floors at a time. Using dynamic programming write a function that will compute the number of steps it takes the elevator to get from floor i to floor j.

我已经决定使用惰性列表表示。一个惰性列表只是一个 Prolog 闭包 C，它可以被调用以产生一个头部和一个新的尾部闭包。

示例流:

 one(1, one).

Haskell take 谓词可以简单地编码如下:

 take(0, _, L) :- !, L = [].
 take(N, C, [X|L]) :- N > 0, 
    call(C, X, D), 
    M is N-1, 
    take(M, D, L). 

这是一个示例运行:

 ?- take(5, one, X).
 X = [1, 1, 1, 1, 1].

 ?- take(10, one, X).
 X = [1, 1, 1, 1, 1, 1, 1, 1, 1|...].

Answer 1

在这个共同递归的序言中 solution我们需要两个积木。

一个构建块是一种在 Prolog 中共同递归枚举搜索树的方法。我们采用这样的想法，即 Prolog 闭包项应该带有一个带有路径的议程，因此应该扩展节点。然后我们可以从一个只包含根的议程开始:

% tree(-Path, -LazyPaths)
tree(H, T) :-
   tree([[]], H, T). 

为了存档广度优先枚举，我们将在议程的末尾附加新的扩展路径和节点。这可以通过一个简单的列表附加谓词调用来完成，因此缺失的定义如下所示。在完整的二叉树路径中，节点总是被扩展两次:

% tree(+Paths, -Path, -LazyPaths)
tree([X|Y], X, tree(Z)) :-
   append(Y, [[0|X],[1|X]], Z). 

这是一个示例运行:

?- take(5, tree, L).
L = [[],[0],[1],[0,0],[1,0]]

?- take(10, tree, L).
L = [[],[0],[1],[0,0],[1,0],[0,1],[1,1],[0,0,0],[1,0,0],[0,1,0]] 

在评估器问题的情况下，我们将有一个路径，因此节点扩展不会总是导致两个后继。如果我们在 k 层，电梯可以到达 k+2 或 k-3 层，前提是电梯停留在建筑物内。所以我们很容易地得出一个共同递归谓词步骤，它确实模拟了电梯的所有可能路径:

?- take(5, steps(7,[[2]]), L).
L = [[2],[4,2],[1,4,2],[6,4,2],[3,1,4,2]]

?- take(10, steps(7,[[2]]), L).
L = [[2],[4,2],[1,4,2],[6,4,2],[3,1,4,2],[3,6,4,2],
    [5,3,1,4,2],[5,3,6,4,2],[2,5,3,1,4,2],[7,5,3,1,4,2]]

最后一个障碍和第二个构建块是在 Prolog 中获得 Haskell dropWhile。我们的目标不是针对 bool 条件采用 Prolog 闭包项参数的谓词，而是仅提供一个枚举惰性列表元素的谓词，并且该谓词的用户可以在 Prolog 延续中进行过滤。

% drop_while(+LazyList, -Element)
drop_while(C, P) :-
   call(C, Q, T),
   (P = Q; drop_while(T, P)).

如果我们把所有东西放在一起，我们会得到一个共同递归的 Prolog 解决方案，除了以广度一阶计算结果之外，它甚至可以通过回溯潜在地枚举评估器问题的所有无限解决方案:

?- elevator(7,2,6,L), length(L,N).
L = [6,4,2],
N = 3 ;
L = [6,4,2,5,3,1,4,2],
N = 8 ;
L = [6,4,7,5,3,1,4,2],
N = 8