CODEWITHSUNDEEP
algorithmgraph-algorithma-starheuristicssliding-tile-puzzle
Petros Sofianos
Petros Sofianos

Reputation: 11

Comparison of A* heuristics for solving an N-puzzle

I am trying to solve the N-puzzle using the A* algorithm with 3 different heuristic functions. I want to know how to compare each of the heuristics in terms of time complexity. The heuristics I am using are: manhattan distance , manhattan distance + linear conflict, N-max swap. And specifically for an 8-puzzle and an 15-puzzle.

Upvotes: 0

Views: 1902

Answers (2)

FrankS101
FrankS101

Reputation: 2135

As @Harold said in his comment, the approach to compare time complexity of heuristic functions is tipically by experimental tests. In your case, generate a set of n random problems for the 8-puzzle and the 15-puzzle and solve them using the different heuristic functions. Things to be aware of are:

  1. The comparison will always depend on several factors, like hardware expecs, programming language, your skills when implementing the algorithm, ...

  2. Generally speaking, a more informed heuristic will always expand less nodes than a less informed one, and will probably be faster.

And finally, in order to compare the three heuristics for each problem set, I would suggest a graphic with average running times (repeat for example 5 times each problem) where:

  1. The problems are in the x-axis sorted by difficulty.
  2. The running times are in the y-axis for each heuristic function (perhaps in logarithmic scale if the difference between the alternatives cannot be easily seen).

and a similar graphic with the number of explored states.

Upvotes: 1

Paul Hankin
Paul Hankin

Reputation: 58241

The N-puzzle is, in general, NP hard to find the shortest solution, so no matter what heuristic you use it's unlikely you'll be able to find any difference in complexity between them, since you won't be prove the tightness of any bound.

If you restrict yourself to the 8-puzzle or 15-puzzle, an A* algorithm with any admissible heuristic will run in O(1) time since there are a finite (albeit large) number of board positions.

Upvotes: 1

Related Questions