0

I have predicate, that enumerates through backtracking list of values. I want to find highest value from this list.

For example:

ranked_move(X,Y,R) :- between(0,10,Y), between(0,10,X), rank_move(X,Y,R).
top_move(X,Y) :- % X, Y for highest R

Right now, I have it solved by using findall and custom predicate that goes through the list and remembers highest value it comes across. But I would like to know if there is way to do it without first turning the moves into a list. Eg. do the picking predicate directly on ranked_move.

I know about https://stackoverflow.com/questions/1701693/max-out-of-values-defined-by-prolog-clauses . I haven't tried it, but I assume Prolog is not going to go through the predicates efficiently.

Improve this question
1
  • I just noticed I posted this on Programmers, not on SO. Commented Apr 20, 2013 at 5:50

1 Answer 1

Reset to default
1

As long as you don't have any way of judging your moves except calling ranked_move/3, no, there is no more efficient way than calling it on everything and finding the maximum of the resulting list.

It would be possible to avoid the findall by writing your own predicates that generate the values systematically and remember the maximum so far, and so avoid the overhead of creating a list. But that overhead is very likely insignificant next to the cost of judging the moves (no heuristic worth implementing could possibly be cheaper than a cons operation).

So the only really useful improvement would be to have a different, cheaper, weaker heuristic that influences the order in which the moves are generated, and iterate over them in an order more likely to have the maximum first. (Even then, of course, you would still not terminate any quicker unless you set a cutoff value that is "good enough" rather than "optimal".)

Improve this answer
1
  • You are right. I was focusing on wrong part of the problem. Commented Apr 20, 2013 at 5:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.