Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).
3.7.5 Direction of Search
The size of the search space of the generic search algorithm on finite uniform graphs is bk, where b is the branching factor and k is the path length. Anything that can be done to reduce k or b can potentially give great savings. The abstract definition of the graph-searching method of problem solving is symmetric in the sense that the algorithm can either begin with a start node and search forward for a goal node or begin with a goal node and search backward for a start node in the inverse graph. Note that in many applications the goal is determined implicitly by a Boolean function that returns true when a goal is found, and not explicitly as a set of nodes, so backward search may not be possible.
For those cases where the goal nodes are explicit, it may be more efficient to search in one direction than in the other. The size of the search space is exponential in the branching factor. It is typically the case that forward and backward searches have different branching factors. A general principle is to search forward or backward, depending on which has the smaller branching factor.
The following sections consider some ways in which search efficiency can be improved beyond this for many search spaces.
