2

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.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
parisa
  • 784
  • 1
  • 8
  • 27
  • For some idea on how to think about this particular problem heuristically, see, for example, http://en.wikipedia.org/wiki/Bridge_and_torch_problem. it describes finding the solution by considering cases in which you consider those people whose travel times are closest together first. – lurker Jan 24 '14 at 22:00

2 Answers2

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.

Community
  • 1
  • 1
Sergii Dymchenko
  • 6,890
  • 1
  • 21
  • 46
2

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.

Paulo Moura
  • 18,373
  • 3
  • 23
  • 33
  • Thanks, Unfortunatly i didn't get why the heuristic function is like this:
    `heuristic((Left, Lamp, Right), Heuristic) :-` `( Lamp = left ->` `list::min(Left, Heuristic)` `; list::max(Right, Max),` `list::min(Right, Min),` `Heuristic is Max + Min` `).` would you please explain it a bit?     – parisa Jan 24 '14 at 22:08
  • Noting that in this formulation of the "bridge" puzzle you want to get all the persons on the left side, the quickest the person on the left side, the fewer moves will be necessary to get slower persons waiting on the right side. When the lamp is on the right side, you usually want to combine in a single move the quicker and the slower persons to go to the left side. – Paulo Moura Jan 25 '14 at 00:57