4 Informed Search Algorithms

 

This chapter covers

  • Defining informed search
  • Learning how to solve minimum spanning tree problem
  • Learning how to find the shortest path using informed search algorithms
  • Solving a real-world routing problem using these algorithms

In the previous chapter, we covered blind search algorithms, which were algorithms in which no information about the search space is needed. In this chapter, we’ll look at how search can be further optimized if we utilize some information about the search space during the search. As problems and search spaces become larger and more complex, so too will the complexity of the algorithms themselves increase. We’ll start by introducing informed search algorithms followed by discussing minimum spanning tree algorithms and shortest path search algorithms. A routing problem is presented as a real-life application to show how to use these algorithms.

4.1 Introduction to Informed Search

 

4.2 Minimum Spanning Tree (MST) Algorithms

 
 

4.3 Shortest Path Algorithms

 
 

4.3.1 Hill Climbing Algorithm

 
 
 

4.3.2 Beam Search Algorithm

 
 
 
 

4.3.3 A* Search Algorithm

 
 
 

4.3.4 Hierarchical Approaches

 
 

4.4 Applying Informed Search to Routing Problem

 
 

4.4.1 Hill Climbing for Routing

 
 

4.4.2 Beam Search for Routing

 
 
 

4.4.3 A* for Routing

 
 
 

4.4.4 Contraction Hierarchies for Routing

 
 

4.5 Summary

 
 
 
 
sitemap

Unable to load book!

The book could not be loaded.

(try again in a couple of minutes)

manning.com homepage
test yourself with a liveTest