|
Ans. Depth-first searches are performed by
diving downward into a tree as quickly possible. It does this
by always generating a child node from the most recently expanded
node, then generating that child's children, and so on until
a goal found or some cutoff depth point d is reached.
If a goal is not found when a 1 node is reached or at the
cutoff point, the program backtracks to the most recently
expanded node and generates another of its children. This
process continues until goal is found or failure occurs.
The following figure shows an example of a depth-first search:
Depth-first places the newly generated children at the head
of the queue so that they will be chosen first The search
proceeds as follows.
1. Place the starting node s on the queue.
2. If the queue is empty, return failure and stop.
3. If the first element on the queue is a goal node g,
return success and stop. Otherwise,
4. Remove and expand the first element, and place the children
at the front of the queue (in any order).
5. Return to step 2.
The depth-first search is preferred over the breadth-first
when the search tree is known to have a plentiful number of
goals. Otherwise, depth-first may never find a solution.
The depth cutoff also introduces some problems. If it is set
too shallow, goals may be missed; if set too deep, extra computation
may be performed.
The time complexity of the depth-first tree search is the
same as that for breadth-first, O(bd). It
is less demanding in space requirements, however, since only
the path from the starting node to the current node needs
to be stored. Therefore, if the depth cutoff is d, the
space complexity is .just O(d).
|
AI
Contents
