Mark: 9 revision(s)

2008-11-03T05:20:46Z

9 revision(s)

New page

==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:
<pre>
OrderedStateList open;
StateSet visited;
StateMap path_map;
bool success = false;
</pre>

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
<pre>
while( ! is_empty_OrderedStateList( &open ) ) {
State s;
pop_OrderedStateList( &open, &s );
if( same_state( &s, goal ) ) {
success = true;
break;
</pre>
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
<pre>
} 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 );
}
}
</pre>
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
<pre>
{ State* s;
for( s = goal; s != 0; s = get_StateMap( &path_map, s ) )
add_to_StateList( solution, s );
}
</pre>
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(?)
<pre>
if( n_states_visited )
*n_states_visited = visited.size;
</pre>
free the orderedStateList
free the StateSet

return success
<pre>
free_OrderedStateList( &open );
free_StateSet( &visited );

return success;
}
</pre>
===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.
<pre>
.12
345
678
->
1.2
345
678
->
142
3.5
678
->
142
.35
678
->
142
635
.78
->
142
635
7.8
</pre>
<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... [[User:Sbha077|State4Plasma]]<sup>[[User_talk:Sbha077|Talk]]</sup> 15:13, 15 June 2008 (NZST)

SE250:lab-X:llay008 - Revision history

Mark: 9 revision(s)