Jun4-minutes

The lecture on 4th June was centered around lab 10 on State space search. The following items were discussed:

Problems with lab 10

• people had some trouble running the program as it had been modified my Jon Hamer to use a 15 state puzzle and this caused the program to give errors at compile time. This problem was soon fixed however by modifying a single line in the code.

• Some people discovered that the program infact used a Manhattan best first search system instead of a simple depth first as was stated in the lab information sheets.

• Not many people got passed Task 6

Manhattan Search

Much of the lecture was dominated by examining the actual program to see what kind of searching pattern was used. It was finally decided that the search implemented a Manhattan best first sequence. The actual code of the search called the add_to_OrderedStateList in the search.c file. This function eventually uses the manhattan code located in the 8-puzzle.c:

*
  Compute the Manhattan distance between a state and the expected goal
  state "12345678."
 */
#include <ctype.h>

int Manhattan( State* s ) {
  int i;
  int cost = 0;
  for( i = 0; i < PUZZLE_SIZE*PUZZLE_SIZE; i++ ) {
    int p;
    if( s->pieces[ i ] == '.' )
      p = PUZZLE_SIZE*PUZZLE_SIZE-1;
    else if( isdigit( s->pieces[ i ] ) )
      p = s->pieces[ i ] - '1';
    else
      p = s->pieces[ i ] - 'a' + 9;
    cost += abs( row(i) - row(p) ) + abs( col(i) - col(p) );
  }
  return cost;
}

int closer_State( State* a, State* b ) {
  return Manhattan(a) - Manhattan(b);
}

Depth First vs. Breadth First

We investigated the different searching techniques:

Depth First

pros:

• Memory efficient

cons:

• Can get stuck on the wrong branch if the state space is infinite.

Breadth First

pros:

• Won't get stuck on the wrong branch if the state space is infinite. It will eventually find the answer.
• Usually faster than Depth First.

cons:

• Not as memory efficient as depth first

Iterative Deepening

Iterative deepening searching was discussed in the lecture. It is a mixture of depth first and breadth first searching and tries to find a compromise between memory efficiency and speed.

Wikipedia states that it is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches d, the depth of the shallowest goal state. On each iteration, the IDDFS visits the nodes in the search tree in the same order as depth-first search, but the cumulative order in which nodes are first visited, assuming no pruning, is effectively breadth-first.

Iterative deepening depth-first search combines depth-first search's space-efficiency and breadth-first search's completeness (when the branching factor is finite). Search is optimal when the path cost is a non-decreasing function(monotone) of the depth of the node.