Home Page Icon
Home Page
Table of Contents for
Table of Contents
Close
Table of Contents
by Stefan Schroedl, Stefan Edelkamp
Heuristic Search
Cover Image
Table of Contents
Front Matter
Copyright
List of Algorithms
Preface
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
6.7. Bibliographic Notes
Chapter 7. Symbolic Search
7.1. Boolean Encodings for Set of States
7.2. Binary Decision Diagrams
7.3. Computing the Image for a State Set
7.4. Symbolic Blind Search
7.5. Limits and Possibilities of BDDs
7.6. Symbolic Heuristic Search
7.7. * Refinements
7.8. Symbolic Algorithms for Explicit Graphs
7.9. Summary
7.10. Exercises
7.11. Bibliographic Notes
Chapter 8. External Search
8.1. Virtual Memory Management
8.2. Fault Tolerance
8.3. Model of Computation
8.4. Basic Primitives
8.5. External Explicit Graph Search
8.6. External Implicit Graph Search
8.7. * Refinements
8.8. * External Value Iteration
8.9. * Flash Memory
8.10. Summary
8.11. Exercises
8.12. Bibliographic Notes
Chapter 9. Distributed Search
9.1. Parallel Processing
9.2. Parallel Depth-First Search
9.3. Parallel Best-First Search Algorithms
9.4. Parallel External Search
9.5. Parallel Search on the GPU
9.6. Bidirectional Search
9.7. Summary
9.8. Exercises
9.9. Bibliographic Notes
Chapter 10. State Space Pruning
10.1. Admissible State Space Pruning
10.2. Nonadmissible State Space Pruning
10.3. Summary
10.4. Exercises
10.5. Bibliographic Notes
Chapter 11. Real-Time Search
11.1. LRTA*
11.2. LRTA* with Lookahead One
11.3. Analysis of the Execution Cost of LRTA*
11.4. Features of LRTA*
11.5. Variants of LRTA*
11.6. How to Use Real-Time Search
11.7. Summary
11.8. Exercises
11.9. Bibliographic Notes
Chapter 12. Adversary Search
12.1. Two-Player Games
12.2. *Multiplayer Games
12.3. General Game Playing
12.4. AND/OR Graph Search
12.5. Summary
12.6. Exercises
12.7. Bibliographic Notes
Chapter 13. Constraint Search
13.1. Constraint Satisfaction
13.2. Consistency
13.3. Search Strategies
13.4. NP-Hard Problem Solving
13.5. Temporal Constraint Networks
13.6. *Path Constraints
13.7. *Soft and Preference Constraints
13.8. *Constraint Optimization
13.9. Summary
13.10. Exercises
13.11. Bibliographic Notes
Chapter 14. Selective Search
14.1. From State Space Search to Minimization
14.2. Hill-Climbing Search
14.3. Simulated Annealing
14.4. Tabu Search
14.5. Evolutionary Algorithms
14.6. Approximate Search
14.7. Randomized Search
14.8. Ant Algorithms
14.9. * Lagrange Multipliers
14.10. * No-Free-Lunch
14.11. Summary
14.12. Exercises
14.13. Bibliographic Notes
Chapter 15. Action Planning
15.1. Optimal Planning
15.2. Suboptimal Planning
15.3. Bibliographic Notes
Chapter 16. Automated System Verification
16.1. Model Checking
16.2. Communication Protocols
16.3. Program Model Checking
16.4. Analyzing Petri Nets
16.5. Exploring Real-Time Systems
16.6. Analyzing Graph Transition Systems
16.7. Anomalies in Knowledge Bases
16.8. Diagnosis
16.9. Automated Theorem Proving
16.10. Bibliographic Notes
Chapter 17. Vehicle Navigation
17.1. Components of Route Guidance Systems
17.2. Routing Algorithms
17.3. Cutting Corners
17.4. Bibliographic Notes
Chapter 18. Computational Biology
18.1. Biological Pathway
18.2. Multiple Sequence Alignment
18.3. Bibliographic Notes
Chapter 19. Robotics
19.1. Search Spaces
19.2. Search under Incomplete Knowledge
19.3. Fundamental Robot-Navigation Problems
19.4. Search Objective
19.5. Search Approaches
19.6. Greedy Localization
19.7. Greedy Mapping
19.8. Search with the Freespace Assumption
19.9. Bibliographic Notes
Bibliography
Search in book...
Toggle Font Controls
Playlists
Add To
Create new playlist
Name your new playlist
Playlist description (optional)
Cancel
Create playlist
Sign In
Email address
Password
Forgot Password?
Create account
Login
or
Continue with Facebook
Continue with Google
Sign Up
Full Name
Email address
Confirm Email Address
Password
Login
Create account
or
Continue with Facebook
Continue with Google
Prev
Previous Chapter
Cover Image
Next
Next Chapter
Front Matter
Table of Contents
Cover Image
Front Matter
Copyright
List of Algorithms
Preface
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
6.7. Bibliographic Notes
Chapter 7. Symbolic Search
7.1. Boolean Encodings for Set of States
7.2. Binary Decision Diagrams
7.3. Computing the Image for a State Set
7.4. Symbolic Blind Search
7.5. Limits and Possibilities of BDDs
7.6. Symbolic Heuristic Search
7.7. * Refinements
7.8. Symbolic Algorithms for Explicit Graphs
7.9. Summary
7.10. Exercises
7.11. Bibliographic Notes
Chapter 8. External Search
8.1. Virtual Memory Management
8.2. Fault Tolerance
8.3. Model of Computation
8.4. Basic Primitives
8.5. External Explicit Graph Search
8.6. External Implicit Graph Search
8.7. * Refinements
8.8. * External Value Iteration
8.9. * Flash Memory
8.10. Summary
8.11. Exercises
8.12. Bibliographic Notes
Chapter 9. Distributed Search
9.1. Parallel Processing
9.2. Parallel Depth-First Search
9.3. Parallel Best-First Search Algorithms
9.4. Parallel External Search
9.5. Parallel Search on the GPU
9.6. Bidirectional Search
9.7. Summary
9.8. Exercises
9.9. Bibliographic Notes
Chapter 10. State Space Pruning
10.1. Admissible State Space Pruning
10.2. Nonadmissible State Space Pruning
10.3. Summary
10.4. Exercises
10.5. Bibliographic Notes
Chapter 11. Real-Time Search
11.1. LRTA*
11.2. LRTA* with Lookahead One
11.3. Analysis of the Execution Cost of LRTA*
11.4. Features of LRTA*
11.5. Variants of LRTA*
11.6. How to Use Real-Time Search
11.7. Summary
11.8. Exercises
11.9. Bibliographic Notes
Chapter 12. Adversary Search
12.1. Two-Player Games
12.2. *Multiplayer Games
12.3. General Game Playing
12.4. AND/OR Graph Search
12.5. Summary
12.6. Exercises
12.7. Bibliographic Notes
Chapter 13. Constraint Search
13.1. Constraint Satisfaction
13.2. Consistency
13.3. Search Strategies
13.4. NP-Hard Problem Solving
13.5. Temporal Constraint Networks
13.6. *Path Constraints
13.7. *Soft and Preference Constraints
13.8. *Constraint Optimization
13.9. Summary
13.10. Exercises
13.11. Bibliographic Notes
Chapter 14. Selective Search
14.1. From State Space Search to Minimization
14.2. Hill-Climbing Search
14.3. Simulated Annealing
14.4. Tabu Search
14.5. Evolutionary Algorithms
14.6. Approximate Search
14.7. Randomized Search
14.8. Ant Algorithms
14.9. * Lagrange Multipliers
14.10. * No-Free-Lunch
14.11. Summary
14.12. Exercises
14.13. Bibliographic Notes
Chapter 15. Action Planning
15.1. Optimal Planning
15.2. Suboptimal Planning
15.3. Bibliographic Notes
Chapter 16. Automated System Verification
16.1. Model Checking
16.2. Communication Protocols
16.3. Program Model Checking
16.4. Analyzing Petri Nets
16.5. Exploring Real-Time Systems
16.6. Analyzing Graph Transition Systems
16.7. Anomalies in Knowledge Bases
16.8. Diagnosis
16.9. Automated Theorem Proving
16.10. Bibliographic Notes
Chapter 17. Vehicle Navigation
17.1. Components of Route Guidance Systems
17.2. Routing Algorithms
17.3. Cutting Corners
17.4. Bibliographic Notes
Chapter 18. Computational Biology
18.1. Biological Pathway
18.2. Multiple Sequence Alignment
18.3. Bibliographic Notes
Chapter 19. Robotics
19.1. Search Spaces
19.2. Search under Incomplete Knowledge
19.3. Fundamental Robot-Navigation Problems
19.4. Search Objective
19.5. Search Approaches
19.6. Greedy Localization
19.7. Greedy Mapping
19.8. Search with the Freespace Assumption
19.9. Bibliographic Notes
Bibliography
Index
Add Highlight
No Comment
..................Content has been hidden....................
You can't read the all page of ebook, please click
here
login for view all page.
Day Mode
Cloud Mode
Night Mode
Reset