Lecture 27

Search Strategies

Consider the following problem:
      T---4----G--4--C
     /\        |         W
    /  \       5        /
   3    5      |       3
  /      \     |      /
 A---4----H-2--B--4--P
The diagram above shows 8 towns (A,T,H,B,G,C,P and W) connected by roads. The distance along each road is also shown on the diagram.

We want to get from town A to town W.

There are two questions we will ask about this journey.

  1. Is it possible? i.e. find any route.
  2. What is the shortest route.
Algorithms to answer the first question are called some path algorithms. Algorithms to answer the second question are called optimal path algorithms.
                       A
                      / \
                    /     \ 
                  /         \ 
                /             \
              /                 \
            /                      \
          /                          \
         H                            T
        / \                          / \
       /   \                        /   \
      /     \                      /     \
     /       \                    /       \
    B         T                  H         G
   / \         \                /         / \
  G   P         G              B         B   C
 / \   \       / \            / \       / \
T   C   W     B   C          P   G     H   P
             /              /     \         \
            P              W       C         W
             \
              W
This diagram is a search tree for the map. The leaf nodes represent places where there is nowhere to go that has not already been visited.

From the tree it can be seen that there are four possible routes to W.

`Some Path' Algorithms

A 'some path' algorithm to find a route between A and W is easy to write, just search the tree until a W is found. There are two useful techniques for doing this, either search the tree from left to right or from top to bottom.

Searching from left to right is called depth first search because we must go to the very bottom of the tree first.

Searching from top to bottom is called breadth first search because we must search across the tree first.

Depth First Search

The tree is be searched using preorder traversal.
                       A1
                      / \
                    /     \ 
                  /         \ 
                /             \
              /                 \
            /                      \
          /                          \
         H2                           T
        / \                          / \
       /   \                        /   \
      /     \                      /     \
     /       \                    /       \
    B3        T                  H         G
   / \         \                /         / \
  G4  P7        G              B         B   C
 / \   \       / \            / \       / \
T5  C6  W8    B   C          P   G     H   P
             /              /     \         \
            P              W       C         W
             \
              W
This diagram shows the order that the first 8 nodes are visited for depth first search. After this, the goal is found.

This procedure can be described recursively.

Depth First Search Procedure:

  1. Determine if this node is the goal.
    If it is, then a path has been found.
  2. If the left subtree exists, search it.
  3. If the right subtree exists, search it.


  4. If the goal has been found then the algorithm has succeeded to find a route otherwise it has failed.

Breadth First Search

                       A1
                      / \
                    /     \ 
                  /         \ 
                /             \
              /                 \
            /                      \
          /                          \
         H2                           T3
        / \                          / \
       /   \                        /   \
      /     \                      /     \
     /       \                    /       \
    B4        T5                 H6        G7
   / \         \                /         / \
  G8  P9        G10            B11       B12 C13
 / \   \       / \            / \       / \
T14 C15 W16   B   C          P   G     H   P
             /              /     \         \
            P              W       C         W
             \
              W
Search Procedure:
  1. Form a one element queue consisting of the root node.
  2. Until the queue is empty or the goal has been reached, determine if the first element in the queue is the goal node.
    1. If it is the goal then do nothing
    2. otherwise: Remove the first element from the queue and add its children (if any) to the back of the queue.
    If the goal has been found then the algorithm has succeeded to find a route otherwise it has failed.
Breadth first search will be better than depth first if there are a lot of dead ends with long paths to them.

`Optimal Path' Algorithms

Now we need to find not just a solution, but the best solution. Assume there is a cost associated with every node. In our case this will be the total distance traveled so far.

The British Museum Algorithm

Search all possible paths. Use Breadth or Depth first but continue after a solution has been found. Choose the solution with the lowest cost.

This method is Impractical except for trivial problems.

The Branch and Bound Algorithm

Instead of searching all possible paths, search in order of lowest cost. The first path found will be optimal.

Search Procedure:

  1. Form a queue of partial paths. Let the initial queue consist of the zero length, zero step path from the root node to nowhere.
  2. Until the queue is empty or the goal has been reached, determine if the first path in the queue reaches the goal node.
    1. If the first path reaches the goal node then do nothing
    2. otherwise:
      1. Remove the first path from the queue.
      2. Form new paths from the removed path by extending one step.
      3. Add the new paths to the queue.
      4. Sort the queue by total cost, with least cost at the front.
    The first path to the goal that is found must be the optimum path.
                       A0
                      / \
                    /     \ 
                  /         \ 
                /             \
              /                 \
            /                      \
          /                          \
         H4                           T3
        / \                          / \
       /   \                        /   \
      /     \                      /     \
     /       \                    /       \
    B6        T9                 H8        G7
   / \         \                /         / \
  G11 P10       G13            B10       B12 C11
 / \   \       / \            / \       / \
T15 C15 W13   B18 C17        P14 G15   H14 P16
             /              /     \         \
            P22            W17     C19       W19
             \
              W25
This diagram shows the distances traveled to reach each node in the tree. From this, it can be seen that the branch and bound algorithm will visit the nodes in the following order.
                       A1
                      / \
                    /     \ 
                  /         \ 
                /             \
              /                 \
            /                      \
          /                          \
         H3                           T2
        / \                          / \
       /   \                        /   \
      /     \                      /     \
     /       \                    /       \
    B4        T7                 H6        G5
   / \         \                /         / \
  G11 P8        G13            B9        B12 C10
 / \   \       / \            / \       / \
T   C   W14   B   C          P   G     H   P
             /              /     \         \
            P              W       C         W
             \
              W
It will take 14 iterations to find the optimal path.