Joa*_*oan 7 prolog swi-prolog iterative-deepening
我试图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.
根据文档，如果目标可以用限制最大递归或更少来证明，它应该会成功。在限制为 30 的第一次调用中，我们看到结果为 25，因此我希望以 26 的限制调用它会成功。我在模块中使用约束处理规则，以防那里可能有一些交互使其行为不端。
编辑：玩过伊莎贝尔的回答后，我想我明白它的行为方式了：
看这个例子：
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.
我不相信 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
我不认为对不终止有什么可做的；你通常会在有无数答案的目标上使用它。
我试图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.