prolog - 下面代码中的修剪选择点如何使其更加高效(Prolog)？

Question

在下面给出的代码中，有一个!(剪切)，它会修剪选择点以提高效率。我非常确定 reverse 谓词和 agent_do_moves 谓词是必不可少的。

solve_task(Task,Cost):-
    agent_current_position(oscar,P),
    solve_task_a(Task,[b(0,0,P)],[],R,Cost,_NewPos),!,  % prune choice point for efficiency
    reverse(R,[_Init|Path]),
    agent_do_moves(oscar,Path).

Answer 1

以上示例中的剪切具有以下效果:

理想情况下，它会将 solve_task_a/6 内可能发生的搜索提交给找到的第一个答案。这可以释放资源来寻找进一步的答案，从而减少空间消耗。

范围问题

但是，与此同时，它也可能隐藏对agent_current_position/2的进一步答案。当然，对于这个目标有进一步的答案没有多大意义，但这可能是一个错误，恰好休眠了一段时间，只是在最坏的情况下变得活跃但仍未被发现。

因此，最好是书写而不是剪切

    ...,
    once( solve_task_a( ... ) ),
    ...

这将范围精确限制为您想要表达的内容。

坚定性问题

但这并不是唯一可能的问题根源。我看到这个变量Cost。当你调用solve_task(Task, Cost)时它会被实例化吗？我可以在这里做很多猜测。但至少这个变量可能会影响 Prolog 将 promise 的答案。因此，solve_task(Task, 99) 和 solve_task(Task, Cost), Cost = 99 可能会产生不同的答案。事实上，后者甚至可能会失败。存在此类问题的谓词被称为缺乏稳定性。

为了说明在这种情况下如何容易失去坚定性，请考虑您的(已改进的)程序的(可运行的)草图:

solve_task(Task,Cost):-    % agent_current_position(oscar,P),    once(solve_task_a(Task,[b(0,0,P)],[],R,Cost,_NewPos)),    true.solve_task_a(_, _, _, _, 20, _).solve_task_a(_, _, _, _, 30, _).

Now

?- solve_task(a, Cost).
   Cost = 20.
?- solve_task(a, 30).
   true.
?- solve_task(a, Cost), Cost = 30.
   false.

通过彻底测试变量Cost，可以轻松解决这个问题，例如产生实例化错误的 Cost >= 0 应该是一个未实例化的变量。但如果您想(正如您在评论中指出的那样)确定成本，您需要这样表述:

solve_task(Task,Cost):-    % agent_current_position(oscar,P),    once(solve_task_a(Task,[b(0,0,P)],[],R,CostX,_NewPos)),    CostX = Cost    true.

通过这种方式，我们可以确保 Cost 不会影响 solve_task_a/6 的结果(呃 - 前提是 Cost 之间没有混叠) > 和 Task - 但我们暂时假设这一点)。有人还说输出统一放在提交后面。

许多人会告诉您，不需要如此额外的小心，因为您永远不会在给定成本的情况下使用 solve_task(Task, Cost)。也许是这样，但你确定你会记住吗？您确定源代码会记住它(无需任何动态检查)吗？如果你的心智能力负担过重，这种隐含的假设很容易累积到一定程度。

并不总是有简单的出路。但很多时候坚持逻辑纯粹是可能的 logical-purity 。在这种情况下，您不必记住任何此类假设。

<小时/>

_{无论如何，我建议您暂时不要进入 Prolog 的这些部分。而是坚持successor-arithmetics , clpfd ，以及其他干净、单调的程序，保留 logical-purity 。有很多东西要学!}