Qfyilyi

For 16-Puzzle, let's say I have 3 heuristics: h1, h2, h3

h1 returns number of misplaced tiles

h2 returns sum of manhattan distances

h3 returns sum of inverted pairs

The cost of each action is set so that all of them are inadmissible (it is not the case that for all n, h(n) <= h*(n)). I'd like to know how to rank them based on speed for any node/state.

I tried testing my code. My results were (predictably): h3 > h2 > h1

Since they are not optimal, speed seems to depend on descending order of the size of h return values. However, I cannot know for sure that this pattern holds for ALL nodes/states. I'd like know if someone can help me know for certain. I've tried browsing for resources in search of a general rule for this type of pattern, but I couldn't find anything.

I would also like to know how to compare the performances of admissible and inadmissible heuristics.

In the Logtalk distribution, I have a state-space search example where I use events to compare search method (e.g. hill-climbing vs best-first) and heuristics performance. For the 8-puzzle, an example of output that includes heuristics stats is:

solution length: 6

number of state transitions: 15

ratio solution length / state transitions: 0.4

minimum branching degree: 2

average branching degree: 3.13333

maximum branching degree: 4

time: 0.02

The stats are collected using a performance monitor for the events (read, messages for public predicate) that make use of heuristics (notably, the predicate that computes the next candidate state(s) for a given state). The full source code of the example can be browsed at:

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

A similar solution should be possible in your case.