SE250:lab-X:dcho040

task1

• ways to organize 9 values(8 values + 1 blank)

  9! = 362,880 

• edges

   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

task2

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;
}

task4, 5

• code

  init_State( &start, "123456.78" );
  init_State( &goal,  "12345.786" );

• result

123
456
.78
 ->
123
456
7.8
 ->
123
456
78.
 ->
123
45.
786
 ->
Visited 6 states

• order to get children

  order (from get_children function)

   left -> right -> up -> down

• how visited states are decided

  * 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
  

• 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

  * 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
  

• 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.