1

所以我有一项任务要处理，但我对一件事感到困惑。这是与我要完成的任务类似的问题。假设我有这些规则：

size(3).
size(5).
size(7).
size(1).
size(2).
size(9).

我想通过取值 3 并将其与 5 进行比较、存储 3 并将其与 7 进行比较、然后将其与 1 进行比较、存储 1 并将其与 2 进行比较...返回值 1 来找到最小的大小。

在没有高阶过程的情况下，我能看到的唯一方法是某种形式的回溯，同时仍然存在 size(X) 值并且每次都更改 size 变量。但是，我看不出您如何既可以回溯又可以保存新的最小值。我想知道是否有人可以帮助我走上正轨。

4

1 回答 1

3

你的作业旨在让你思考 Prolog 的特殊控制流程，事实上你现在已经到了重点。我已经对解决方案进行了编码并添加了一些解释性注释：填写省略号以完成代码

find_min_size(MinSize) :-
    size(Hypothesis),
    !,  % without this cut the minimum is obtained more times...
    find_min_size(Hypothesis, MinSize).

find_min_size(SoFar, MinSize) :-
    % when I should keep searching?
    ...

% the exhaustive search come to end!
find_min_size(MinSize, MinSize).

我认为在 Prolog 中不可能获得 O(N) 性能，没有“高阶程序”（你的意思是 findall 等吗？）。上面的代码将以 O(N^2) 运行。索引无法发挥作用，因为 size/1 将使用未绑定的变量重新启动...

一个有趣的 O(N) 替代方案是使用故障驱动循环和 @false 在介绍call_nth时解释得很好的技术（另请参阅此处的后续内容）。所有这些都在 Prolog 的“不纯”领域，虽然......

在此处编辑故障驱动循环

find_min_size(MinSize) :-
    State = (_, _),
    (   size(V),
        arg(1, State, C),
        ( ( var(C) ; V < C ) -> U = V ; U = C ),
        nb_setarg(1, State, U),
        fail
    ;   arg(1, State, MinSize)
    ).
于 2012-11-27T07:41:23.407 回答