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.
-
Is it possible? i.e. find any route.
-
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:
-
Determine if this node is the goal.
If it is, then a path has been found.
-
If the left subtree exists, search it.
-
If the right subtree exists, search it.
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:
-
Form a one element queue consisting of the root node.
-
Until the queue is empty or the goal has been reached, determine if the
first element in the queue is the goal node.
-
If it is the goal then do nothing
-
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:
-
Form a queue of partial paths. Let the initial queue consist of the zero
length, zero step path from the root node to nowhere.
-
Until the queue is empty or the goal has been reached, determine if the
first path in the queue reaches the goal node.
-
If the first path reaches the goal node then do nothing
-
otherwise:
-
Remove the first path from the queue.
-
Form new paths from the removed path by extending one step.
-
Add the new paths to the queue.
-
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.