Sign in to follow this  
Tech19

A* with 8 Puzzle Problem

Recommended Posts

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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
How are the closed and open lists best organised in an A* search of the 8-puzzle?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this