6. Informed search

The search strategies of the previous chapter do not make any assumptions about the plausibility of a certain node in the search space leading to a goal. Such a form of search is called blind search. Alternatively, search strategies which do make such assumptions are called informed search strategies. The extra information which is incorporated in the search process is provided by an evaluation function \(h\) called a heuristic, which estimates how far a given node is from a goal. This information can be used in several ways. If we use it to order the nodes on the agenda, such that most promising nodes are tried first, the resulting search method is called best-first search. In Section 6.2, we will discuss a complete variant of best-first search called the A algorithm, and investigate the conditions under which this algorithm is optimal. In Section 6.3, we will discuss non-exhaustive informed search strategies, that can be derived from best-first search by limiting the size of the agenda.