Why does my a-star algorithm expand too many nodes despite having a correct heuristic?

Question

I'm doing an assignment where I have to use a-star to solve a 15-puzzle (in C).

The heuristic function is the Manhattan distance (aka taxicab distance).

We are given a sample input/output where the board is solved in 22 moves and after expanding 395nodes (board states) (i.e we had to look at the children of 395 nodes)

By 'correct' heuristic I mean my function is the same as the one used to produce the sample outputs and produces the correct distance.

The problem is my solution expands more than 400 nodes to find the solution (it is optimal 22 moves but a different one).

I noticed the number changes depending on the order I generate the children nodes (move the space tile up, left, down, right or other directions).

There are 24 ways you can move the space tile up, down, left and right to generate the children and I tried all of them but none of them expanded 395 nodes.

Why is this happening?

Terminology:

• node: each node is a configuration of the 15-puzzle board

• children: the configurations that you can achieve by moving the space tile up, down, left or right from the current node

PS: I'm using a binary heap for the open list if that matters

Thanks

Answer 1

When the heuristic is inconsistent in the algorithm, A* can perform very poorly as nodes that have already been expanded may need to be re-expanded many times. This result leads us to have the worst-case of O(2N ) node expansions, where N is the number of distinct nodes expanded.

For more information regarding this, refer the link:

https://www.ijcai.org/Proceedings/09/Papers/111.pdf