6.3. Non-exhaustive informed search

The search strategies discussed until now are all exhaustive: they will all search the complete search space in the worst case. This is so because all children of a certain node will be put on the agenda, in some order. Exhaustive search is often impractical, since the size of the agenda grows exponentially with the search depth. The use of a heuristic offers the possibility of keeping only a selection of best nodes on the agenda. Such non-exhaustive search strategies are, of course, not guaranteed to be complete, and should only be applied in combination with a reasonably informed heuristic.

Beam search is a form of best-first search in which the number of nodes on the agenda is limited. In its most simple form, the agenda is of fixed size. Alternatively, one could allow the agenda to grow polynomially (instead of exponentially) with the search depth. The effect of this strategy is, that only a ‘beam’ of the search space is searched:

search_beam(Agenda,Goal):-
    search_beam(1,Agenda,[],Goal).

search_beam(D,[],NextLayer,Goal):-
    D1 is D+1,
    search_beam(D1,NextLayer,[],Goal).
search_beam(D,[Goal|Rest],NextLayer,Goal):-
    goal(Goal).
search_beam(D,[Current|Rest],NextLayer,Goal):-
    children(Current,Children),
    add_beam(D,Children,NextLayer,NewNextLayer),
    search_beam(D,Rest,NewNextLayer,Goal).

In this program, two agendas are maintained, one for the current level, and one for the children of the nodes on the current level. Once the current level is exhausted, the agenda’s are swapped and the depth count is increased. The depth count is passed on to the predicate add_beam/4, in order to decide how many children to add to the agenda for the next level.

Exercise 6.6

Extend the program of Exercise 6.3 with beam search with fixed agenda size. Demonstrate the non-optimality of the search strategy.

If we limit the size of the agenda to 1, we arrive at a search strategy called hill-climbing. It is also called greedy search, since there is no backtracking involved. Hill-climbing is the type of search employed by a wanderer who wants to reach the top of a hill by always moving in the steepest direction. Clearly, she will reach the top of a hill (and never get off it), but it is not necessarily the highest one.

The predicate search_hc/2 below implements a hill-climbing search strategy. Instead of maintaining an agenda of nodes yet to be investigated, it maintains a single node in its first argument. Therefore, hill-climbing has some similarity with depth-first search with implicit agenda:

search_hc(Goal,Goal):-
    goal(Goal).
search_hc(Current,Goal):-
    children(Current,Children),
    select_best(Children,Best),
    search_hc(Best,Goal).

The predicate select_best/2 selects the best child of the current node, according to the heuristic value to be optimised. To stress that backtracking is not needed after the best child has been selected, one can place a cut before the recursive call in the second clause.