Heuristic Search

1st Edition

Theory and Applications

Print ISBN: 9780123725127
eBook ISBN: 9780080919737
Imprint: Morgan Kaufmann
Published Date: 20th June 2011
Page Count: 712
55.95 + applicable tax
44.99 + applicable tax
89.95 + applicable tax
Compatible Not compatible
VitalSource PC, Mac, iPhone & iPad Amazon Kindle eReader
ePub & PDF Apple & PC desktop. Mobile devices (Apple & Android) Amazon Kindle eReader
Mobi Amazon Kindle eReader Anything else

Institutional Access


Search has been vital to artificial intelligence from the very beginning as a core technique in problem solving. The authors present a thorough overview of heuristic search with a balance of discussion between theoretical analysis and efficient implementation and application to real-world problems. Current developments in search such as pattern databases and search with efficient use of external memory and parallel processing units on main boards and graphics cards are detailed.

Heuristic search as a problem solving tool is demonstrated in applications for puzzle solving, game playing, constraint satisfaction and machine learning. While no previous familiarity with heuristic search is necessary the reader should have a basic knowledge of algorithms, data structures, and calculus. Real-world case studies and chapter ending exercises help to create a full and realized picture of how search fits into the world of artificial intelligence and the one around us.

Key Features

  • Provides real-world success stories and case studies for heuristic search algorithms
  • Includes many AI developments not yet covered in textbooks such as pattern databases, symbolic search, and parallel processing units


Researchers, professors, and graduate students

Table of Contents

List of Algorithms


Chapter 1. Introduction

1.1. Notational and Mathematical Background

1.2. Search

1.3. Success Stories

1.4. State Space Problems

1.5. Problem Graph Representations

1.6. Heuristics

1.7. Examples of Search Problems

1.8. General State Space Descriptions

1.9. Summary

1.10. Exercises

1.11. Bibliographic Notes

Chapter 2. Basic Search Algorithms

2.1. Uninformed Graph Search Algorithms

2.2. Informed Optimal Search

2.3. *General Weights

2.4. Summary

2.5. Exercises

2.6. Bibliographic Notes

Chapter 3. *Dictionary Data Structures

3.1. Priority Queues

3.2. Hash Tables

3.3. Subset Dictionaries

3.4. String Dictionaries

3.5. Summary

3.6. Exercises

3.7. Bibliographic Notes

Chapter 4. Automatically Created Heuristics

4.1. Abstraction Transformations

4.2. Valtorta's Theorem

4.3. Hierarchical A

4.4. Pattern Databases

4.5. * Customized Pattern Databases

4.6. Summary

4.7. Exercises

4.8. Bibliographic Notes

Chapter 5. Linear-Space Search

5.1. *Logarithmic Space Algorithms

5.2. Exploring the Search Tree

5.3. Branch-and-Bound

5.4. Iterative-Deepening Search

5.5. Iterative-Deepening A*

5.6. Prediction of IDA* Search

5.7. *Refined Threshold Determination

5.8. *Recursive Best-First Search

5.9. Summary

5.10. Exercises

5.11. Bibliographic Notes

Chapter 6. Memory-Restricted Search

6.1. Linear Variants Using Additional Memory

6.2. Nonadmissible Search

6.3. Reduction of the Closed List

6.4. Reduction of the Open List

6.5. Summary

6.6. Exercises


No. of pages:
© Morgan Kaufmann 2012
Morgan Kaufmann
eBook ISBN:
Hardcover ISBN:


"Heuristic Search is a very solid monograph and textbook on (not only heuristic) search. In its presentation it is always more formal than colloquial, it is precise and well structured. Due to its spiral approach it motivates reading it in its entirety." --Zentralblatt MATH 2012

"The authors have done an outstanding job putting together this book on artificial intelligence (AI) heuristic state space search. It comprehensively covers the subject from its basics to the most recent work and is a great introduction for beginners in this field." --BCS.org

"Heuristic search lies at the core of Artificial Intelligence and it provides the foundations for many different approaches in problem solving. This book provides a comprehensive yet deep description of the main algorithms in the field along with a very complete discussion of their main applications. Very well-written, it embellishes every algorithm with pseudo-code and technical studies of their theoretical performance." --Carlos Linares López, Universidad Carlos III de Madrid

"This is an introduction to artificial intelligence heuristic state space search. Authors Edelkamp (U. of Bremen, Germany) and Schrödl (a research scientist at Yahoo! Labs) seek to strike a balance between search algorithms and their theoretical analysis, on the one hand, and their efficient implementation and application to important real-world problems on the other, while covering the field comprehensively from well-known basic results to recent work in the state of the art. Prior knowledge of artificial intelligence is not assumed, but basic knowledge of algorithms, data structures, and calculus is expected. Proofs are included for formal rigor and to introduce proof techniques to the reader. They have organized the material into five sections: heuristic search primer, heuristic search under memory constraints, heuristic search under time constraints, heuristic searc