SE250:lab-X:llay008
Lab X
Task One
Task Two
This took a while to go through and figure out, partly because I didn't know exactly what the OrderedStateList etc was doing. Here is my attempt at a summary of the the search function...
Takes in four arguments
- A State struct that represents the start state.
- A State struct that represents the end state.
- A pointer to StateList struct (called solution).
- A pointer to an int (called n_states_visited).
Returns
- A boolean
There are four initialised variables at the start:
OrderedStateList open; StateSet visited; StateMap path_map; bool success = false;
The top three are then initialised by calling functions defined elsewhere While the OrderedStateList is not empty... Get the next state If it is the state that you are searching for... success boolean is equal to true. Break
while( ! is_empty_OrderedStateList( &open ) ) {
State s;
pop_OrderedStateList( &open, &s );
if( same_state( &s, goal ) ) {
success = true;
break;
Else Get the children of the state Iterate through the children if we have not seen the state... put the state in the stateMap and add the state to the OrderedStateList Release the children
} else {
int i, n_children;
State* cs = get_children( &s, &n_children );
for( i = 0; i < n_children; i++ )
if( add_to_StateSet( &visited, &cs[ i ] ) ) {
/* we have not yet seen this state */
put_StateMap( &path_map, &cs[ i ], &s );
add_to_OrderedStateList( &open, &cs[ i ] );
}
release_children( cs );
}
}
Create a new variable called s which is a State Iterate through the states, goal state ? while the State is not equal to 0, going to the next state on the StateMap
{ State* s;
for( s = goal; s != 0; s = get_StateMap( &path_map, s ) )
add_to_StateList( solution, s );
}
If n_state_visited (this is the pointer to an int that is passed through in the function call), the pointer is now equal to the number of states visited(?)
if( n_states_visited )
*n_states_visited = visited.size;
free the orderedStateList free the StateSet
return success
free_OrderedStateList( &open ); free_StateSet( &visited ); return success; }
Task Three
Task Four
On of the problems that I had with this task was that it wouldn't compile. This was not helped by the fact that there was a mistake in the main function and the test example was for a 4*4 grid, instead of 3*3.
Here is an excerpt of the result of trying to go from .12345678 to 12345678.
.12 345 678 -> 1.2 345 678 -> 142 3.5 678 -> 142 .35 678 -> 142 635 .78 -> 142 635 7.8
<html><embed src="http://i298.photobucket.com/albums/mm247/Phoenix100_album/Depth-first-search.jpg" width=1000 height=300></html>
Sadly, as is, my graph is not at all legible, though it can be read when you zoom in a couple hundred percent. The node at the top of the graph is the final state and I can't find the initial state... due to the fact that one side of my graph has been cut off. From this graph, the tree started at the right-hand corner. The other nodes at the bottom of the tree are dead ends, where there are no new states that the tree can look at.
Actually... couple/several hundred % zooming doesn't exactly help because of the low pixel count. The tree just becomes a real big mess (blurr) to look at... State4PlasmaTalk 15:13, 15 June 2008 (NZST)