What a night...
Anyway, let's go over what we have so far. With Dijkstra's algorithm we have a - computationally expensive - method to solve problems given a search space (S, T), a start state (start), and the goal state (goal). Btw. this algorithm can be applied to any problem that can be abstracted to search space, start, and goal. Now why is this approach so computationally expensive? Because the algorithm applied is basically dumb, i.e. it doesn't use any means to decide, which transition seems to be the most promising one to take at any given puzzle state.
3. Dijkstra + knowledge -> A*:
To reduce the effort necessary to find a solution we will have to find some means to favor one transition over another at a given state. For the 15 puzzle there is no actual information to gain from looking at the layout, as far as I can see. So we will have to guess which one of any two given states is closer to our goal. Let's call additional information on a problem 'heuristic' (h). One thing we can be sure about the 15 puzzle is, that if
h = number of tiles at wrong locations
we will need at least h moves (at least 1 move for each incorrect tile) to reach the goal. How can we use this information to reduce the amount of searching necessary to find a solution? Let's go back to Dijkstra's algorithm. Instead of sorting our open list with respect to the number of moves taken so far, let's take our estimate on the 'distance' from the goal into account. While Dijkstra's sorting predicate is
f = g (g = costs so far)
we'll use costs + estimate
f = g + h
and call this 'new' algorithm A*. So the difference between Dijkstra's algorithm and A* is, that Dijkstra is searching indifferent in all possible directions whereas A* is searching in favor of those directions, that are presumably closer to the goal. Bare in mind though that our presumtions are based on guessing only.
3.1. Small guess-ology:
It appears to be logical that A* will find a solution faster than Dijkstra if our presumtions are all correct. But what happens if not? What if only some of them are wrong? Let's discover the different degrees of, hmm, wrongness? wrongity? anyone? If our estimated distance is wrong it can be either too large or too small. Overestimating is dangerous in that we may be skipping potential solutions. Understimating is not only harmless, but essential to ensure that the returned solution requires the least number of transitions to be reached.
3.2. It's all in the heuristics:
Let's check the heuristic above against this. It is obvious that if n tiles are in wrong locations it takes n moves at best to reach the solution. Since A* uses the heuristic as a decisive means to cut down computational effort, the heuristic's quality is the key component to success. If it comes close to the actual effort it unleashes A*'s power. In fact, if every guess is correct, i.e. we have a perfect heuristic, A*'s very first try at the puzzle will return the best possible solution. However, our heuristic only returns values in the range of [0..15] and becomes somwhat void after about 100 moves. In the introduction I said that 'it might not be the best approach'. There is some computational overhead involved in calculating the heuristic. In our case this might not really matter, however, if our chosen heuristic is very poor, A* can become even more timeconsuming than Dijkstra! In other words: While Dijkstra will find the best solution, A*'s heuristic is in charge of the time spent to discover it.
So what do we have now? In section 1 we found a way to present the problem in a machine-readable form. Section 2 introduced a method to blindly search for a solution. In section 3 we discovered a possibility to bring orientation into the darkness. 'Yeah, I know, but this is all theoretical. Don't you have a more specific explanation, a more visual one?' I hear you ask.
4. Can you picture this?:
Well, no. The 1-dimensionality of the 15 puzzle seems to be ungraspable for my mind. If you don't mind, let's leave this problem behind and look at something different. Pretend we're implementing pathfinding strategies for a tile-based RTS-game. The search space is defined by our grid consisting of w * h tiles. In this case the open list can be depicted as the outer border of all tiles that have been examined in search of a solution. The closed list contains all tiles 'inside' the open list. When applying Dijkstra's algorithm to find the shortest path from A to B, the search radius will extend in a circular fashion around A (if we allow diagonal moves, otherwise it would be a square) until the border touches B. Thus the open list forms a circle, and closed contains everything inside forming a disc. A*'s search pattern is more irregular and extends more towards the presumably best path. If we have a perfect heuristic the closed list will be nothing but a single line containing the path with the open list surrounding it. In a worst case scenario though, after an A*-search has completed, the closed list can contain all positions, but the goal B, which would be the last one in the open list. I hope this can help to clarify why an A* equipped with a bad - even though correctly underestimating - heuristic can perform worse than Dijkstra.
This is it. For now. Give me a day and I'll come up with some code. If anyone cares about, let me know and I'll mail it to you. I'd like to post it here, but without a fixed-font (and possibly syntax highlighting) it doesn't really turn out readable. If you have questions, insults, comments, ... let me know.
regards,
.:fl0yd:.
--------------------------
errata (guess noone is perfect, oh well...):
c.) for each legal dir { open.push_back( n ); n.tile_state = transform( n.tile_state, dir ); n.dir_parent
= rev_dir( dir ); goto b.); }
should be:
c.) closed.push_back( n );
++n.move_count;
for each legal dir {
n.tile_state = transform( n.tile_state, dir );
if( !closed.find( n ) ) { // == if not already visited
n.dir_parent = rev_dir( dir );
goto b.)
}
}
return FAILED; // no solution
f.) for( char d = 1; d <=8; d << 1 ) {
if( legal_move( n.tile_state, d ) ) {
node n_new = transform( n.tile_state, d );
if( !closed.find( n_new ) && !open.find( n_new ) ) {
open.push_back( n_new );
}
}
}
should be:
f.) ++n.move_count;
for( char d = 1; d <= 8; d << 1 ) {
if( legal_move( n.tile_state, d ) ) {
node node_new( transform( n.tile_state, d ), rev_dir( d ), n.move_count );
if( !closed.find( n_new ) ) // not visited yet
if( !open.find( n_new ) ) // and not already in examination queue
open.push_back( n_new );
else // if already in examination queue
if( *open.find( n_new ).move_count > n_new.move_count )
*open.find( n_new ) = n_new; // if faster to reach replace it
}
}
disclaimer: no animals were harmed during the course this production
Main Topics
Browse All Topics
by: fl0ydPosted on 2001-10-04 at 12:55:10ID: 6528639
Hi jiminika,
this question is surely worth the 200 points. To answer your question right away: A* *CAN* be used to solve the 15 puzzle. However it might not be the best approach; I'll get to that in a minute.
As this is going to become a bit lengthy let me offer you a table of contents so you don't get lost:
1. Breaking down the problem
2. Dijkstra's algorithm
3. Dijkstra + knowledge -> A*
4. Can you picture this?
All code priveded is optimized for readablity only.
1. Breaking down the problem:
As with all problems you'd like to present to a computer you will have to transform it, so that a machine can 'understand' it. Thus transformation usually means abstraction of the nature of the problem.
Let's go back to the 15 puzzle. There are 4 pieces of information to describe the entire problem. A set of states (S), a set of transitions (T) to move from one state to another, a start state (start), and a goal state (goal).
Set of states (S): this is a machine-readable description of all possible constellations of the puzzle. I'd suggest using a 4x4 array
char tile[16];
to describe the layout, where tile[0] is the top left corner, tile[3] the top right corner, tile[15] the bottom right corner. Fill this array with the respective number of the tile and mark the empty spot with a '0'. This way you have just created the start state (start). Your goal state (goal) is {1, 2, 3, ..., 14, 15, 0}.
Set of transitions (T): this refers to sliding pieces on the board to get from one layout to another. For any state of the puzzle this can be 2, 3, or 4 legal moves (2 at corners, 3 on edges, and 4 on the interior). We'll use
char dir;
for transitions and declare the directions as follows:
right: 00000001b (1)
top: 00000010b (2)
left: 00000100b (4)
bottom: 00001000b (8)
Information on which tile is to be moved can be gathered from the direction code (d) and the current state (cs). Let's say d == 4 (left) and cs = { 0, .... } then the 2nd tile (tile[1]) is to be moved.
Let's take a step back and see what we have so far: We know WHAT the puzzle looks like (start), we know WHERE we are headed (goal), and we know HOW to walk (set of transitions T). Still with me? Good!
2. Dijkstra's algorithm
With all the WHAT, WHERE, and HOW we still don't know WHICH step at any give puzzle state will get us closer to our goal. There aren't many means to choose from when there is nothing to decide upon, so let's face it: a situation like this calls for brute force. Beginnig with the start state we do the following:
a.) set cs = start
b.) if( cs == goal ) return GOAL_REACHED;
c.) for each legal direction set cs = transform( cs, dir ) and goto b.)
[transform( const char[16]& state, const char dir ) returns new puzzle state after sliding the appropriate tile into the specified direction]
Simplified - and not quite accurate, I admit - this is Dijkstra's algorithm: Check for ALL possibilities until we reach the goal. Cool! We've reached the goal then? Technically speaking, yes, cs == goal. From a human perspective, though, the interest is more towards 'can you tell me how?'. Damn, we forgot the housekeeping. We need some structure to hold information on where we came from.
struct node {
char tile_state[16];
char dir_parent;
};
And we need some means to 'remember' where a possible parent of a parent came from. What about some sort of long term memory that stores all puzzle states we've examined so far? Let's just call it closed (as in 'closed for examination'):
#include <list>
std::list<node> closed;
Let's refine the algorithm above:
a.) node n = {start, 0};
b.) if( n.tile_state == goal ) return solution;
c.) for each legal dir { open.push_back( n ); n.tile_state = transform( n.tile_state, dir ); n.dir_parent = rev_dir( dir ); goto b.); }
Now we have all the information to construct a solution. Starting at goal, we check for equality with start. If not, we retrieve node n from closed, where n.tile_state == cs, and append n.dir_parent to our solution list, ... The list is still doubly inverted. All we have to do is to change the order from back to front and reverse each direction. Voila - here it is.
Well, possibly, but not necessarily. We did not take any precautions to avoid ending up in an endless loop (i.e. moving a tile to the left and moving it to the right again, then left, right, left, right, ...) And possibly we could use the little information we have gathered on our way to speed up calculation. Let's redesign our node structure:
class node {
char tile_state[16];
char dir_parent;
int move_count;
};
move_count is set to 0 for the start node and increased by 1 for each expansion. We'll also be using a short term memory list that holds all nodes open for examination and call it open. Before expanding a node the open list is sorted in ascending order, so we'll expand all nodes whose tile_state can be reached with one move, then those, that can be reached in two moves, and so on.
To finish this section, here is the more complete algorithm in pseudo-code:
a.) node n = { s, 0, 0 }; open.push_back( n );
b.) if( 0 == open.size() ) return FAILED; // no solution!
c.) open.sort( ASCENDING ); n = open.front(); open.pop_front();
d.) if( n.tile_state == goal ) return solution;
e.) closed.push_back( n );
f.) for( char d = 1; d <=8; d << 1 ) {
if( legal_move( n.tile_state, d ) ) {
node n_new = transform( n.tile_state, d );
if( !closed.find( n_new ) && !open.find( n_new ) ) {
open.push_back( n_new );
}
}
}
g.) goto b.)
Enough for today, my girlfriend needs attention...
The rest will follow tomorrow.
regards,
.:fl0yd:.