Introduction to AI

Module 2: creating effective heuristics for search

creating effective heuristics

When you design your informed search implementation for a specific problem, it is important that you create effective heuristics or the informed search will not be any more efficient than uninformed search, nor will it find an optimal answer.

What makes a good heuristic?

When you design your heuristic, you want to make sure it is going to actually help make the search more efficient.  Follow these guidelines to ensure h(n) is effective.

How to create a heuristic 

Creating a heuristic in a non-Euclidean space can feel challenging.  We offer some tips to help you to design effective heuristics.

Example heuristics

The two most commonly used heuristics for Euclidean space are

  • Euclidean distance or straight line distance: there is not a shorter path than a straight line between two points so this is the most optimistic estimate one can give in a Euclidean space.
  • Manhattan distance or city block distance: if you are in a gridded environment (or in a city!), straight lines are not possible and thus the city block distance is used
  • Easter egg: if you got this far, please post a picture of your pet (or a friend’s pet, or a favorite cute animal!) to #random on slack and all such posts will get extra credit