Why is my a-star algorithm expanding too many nodes despite the correct heuristic?

Question

I am doing a job where I need to use a-star to solve a 15-puzzle (in C).

Heuristic function Manhattan distance (otherwise it is a taxi distance).

We are given an example of input / output, where the board is solved when moving 22 and after the expansion of nodes 395 (state of the board) (i.e. we had to look at children from 395 nodes)

By “correct” heuristic, I mean that my function is the same as that used to generate the sample output and gives the correct distance.

Problem my solution expands over 400 nodes to find a solution (this is an optimal 22 moves, but different).

I noticed that the number changes depending on the generation order of the child nodes (move space, up, left, down, right, or in the other direction).

There are 24 ways to move a piece of space up, down, left, and right to generate child elements, and I tried all of them, but none of them expanded 395 nodes.

Why is this happening?

Terminology:

• node: each node is a 15-voice card configuration
• children: configurations you can achieve by moving the tile space up, down, left, or right of the current node

PS: I use a binary heap for an open list, if that matters

thanks

Answer 1

Mmmh ... In the ideal case, A * does not depend on what order you create for the children. Unfortunately, if you have a “queue” of two or more nodes with the same heuristic value with distance plus cost, the algorithm can select “randomly” one of these nodes and find another solution (and study a different search path).

I think you can try:

• Check heuristic function with remote heuristic. (each action cost is 1? Do you sum the distance of each square from the right position in the right direction?)
• Check your bunch. Does it return the correct nodes? How many nodes with the same heuristic value can you have at the same stage?

This is the only thing I can tell you with this information. :)