A* with 8 Puzzle Problem

The optimality of the solution doesn't depend on the order in which you consider moves with equal heuristic value. As long as your heuristic never overestimates the number of moves left, you should get optimal solutions.

The Manhattan distance is a conservative estimate of the number of moves left, therefore you should be getting optimal solutions. I would say there is a mistake somewhere in your program.

Quote:

Original post by Tech19 Firstly if you are unfamiliar with the 8 puzzle problem take a look at http://www.permadi.com/java/puzzle8/ I have decided to go with using the manhattan distance as my heurisitc, is this the best approach? Secondly what should I do if two states come out with the same value for the heuristic? How do should the program decide which path to follow? At the moment my program is always just following the first state, however this does not always lead to the optimal solution.

Your heuristic must be admissible, in that it won't ever over estimate the cost of reaching your goal node. If this is the case, A* will always find an optimal solution so you must be doing something wrong. As for picking which state to go to, if two or more states have exactly the same score with your heuristic, there isn't any logical reason to pick one over the other so just do what's easiest.

The manhatten distance is the standard heuristic used for this sort of problem. I'm sure other more interesting heuristics exist, but they are probably a lot more computationaly expensive, and not much better at evaluating states.

The total cost of a state consists of the cost of getting to that state plus the estimated cost of getting to the solution state (the heuristic). If two states have the exact same cost, then it doesn't really matter which one you investigate first as you have no way of knowing which is actually superior. Whichever state you expand first you are still gauranteed to get the optimum solution if your heuristic underestimates the true cost of a state.

If you're not getting the optimal solution then you havn't implemented the A* search properly.