Informed Search and Heuristics

What Is Informed Search?

Informed search uses additional knowledge to guide exploration toward promising states.

This knowledge is often represented by a heuristic function.

A heuristic estimates how close a state is to the goal or how much effort remains before reaching it.

For example, a navigation algorithm may use the straight-line distance between the current location and the destination as an estimate of the remaining travel distance.

A heuristic does not necessarily provide the exact cost. Its purpose is to help the algorithm decide which states to explore first.

What Is a Heuristic Function?

A heuristic function is commonly represented as:

[
h(n)
]

Here, (h(n)) estimates the remaining cost from node (n) to the goal.

For a route-planning problem, a heuristic might estimate the remaining distance to the destination.

For a grid-based puzzle, it might count how many tiles are in the wrong positions.

A useful heuristic helps reduce unnecessary exploration.

1. Greedy Best-First Search

Greedy Best-First Search selects the node with the smallest estimated remaining cost.

Its evaluation function is:

[
f(n)=h(n)
]

The algorithm focuses on which node appears closest to the goal, rather than considering the total cost already spent reaching that node.

Advantage: It can reach promising states quickly when the heuristic is useful.

Limitation: It may select a route that looks promising but has a high total cost. It is not generally guaranteed to find the optimal solution.

2. A* Search

A* Search combines the cost already incurred with the estimated remaining cost.

Its evaluation function is:

[
f(n)=g(n)+h(n)
]

Where:

• (g(n)) is the actual cost from the starting state to node (n).
• (h(n)) is the estimated cost from node (n) to the goal.
• (f(n)) is the estimated total cost of a solution through node (n).

A* balances progress already made with the estimated cost of reaching the goal.

Example

Suppose an algorithm is choosing between two nodes:

Greedy Best-First Search prefers C because its heuristic value is 2, compared with B's value of 8.

A* also prefers C in this example because its total estimated cost is 8, compared with B's score of 11.

However, in another problem, the two algorithms may choose different nodes because A* accounts for the cost already incurred.

Properties of a Good Heuristic

An effective heuristic should be relevant to the problem and inexpensive enough to calculate.

For A* optimality, a commonly used requirement is that the heuristic be admissible: it never overestimates the true minimum remaining cost.

In graph search, consistency is another useful property. When the heuristic is consistent and the implementation handles repeated states appropriately, A* can efficiently preserve optimality.

Applications of Informed Search

• Navigation and route planning.
• Puzzle solving.
• Game-playing systems.
• Robot pathfinding.
• Planning and scheduling.
• Automated problem-solving.