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

Informed search

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.

previous

5.5. Further reading

next

6.1. Best-first search

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.