Section 3.4 Informed Search

In the previous section, you learned about uninformed search strategies, where the algorithm had no additional information about the problem beyond its basic definition. Uninformed search methods lack problem-specific knowledge and are too slow for most real-world problems. The good news is that in many situations, we can dramatically improve search speed by using knowledge about the problem itself. This is the core idea behind informed search, also known as heuristic search.

Informed search algorithms use problem-specific knowledge to find solutions more efficiently than uninformed methods. The key difference is that informed search uses a heuristic—a rule of thumb that estimates how close a state is to the goal. This knowledge allows algorithms to prioritize promising directions and dramatically reduce the number of states explored.

Think of It This Way....

Imagine you’re trying to find a friend’s house in an unfamiliar city. An uninformed search would be like walking down every street systematically until you happen to find the right house. An informed search is like having a GPS that gives you the straight-line distance to your destination—you still don’t know every turn, but you at least know which direction is generally correct.

Subsection 3.4.1 What Is a Heuristic?

A heuristic is a rule of thumb, a guideline, or an educated guess that helps point the search in a promising direction. In everyday life, we use heuristics all the time:

"If you’re lost in a forest, follow a stream downhill—it will eventually lead to civilization."
"When packing a suitcase, put heavy items at the bottom."
"In a restaurant, choose the dish the waiter recommends—it’s probably the freshest."

In AI search, a heuristic estimates how far a given state is from the goal. It doesn’t need to be perfect—it just needs to be useful. The better the heuristic, the faster the search will find a solution.

For example, in a route-finding problem, a good heuristic might be the straight-line distance to your destination. Even though you can’t drive in a straight line, this estimate helps the search focus on cities that are generally in the right direction.

Subsection 3.4.2 Best-First Search

Best-first search is a general approach where the algorithm always chooses the most promising node to explore next. It uses an evaluation function to determine which node looks best. The algorithm always picks the node that seems closest to the goal—at least according to its heuristic.

However, the evaluation function may not be perfect. The node that appears to be the "best" might not actually be the best in reality. Different strategies use different ways of evaluating which node is "best."

Subsection 3.4.3 Greedy Best-First Search

Greedy best-first search always expands the node that appears closest to the goal. It uses only the heuristic to make its decision, completely ignoring how much it has already cost to get there.

How it works:: At each step, pick the node with the lowest heuristic value—the one that seems closest to the goal.
Strengths:: Very fast—it heads straight for what looks like the goal.
Weaknesses:: It can be fooled. A path that looks good at first might turn out to be a dead end, and by then you’ve already invested time exploring it.

Analogy:.

Imagine you’re trying to find a friend’s house in an unfamiliar city. You know the general direction, so you just keep heading that way, turning down any street that points toward your destination. You might get there quickly, or you might hit a dead end and have to backtrack.

Best for: Situations where speed matters more than finding the absolute best path, and you have a reliable heuristic.

Subsection 3.4.4 Uniform-Cost Search

Uniform-cost search uses the cost of the path so far to determine which node to explore next. It expands the node with the lowest path cost (how expensive it has been to get there).

How it works:: At each step, pick the node that has cost the least to reach.
Strengths:: It always finds the cheapest path.
Weaknesses:: It doesn’t use any information about the goal, so it might wander around exploring cheap paths that lead nowhere.

Analogy:.

Imagine you’re looking for the cheapest way to travel across the country. You always take the cheapest next leg of the trip, without considering whether it’s actually taking you in the right direction. You might find a very cheap route—or you might end up in the wrong state entirely!

Important: Uniform-cost search is actually considered an uninformed strategy because it doesn’t use any goal information—it only looks backward at where you’ve been, not forward at where you’re going.

Subsection 3.4.5 A* Search

A* search (pronounced "A-star") combines the best of both worlds. It considers both how much it has cost to get to a node and how much it will cost to reach the goal from there. It was first published in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael, and remains one of the most widely used search algorithms more than fifty years later.

How it works:

At each step, pick the node with the lowest value of:

f(n) = cost so far + estimated cost to goal

Where:

cost so far (g) = how expensive it has been to reach this node
estimated cost to goal (h) = how far this node appears to be from the goal

Analogy:.

Imagine planning a road trip. You consider both how far you’ve already driven and how far you still need to go. If one route has already taken you 100 miles but you’re almost there, while another has only taken you 10 miles but you’re still far away, A* will consider both factors to choose the better route.

Strengths:

It finds the optimal (best) solution—provided your heuristic is good
It’s much faster than uninformed search
It balances exploring new areas with following promising paths

Weaknesses:

It uses a lot of memory—it must store all nodes it’s considering
It requires a good heuristic to work well
For very large problems, even A* can be too slow

Best for: Route planning, game pathfinding, robotics, and any problem where you need a guaranteed best path and have a good heuristic available.

Properties of A*:

Table 3.4.1. Properties of A* Search

Property	What It Means
Complete	Yes—it will always find a solution if one exists
Optimal	Yes—but only if the heuristic is admissible
Time	Can be slow, but much faster than uninformed search with a good heuristic
Space	Uses a lot of memory—it stores many nodes at once

Subsection 3.4.6 Heuristic Functions

The quality of a heuristic is crucial. A good heuristic can make A* find a solution in milliseconds. A bad heuristic can make it barely better than blind exploration.

Subsection 3.4.7 Admissible Heuristics

For A* to guarantee finding the best possible solution, the heuristic must be admissible. This is a fancy word that simply means: the heuristic never overestimates the true cost. In other words, it’s always optimistic—it thinks you’re at least as close to the goal as you actually are.

Example: In route planning, straight-line distance is admissible because a straight line is always the shortest possible distance. The actual driving distance will always be at least as long as the straight-line distance.

If a heuristic occasionally overestimates, the search might ignore the best path because it looks too expensive. It might then find a worse path and mistakenly think it’s the best one.

Examples of admissible heuristics:

Straight-line distance in route-finding
Number of tiles in the wrong position in the 8-puzzle
Sum of distances of tiles from their goal position (called Manhattan distance) in the 8-puzzle

Subsection 3.4.8 Consistency

A heuristic is consistent if a simple rule holds: the estimated cost from a node to the goal should never exceed the cost of moving to a neighboring node plus the estimated cost from that neighbor to the goal.

Don’t worry too much about the formal definition. What matters is this: most well-designed heuristics are consistent, and consistency guarantees that A* will find the best solution.

Subsection 3.4.9 Comparing Informed Search Strategies

Table 3.4.2. Comparison of informed search strategies

Algorithm	Complete?	Finds Best?	Memory Use	Best For
Greedy BFS	No	No	Moderate	Speed over optimality
Uniform-Cost	Yes	Yes	High	Cheapest path, no heuristic
A*	Yes	Yes*	High	Optimal path with good heuristic

*Finds the best solution only when the heuristic is admissible and consistent

Subsection 3.4.10 When to Use Informed Search

Informed search is the right tool when:

You have a good heuristic — If you can define a reliable rule of thumb, informed search will be much faster than uninformed search.
The problem is large — For large state spaces, uninformed search is often too slow to be practical.
You need optimality — With an admissible heuristic, A* guarantees the best solution.
Speed matters — Even a simple heuristic can dramatically reduce search time compared to uninformed methods.

Choosing Your Search Strategy.

Think of it like choosing a travel strategy: If you have a good map (heuristic), use it to plan your route (A*). If you’re in a hurry and don’t need the absolute best route, just head toward your destination (Greedy BFS). If you’re on a tight budget and the map is unreliable, take the cheapest steps (Uniform-Cost).

You have attempted of activities on this page.

Prev Top Next