Module 2: Idealized Searches

Adding information to our searches

Uninformed searches can be useful in many situations. However, often the human can provide helpful strategies to guide the agent in the search, which means we can improve our search efficiency and find optimal paths in many cases.  This topic focuses on informed searches.  Both algorithms will use information provided to estimate how far it is to the goal from the current node but they differ after that.

Greedy Best First Search

• Reading
  • Read Section 3.5-3.6 of Chapter 3 (Informed (Heuristic) Search Strategies through Heuristic Functions)
• The first search algorithm we will discuss in this module is one that uses only the heuristic information provided by the user to estimate distance from the current node to the goal.  This is called greedy best first search
  • Link to the slides
• Complete the assignment on using GBFS

A* Search

• The second algorithm we will discuss combines the heuristic with the actual path costs to achieve an optimal path (with some requirements, discussed in the video and in the chapter). This is A* search.
  • Link to the slides
  • Explore some examples of using A* on a different graph! 
• Complete the assignment on using A* 

Making Good Heuristics for A*

• I did something a little different for your final part of this topic.  Instead of recording a video, I made a page to read about how to create effective heuristics
  • Complete the exercise on making effective heuristics
  • Feel free to discuss the heuristic ideas for these two problems in the #general channel!  You can learn a lot from each other!

Next topic

• You might think that search methods do not have ethical implications but they do!  Jump to the next topic on ethics for search.