Geek Answers Handbook

How do narrow selections in the code below make it more efficient (Prolog)?

The code below is ! (cut), which shortens the selection point for efficiency. I am pretty sure 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).
+4
source share
1 answer

Cutting in the above examples has the following effect:

Ideally, it performs a search, which can occur in solve_task_a/6 , to the first answer found. This frees up resources for further answers that improve space consumption.

Area Issues

However, at the same time, it may also hide further responses to agent_current_position/2 . Of course, it makes no sense to have further answers for this purpose, but it can be a mistake that can sometimes sleep, only to become active, but still undiscovered in the worst possible situation.

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

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

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

Persistence problem

But this is not the only possible source of problems. I see this variable Cost . Will it be created when call solve_task(Task, Cost) or not? I could guess a lot here. But at least this variable can affect the response that Prolog agrees to. Therefore, solve_task(Task, 99) and solve_task(Task, Cost), Cost = 99 can give different answers. In fact, the latter may even fail. Predicates that have such problems say lack of persistence .

To illustrate how resilience is easily lost in such a situation, consider this (executable) 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.

It would be easy to get out of this problem by reading the Cost test variable, for example. Cost >= 0 , which creates an instance creation error, should Cost be an undefined variable. But if you want (as you indicate in your comment) to determine the cost, you need to do this:

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

Thus, we can be sure that Cost cannot influence the result of solve_task_a/6 (euch - in the absence of overlap between Cost and Task - but suppose at the moment). It also states that weekend unifications are placed behind a commit .

Many will tell you that such additional help is not needed, since you will never use solve_task(Task, Cost) with a certain cost. It may be so, but are you sure you will remember it? And are you sure that the source code will remember it (without any dynamic verification)? Such implicit assumptions easily accumulate to some extent, as your mental abilities are overloaded.

There is not always an easy way out. But quite often you can adhere to the logical purity of logical-purity . In this case, you do not need to remember such assumptions.

In any case, I would recommend you not to go into these parts of the Prolog at the moment. Rather stick to successor-arithmetics , clpfd, and other pure monotonous programs that preserve logical-purity . There are many opportunities to explore!

+7
source

More articles:


All Articles