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.