Heuristic Search In Prolog [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

Questions asking us to recommend or find a tool, library or favorite off-site resource are off-topic for Stack Overflow as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it.

Closed 8 years ago.

Improve this question

I have solved Bridge and Torch puzzle in Prolog by simple depth first search. Now I am trying to solve it via a heuristic search. But I have no idea how should a heuristic be defined in Prolog.

As I have not found useful examples in SWI-Prolog manual and Google, would you please help me find some examples in Prolog which use heuristics for searching? Or give me a hint to start thinking heuristically about this problem.

Answer 1

Take a look to the state-space searching example distributed with Logtalk (which you can run using several backend Prolog compilers, including SWI-Prolog):

https://github.com/LogtalkDotOrg/logtalk3/tree/master/examples/searching

This example defines a state-space searching framework, supporting both blind and heuristic search, and comes with several examples, including a "bridge" one that might be useful to compare with your own solution. You will find examples of heuristics in some of the provided examples. This "searching" example also provides profiling support, which is useful to compare the effectiveness of different heuristics and search strategies.

Answer 2

You may look at my answer that uses Warnsdorff's heuristic to solve large Knight's tour puzzle: https://stackoverflow.com/a/21069014/220700 But the Warnsdorff's heuristic (Warnsdorff's rule) is very strong - it always works, which is not typical for heuristics in general.

The main idea of using heuristics in general is that if you have a predicate that lists all possible moves, order them according to some rule: shortest first, largest first, etc.

A* (A star) is one of the most used heuristics-based algorithms. Just google "a-star in prolog" for a lot of info.

Also constraint logic programming uses heuristics all the time: first_fail, most_constrained, largest, etc.