(ch:5)=
# Searching graphs #
As explained earlier, a *search problem* is defined by a *search space*, which is a graph with one or more *starting nodes* and one or more *goal nodes*. Given a search space, a *solution* is a path from a starting node to a goal node . A *cost function* $c$ assigns a number to each arc from $n_1$ to $n_2$, specifying the *cost* of moving from $n_1$ to $n_2$. The cost of a path is the sum of the costs of the arcs in the path. Given a search space and a cost function, an *optimal solution* is a solution with minimal cost. A trivial example of a cost function is $c(a)=1$ for each arc $a$, in which case the cost of a path equals the length of the path, and an optimal solution is a shortest path. For SLD proofs, such a cost function would measure the depth of the proof tree.
+++
In this chapter, we will discuss and implement some basic techniques for finding solutions in search spaces. Their common denominator is that they are *exhaustive*: that is, in the worst case they will eventually visit every node in the search space along every possible path, before finding a solution. On the other hand, they differ with regard to:
* *completeness* -- will a solution always be found?
* *optimality* -- will shorter paths be found before longer ones?
* *efficiency* -- what are the runtime and memory requirements?
We start with a general discussion of the problem of search. Then, we will discuss the basic exhaustive search strategies: depth-first search, breadth-first search, and forward chaining.