Mark: 11 revision(s)

2008-11-03T05:20:43Z

11 revision(s)

New page

== task1 ==
*ways to organize 9 values(8 values + 1 blank)
9! = 362,880
*edges
<pre>
9!/1 (middle )=> 4 ways to move
9!/4 (corners)=> 2 ways to move
9!/4 (others )=> 3 ways to move
total ways to move = 9!/1*4 + 9!/4*2 + 9!/4*3 = 1,905,120
</pre>
== task2 ==
<pre>
bool search( State* start, State* goal, StateList* solution, int* n_states_visited ) {
OrderedStateList open;
StateSet visited;
StateMap path_map;
bool success = false;

// initialize the Map, Set and List
init_OrderedStateList( &open );
init_StateSet( &visited );
init_StateMap( &path_map );

// add starting states to the List and Set
add_to_OrderedStateList( &open, start );
add_to_StateSet( &visited, start );

// Find the goal state using while
while( ! is_empty_OrderedStateList( &open ) ) {
State s;
// put children from before loop to S
pop_OrderedStateList( &open, &s );
// return true and break when S has the goal
if( same_state( &s, goal ) ) {
success = true;
break;
// else check all children
} else {
int i, n_children;
State* cs = get_children( &s, &n_children );
for( i = 0; i < n_children; i++ )
// if the child is not visited state
if( add_to_StateSet( &visited, &cs[ i ] ) ) {
/* we have not yet seen this state */
// put the child in state Map
put_StateMap( &path_map, &cs[ i ], &s );
// save the child to ordered list
add_to_OrderedStateList( &open, &cs[ i ] );
}
// reset the children
release_children( cs );
}
}

// get the solution list from the goal to the top in state map
{ State* s;
for( s = goal; s != 0; s = get_StateMap( &path_map, s ) )
add_to_StateList( solution, s );
}
// save the number of states looked for this search
if( n_states_visited )
*n_states_visited = visited.size;
// free ordered list and Set
free_OrderedStateList( &open );
free_StateSet( &visited );
// return success
return success;
}
</pre>
==task4, 5==
*code
<pre>
init_State( &start, "123456.78" );
init_State( &goal, "12345.786" );
</pre>
*result
<pre>
123
456
.78
->
123
456
7.8
->
123
456
78.
->
123
45.
786
->
Visited 6 states

</pre>
* order to get children
<pre>
order (from get_children function)

left -> right -> up -> down

</pre>
* how visited states are decided
<pre>
* depth-first search *

123
firstLevel 456
.78

left(X) right up down(X)

123 123
secondLevel 456 .56
7.8 478

left right up down(X)
(already visited)
123 123
thirdLevel 456 4.6
78. 758

left right(X) up down(X)
(already visited)
123
forthLevel 45.
786

6 states

</pre>
* discussion
* depth-first search *
one wrong way took a long time to turn back to right way
if the way is right, quick search is possible

==task6==
*code
init_State( &start, "123456.78" );
init_State( &goal, "1235.6478" );

*searching structure
<pre>

* Breadth-first search *

123
firstLevel 456
.78

left(X) right up down(X)

123 123
secondLevel 456 .56
7.8 478

left right up down(X) left(X) right up down
(already visited) (already visited)
123 123 123 .23
thirdLevel 456 4.6 5.6 156
78. 758 478 478

7 states

</pre>
*discussion
Breadth-first search searches all states by each level from the top

==discussion==
I will be back to this lab when I have more time but I have got some idea of Breadth first search and depth first search.

SE250:lab-X:dcho040 - Revision history

Mark: 11 revision(s)