7

我试图call_with_depth_limit/3在 SWI-Prolog 中使用来实现迭代深化，要么我不明白它是如何工作的，要么它行为不端。我有一个发生以下情况的示例：

?- call_with_depth_limit(mygoal, 29, Result).
Result = 29 ;
Result = 25 ;
Result = 27 ;
Result = 27 ;
false.

?- call_with_depth_limit(mygoal, 26, Result).
Result = depth_limit_exceeded ;
false.

根据文档，如果可以使用 Limit max recursion 或更少来证明目标，它应该会成功。在第一个限制为 30 的调用中，我们看到 Result 为 25 的结果，因此我希望以 26 的限制调用它会成功。我在模块中使用约束处理规则，以防那里可能存在一些使其行为不端的交互。

编辑：玩过伊莎贝尔的回答后，我想我明白它的行为方式：

  • 它像往常一样运行深度优先搜索，但如果它达到 Limit+1 深度，它就像失败一样。
  • 失败的分支计入结果。
  • 每次它在成功回答后回溯时，都会将 Result 重置为堆栈的当前深度。

看这个例子：

loop :- loop.

succeed(0).
succeed(N) :- N > 0, N1 is N - 1, succeed(N1).

fail(N) :- N > 0, N1 is N - 1, fail(N1).

?- call_with_depth_limit(succeed(0), 1000, Result).
Result = 1 ;
false.

?- call_with_depth_limit(fail(50);succeed(0), 1000, Result).
Result = 53 ;
false.

% It tries loop until Limit+1 and therefore this is the Result
?- call_with_depth_limit(loop;succeed(0), 1000, Result).
Result = 1001 ;
false.

% In the second result it has to unroll the stack from 100 before trying the next, so Result is 100.
?- call_with_depth_limit(loop;succeed(100);succeed(0), 1000, Result).
Result = 1001 ;
Result = 103 ;
false.

?- call_with_depth_limit(loop;succeed(0);succeed(0), 1000, Result).
Result = 1001 ;
Result = 3 ;
false.

% If it gets to the end, and it has reached Limit+1 since the last successful result it returns depth_limit_exceeded.
?- call_with_depth_limit(loop;succeed(100);succeed(0);loop, 1000, Result).
Result = 1001 ;
Result = 103 ;
Result = depth_limit_exceeded.
4

4 回答 4

8

我不相信 SWI-Prolog 甚至实现了自己的call_with_depth_limit/3. 至少我读到：

如果 Goal 可以在没有比 Limit 级别更深的递归的情况下被证明，则 call_with_depth_limit/3 成功，将 Result 绑定到证明期间使用的最深递归级别。否则，如果在证明期间超出限制，则 Result 与 depth_limit_exceeded 统一...

暗示Result永远不会大于Limit。但是有了这个程序：

succeed_with_depth(3) :-
    succeed(3).
succeed_with_depth(1) :-
    succeed(1).

succeed(0).
succeed(N) :-
    N > 0,
    N1 is N - 1,
    succeed(N1).

我观察到（SWI-Prolog 7.6.4）：

?- call_with_depth_limit(succeed_with_depth(N), 5, Result).
N = 3,
Result = 5 ;
N = 1,
Result = 6 ;
false.

证明更浅的目标会导致更深的递归。超出限制但仍然成功的递归。

就个人而言，阅读文档我希望获得与succeed_with_depth(1)直接调用它时相同的深度来证明回溯：

?- call_with_depth_limit(succeed_with_depth(1), 5, Result).
Result = 3 ;
false.

或者可能在最外层添加 1 个深度用于回溯succeed_with_depth？那仍然应该给Result = 4而不是6。

编辑：正如 rajashekar 在评论中指出的那样，在第一个子句中添加一个剪切，succeed/1将意外行为更改为预期行为。我认为这进一步表明 SWI-Prolog 的行为已被破坏：唯一的区别是删除了一个在回溯时将立即失败的选择。在任何后续计算中都没有实际的更深层次的递归。

编辑2：为了说明我为此想象的语义很简单，并且它实际上可以用于实现迭代深化，这里有一个小的元解释器，它足够强大，可以从上面执行我的程序：

interpret_with_depth_limit(Goal, Limit, Result) :-
    interpret_with_depth_limit(Goal, 0, Limit, Result).

interpret_with_depth_limit(_Goal, Current, Limit, depth_limit_exceeded) :-
    Current >= Limit,
    !.
interpret_with_depth_limit(Builtin, N, _Limit, N) :-
    builtin(Builtin),
    !,
    call(Builtin).
interpret_with_depth_limit((A, B), N, Limit, Result) :-
    !,
    interpret_with_depth_limit(A, N, Limit, ResultA),
    integer(ResultA),
    interpret_with_depth_limit(B, N, Limit, ResultB),
    integer(ResultB),
    Result is max(ResultA, ResultB).
interpret_with_depth_limit(Goal, N, Limit, Result) :-
    N1 is N + 1,
    N1 < Limit,
    clause(Goal, Body),
    interpret_with_depth_limit(Body, N1, Limit, Result).

builtin(true).
builtin(_ > _).
builtin(_ is _).

这不会在回溯中保留深度信息，因此回溯的行为与调用更具体的目标实例时相同：

?- interpret_with_depth_limit(succeed_with_depth(N), 6, Result).
N = 3,
Result = 5 ;
N = 1,
Result = 3 ;
false.

?- interpret_with_depth_limit(succeed_with_depth(3), 6, Result).
Result = 5 ;
false.

?- interpret_with_depth_limit(succeed_with_depth(1), 6, Result).
Result = 3 ;
false.

迭代深化，以正确的顺序准确地找到每个答案一次（即，首先是最浅的证明），然后是：

call_succeedingdepth(Goal, Depth) :-
    between(1, infinite, Limit),
    Depth is Limit - 1,
    interpret_with_depth_limit(Goal, Limit, Depth).

测试：

?- call_succeedingdepth(succeed_with_depth(N), Depth).
N = 1,
Depth = 3 ;
N = 3,
Depth = 5 ;
% nontermination

我不认为关于不终止的事情可以做任何事情。你通常会在有无数个答案的目标上使用它。

于 2020-12-21T16:04:59.397 回答
5

我试图call_with_depth_limit/3通过使用这个程序来理解它是如何工作的：

%           a        <- 1st call
%         /   \
%        b     g     <- 2nd call
%       /
%      c             <- 3rd call
%     / \
%    g   d           <- 4th call
%        |
%        e           <- 5th call

arc(a, b).
arc(a, g).
arc(b, c).
arc(c, g).
arc(c, d).
arc(d, e).

path(X, X, [X]).
path(X, Z, [X|R]) :- arc(X, Y), path(Y, Z, R).

获得的结果：

?- call_with_depth_limit(path(a,g,P), 4, D).
P = [a, b, c, g],
D = 4 ;
P = [a, g],
D = 5 ;
false.

答案似乎是：

  • P = [a, b, c, g], D = 4意味着 4 次调用以获得第一个解决方案。
  • P = [a, g], D = 5意味着 5 次调用以获得第二个解决方案（请注意，在获得第二个解决方案之前，[a,b,c,d,e]必须探索失败路径并且第 5 次调用导致失败 - 这个事实证明了答案是正确的D = 5）。

另一个查询：

?- call_with_depth_limit(path(a,g,P), 3, D).
P = [a, g],
D = 4 ;
false.

我们可以看到搜索在 4 次调用 ( D = 4) 后回溯，但获得解决方案所需的第四次调用[a,b,c,g]导致失败（因为depth_limit是 3）并且没有产生结果。

[编辑] 另一种场景： 在这个新场景中，在谓词的第一个子句中添加了一个剪切，path/3以避免扩展已经是解决方案的路径（否则，搜索将尝试在同一路径中再向下一步，并且在找到第二个解决方案之前会以深度 5 失败）。

%           a        <- 1st call
%         /   \
%        b     g     <- 2nd call
%       /
%      c             <- 3rd call
%     /
%    g               <- 4th call
%
%                    <- 5th call

arc(a, b).
arc(a, g).
arc(b, c).
arc(c, g).

path(X, X, [X]) :- !.
path(X, Z, [X|R]) :- arc(X, Y), path(Y, Z, R).

在这个新场景中，我们有：

?- call_with_depth_limit(path(a,g,P), 4, D).
P = [a, b, c, g],
D = 4 ;
P = [a, g],
D = 2.

我们观察到：

  • 在第二种情况下，找到第二种解决方案所达到的最深递归级别是 2。

  • 但是，在第一种情况下，找到第二个解决方案的最深递归级别是 5，因为在找到第二个解决方案之前，搜索必须尝试扩展路径[a,b,c,g]并探索路径[a,b,c,d,e]（因此，在证明过程中使用的最深递归级别解决方案[a,g]是 5）。

重要的是要注意，正如 SWI-Prolog 文档中所述，Result它绑定到在证明特定解决方案期间使用的最深递归级别，而不是找到该解决方案的级别。

call_with_depth_limit(:Goal, +Limit, -Result) 如果 Goal 可以在没有比 Limit 级别更深的递归的情况下被证明，则 call_with_depth_limit/3 成功，将 Result 绑定到证明期间使用的最深递归级别。否则，如果在证明过程中超过限制，则 Result 与 depth_limit_exceeded 统一，或者如果 Goal 失败但未超过 Limit，则整个谓词失败。

迭代深化深度优先搜索

找到 的最浅解Goal，但不超过Limit：

ids(Goal, Limit) :-
    between(1, Limit, Depth),
    call_with_depth_limit(Goal, Depth, Result),
    Result \= depth_limit_exceeded,
    !.

以下是一些示例（两种情况的答案相同）：

?- ids(path(a,g,P), inf).
P = [a, g].

?- ids(path(a,g,P), 10).
P = [a, g].

?- ids(path(a,g,P), 2).
P = [a, g].

?- ids(path(a,g,P), 1).
false.
于 2020-12-21T17:25:30.683 回答
3

不就是第一个成功的结果需要29的深度，这显然是过分了，然后就吹了？然后将永远不会尝试下一个需要深度为 25 的结果。

于 2020-12-21T14:52:08.680 回答
0

根据SWI 文档，

深度限制由内部机械保护。这可能与基于理论模型计算的深度不同。[...] 因此， call_with_depth_limit/3 可能仍会在理论上应该在有限时间内完成的程序上无限循环。

所以它的“深度”不同于基于理论模型计算的深度。

于 2020-12-22T19:43:51.123 回答