Back to Study Material Artificial Intelligence

Search methods

Search methods in AI are divided into two broad categories: uninformed search, which uses no information about how close a state is to the goal, and inform...

Search methods

Uninformed vs Informed Search

Search methods in AI are divided into two broad categories: uninformed search, which uses no information about how close a state is to the goal, and informed search, which uses such knowledge in the form of a heuristic to guide exploration more efficiently.

Breadth-first search expands the shallowest unexpanded node first by processing states level by level. It is complete, meaning it will always find a solution if one exists, and it is optimal when all step costs are equal. Its weakness is memory consumption: it must store every node on the current frontier, which grows exponentially with depth. Depth-first search explores as deep as possible before backtracking. It uses far less memory but is neither complete in infinite state spaces nor optimal. Uniform-cost search extends breadth-first search by always expanding the lowest path-cost node, making it optimal for arbitrary step costs.

Greedy best-first search is an informed method that expands the node that appears closest to the goal according to a heuristic function. It is fast but not optimal and can get trapped in dead ends. A-star search combines the actual path cost from the start with the heuristic estimate to the goal. When the heuristic is admissible, meaning it never overestimates the true cost, A-star is both complete and optimal. It is the most widely used informed search algorithm.

A Real Example

Google Maps uses a variant of A-star with a heuristic based on straight-line distance to find driving routes efficiently. The heuristic ensures the algorithm focuses computation toward the destination rather than exploring roads in every direction equally.

Exam Tip

Questions often ask you to compare search algorithms on completeness, optimality, time complexity, and space complexity. Memorise this four-property matrix for BFS, DFS, UCS, greedy best-first, and A-star. Remember that A-star's time complexity depends on the quality of the heuristic: a perfect heuristic gives linear time, while a zero heuristic degrades to uniform-cost search.