logo

Simply Logical
Intelligent Reasoning by Example

  • Simply Logical
  • Preface
  • I. Logic and Logic Programming
    • 1. A brief introduction to clausal logic
      • 1.1. Answering queries
      • 1.2. Recursion
      • 1.3. Structured terms
      • 1.4. What else is there to know about clausal logic?
    • 2. Clausal logic and resolution: theoretical backgrounds
      • 2.1. Propositional clausal logic
      • 2.2. Relational clausal logic
      • 2.3. Full clausal logic
      • 2.4. Definite clause logic
      • 2.5. The relation between clausal logic and Predicate Logic
      • 2.6. Further reading
    • 3. Logic Programming and Prolog
      • 3.1. SLD-resolution
      • 3.2. Pruning the search by means of cut
      • 3.3. Negation as failure
      • 3.4. Other uses of cut
      • 3.5. Arithmetic expressions
      • 3.6. Accumulators
      • 3.7. Second-order predicates
      • 3.8. Meta-programs
      • 3.9. A methodology of Prolog programming
      • 3.10. Further reading
  • II. Reasoning with structured knowledge
    • 4. Representing structured knowledge
      • 4.1. Trees as terms
      • 4.2. Graphs generated by a predicate
      • 4.3. Inheritance hierarchies
      • 4.4. Further reading
    • 5. Searching graphs
      • 5.1. A general search procedure
      • 5.2. Depth-first search
      • 5.3. Breadth-first search
      • 5.4. Forward chaining
      • 5.5. Further reading
    • 6. Informed search
      • 6.1. Best-first search
      • 6.2. Optimal best-first search
      • 6.3. Non-exhaustive informed search
      • 6.4. Further reading
  • III. Advanced reasoning techniques
    • 7. Reasoning with natural language
      • 7.1. Grammars and parsing
      • 7.2. Definite Clause Grammars
      • 7.3. Interpretation of natural language
      • 7.4. Further reading
    • 8. Reasoning with incomplete information
      • 8.1. Default reasoning
      • 8.2. The semantics of incomplete information
      • 8.3. Abduction and diagnostic reasoning
      • 8.4. The complete picture
      • 8.5. Further reading
    • 9. Inductive reasoning
      • 9.1. Generalisation and specialisation
      • 9.2. Bottom-up induction
      • 9.3. Top-down induction
      • 9.4. Further reading
  • Additional materials
    • 10. A catalogue of useful predicates
      • 10.1. Built-in predicates
      • 10.2. A library of utility predicates
    • 11. Two programs for logical conversion
      • 11.1. From Predicate Logic to clausal logic
      • 11.2. Predicate Completion
    • 12. Answers to selected exercises
      • 12.1. A brief introduction to clausal logic
      • 12.2. Clausal logic and resolution: theoretical backgrounds
      • 12.3. Logic Programming and Prolog
      • 12.4. Representing structured knowledge
      • 12.5. Searching graphs
      • 12.6. Informed search
      • 12.7. Reasoning with natural language
      • 12.8. Reasoning with incomplete information
      • 12.9. Inductive reasoning
  • Simply Logical Organisation
  • Original Book Home
DOI
Licence
  • repository
  • open issue
  • suggest edit
  • .md

Non-exhaustive informed search

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.

previous

6.2. Optimal best-first search

next

6.4. Further reading

By Peter Flach and Kacper Sokol, University of Bristol, United Kingdom
© Copyright 2015–2022.

This work is licenced under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International Licence.

This book discusses methods to implement intelligent reasoning by means of Prolog programs. The book is written from the shared viewpoints of Computational Logic, which aims at automating various kinds of reasoning, and Artificial Intelligence, which seeks to implement aspects of intelligent behaviour on a computer.