The techniques that we have described can be applied to many
problem solving tasks. However, for realistic problems we
often run into problems. One problem relates to the
complexity of the algorithms. For brute force
search techniques such as breadth first and depth first
we may end up having to search an enormous number of nodes in the
search space to find a solution. For example, if there are (on average)
n successors to every node in the search space, and our
solution is at depth d, then in breadth first search we
may need to search n nodes. In n is, say, 20 and d is 6 then
we may need to search over 60 million nodes. For depth first
search we may be luckier, and happen to hit on a solution soon,
but then if there isn't a solution on the first branch we try
we may end up having to search even more nodes.
For graph search (where we check to see if we have already
searched a node before) things may be a bit better, but maybe
not much (and anyway, it may be too expensive in terms of
memory requirements). Even using heuristic search
may not help much, unless our evaluation functions are very good.
The average number of successor states for nodes in the search space is known as the branching factor. For search to be tractable we want our search space to have a fairly small branching factor. The branching factor will depend on how a problem is formulated. In state space search the branching factor can be reduced by applying some (human!) intelligence when specifying the rules or operators for deriving succesor states - we want to make sure any pointless actions/sucessor states are not even considered in the search. It may also be reduced by choosing appropriately whether to search forward, from the initial state, or backwards, from the goal state. The branching factor in each case may be very different. This is what we were talking about in the section on rules, where we considered forward vs backwards reasoning.
If none of this helps then we have a combinatorial explosion! We just have too many combinations to try, and the deeper in the tree we search the worse it gets. Largely because of this problem, general purpose search techniques are often inadequate for serious problem solving. They need to at least be augmented with more specialized, domain specific problem solving techniques. (Nevertheless, it is important to first understand the general purpose search techniques, and their limitations, before developing more specialized algorithms.)