下面代码中的修剪选择点如何使其更高效(Prolog)? [英] How does pruning choice points in the code below make it more efficient (Prolog)?

问题描述

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

solve_task(Task,Cost):-agent_current_position(奥斯卡，P)，solve_task_a(Task,[b(0,0,P)],[],R,Cost,_NewPos),!, % 修剪选择点以提高效率反向(R，[_Init|路径])，agent_do_moves(奥斯卡，路径).

解决方案

以上例子中的切入有以下效果:

理想情况下，它提交可能发生在solve_task_a/6中的搜索到找到的第一个答案.这可以释放资源来寻找进一步的答案，从而改善空间消耗.

范围问题

然而，与此同时，它也可能隐藏对agent_current_position/2的进一步回答.当然，对于这个目标有进一步的答案没有多大意义，但它可能是一个错误，碰巧睡了一会，在最坏的情况下才变得活跃但仍然未被发现.

出于这个原因，最好写而不是剪切

 ...,一次(solve_task_a(...)),...

这将范围限制在您想要表达的范围内.

稳定性问题

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

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

<预>解决任务(任务，成本):-% agent_current_position(oscar,P),一次(solve_task_a(Task,[b(0,0,P)],[],R,Cost,_NewPos)),真的.solve_task_a(_, _, _, _, 20, _).solve_task_a(_, _, _, _, 30, _).

现在

?- solve_task(a, Cost).成本 = 20.?-solve_task(a, 30).真的.?- solve_task(a, Cost), Cost = 30.错误的.

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

<预>解决任务(任务，成本):-% agent_current_position(oscar,P),一次(solve_task_a(Task,[b(0,0,P)],[],R,CostX,_NewPos)),成本X = 成本真的.

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

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

并非总是有捷径可走.但通常可以坚持逻辑纯度 逻辑纯度.在这种情况下，您不必记住任何此类假设.

<小时>

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

In the code given below, there is the ! (cut) that prunes the choice point for efficiency. I am pretty certain that the reverse predicate and the agent_do_moves predicate are essential.

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).

解决方案

The cut in above examples has the following effect:

Ideally, it commits the search which might happen within solve_task_a/6 to the first answer found. This frees resources for finding further answers which improves space consumption.

Scope problems

However, at the same time, it might also hide further answers to agent_current_position/2. Of course, it does not make much sense to have further answers for this goal, but it might be an error that happens to sleep for a while, only to become active but still undiscovered in the worst possible situation.

For this reason, it would be preferable to write instead of the cut

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

This limits the scope precisely to what you want to express.

Steadfastness problem

But this is not the only possible source of problems. I see this variable Cost. Will it be instantiated when you call solve_task(Task, Cost) or not? I could do a lot of guessing here. But at least this variable might influence the answer Prolog will commit to. So solve_task(Task, 99) and solve_task(Task, Cost), Cost = 99 might produce different answers. In fact, the latter might even fail. Predicates that have such problems are said to lack steadfastness.

To illustrate how steadfastness is easily lost in such a situation consider this (runnable) sketch of your (already improved) program:

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.

There would be an easy way out of this problem by cleanly testing variable Cost, e.g. Cost >= 0 which produces an instantiation error should Cost be an uninstantiated variable. But if you want (as you indicate in your comment) to determine the cost, you need to put it like so:

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

In this manner we can be sure that Cost cannot influence the outcome of solve_task_a/6 (euh - provided there is no aliasing between Cost and Task - but let's assume that for the moment). One says also that output unifications are put behind the commit.

Many people will tell you that such extra care is not needed, as you will never use solve_task(Task, Cost) with a given cost. That might be the case, but are you sure you will remember it? And are you sure the source code will remember it (without any dynamic check)? Such implicit assumptions easily accumulate to a degree were your mental capacities are overburdened.

There is not always an easy way out. But quite often it is possible to stick to logical purity logical-purity. In that case, you do not have to remember any such assumptions.

---

_{In any case, I would recommend that you do not go into these parts of Prolog for the moment. Rather stick to successor-arithmetics, clpfd, and other clean, monotonic programs preserving logical-purity. There is a lot to learn!}

这篇关于下面代码中的修剪选择点如何使其更高效(Prolog)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！