Course contentsShow
← Computer Science
Lesson 2749 of 2,87261. AI and Search AlgorithmsFree lesson

Introduction to Informed Search

Learn how heuristic functions guide search algorithms toward goals more efficiently than uninformed methods.

Introduction to Informed Search

What you'll learn: How search algorithms can use problem-specific knowledge to find goals faster than blindly exploring every possibility.

The Problem with Uninformed Search

In your previous lessons, you explored strategies like BFS, DFS, and Uniform-Cost Search. These are uninformed because they treat all unexpanded states equally—they have no sense of whether one path "looks more promising" than another. They work systematically but can waste time exploring directions that lead away from the goal.

What Makes Search "Informed"?

Informed search (also called heuristic search) uses a heuristic function—a problem-specific estimate of how far a state is from the goal. Think of it like having a compass when navigating: uninformed search is like exploring every street methodically, while informed search is like walking toward where your compass points north, making educated guesses about which paths are likely shorter.

The Heuristic Function

A heuristic function h(n) estimates the cost from state n to the nearest goal. For example:

  • In route-finding, h(n) might be the straight-line distance to the destination
  • In a sliding puzzle, h(n) might count how many tiles are out of place

The heuristic guides the search by prioritizing states that appear closer to the goal. It doesn't guarantee finding those states first, but it makes the search much more efficient in practice by expanding fewer nodes.

Why This Matters

Informed search dramatically reduces the portion of the state space you must explore. Instead of treating the frontier as a simple queue, you use the heuristic to decide which states look most promising—letting you reach the goal with far fewer expansions than uninformed methods.

Key Takeaway: Informed search uses heuristic functions to estimate goal distance, guiding algorithms to explore promising paths first and achieving greater efficiency than uninformed approaches.