Search Algorithms in AI - Types of Search Algorithms in AI & Techniques
What are Search Algorithms in AI?
Search algorithms help AI systems explore possible states to find a path from an initial state to a goal state — fundamental to problem-solving agents.
Uninformed Search Techniques
- Breadth-First Search (BFS): Explores all nodes at the current depth before moving deeper.
- Depth-First Search (DFS): Explores as far as possible along a branch before backtracking.
- Uniform Cost Search: Expands the node with the lowest path cost.
Informed (Heuristic) Search Techniques
- Greedy Best-First Search: Chooses the node closest to the goal based on a heuristic.
- A* Search: Combines path cost and heuristic estimate for optimal, efficient search.
Local Search Algorithms
- Hill Climbing: Continuously moves toward increasing value.
- Simulated Annealing: Allows occasional worse moves to avoid local optima.
Applications
Search algorithms power route planning (like GPS navigation), puzzle solvers, and game-playing AI such as chess engines.
How the Main Algorithms Compare
Choosing a search algorithm usually comes down to four questions: will it find a solution if one exists (complete), will it find the best one (optimal), how long does it take, and how much memory does it need. Here, b is the branching factor and d is the depth of the shallowest solution.
| Algorithm | Complete? | Optimal? | Memory behaviour |
|---|---|---|---|
| BFS | Yes, if b is finite | Yes, when every step costs the same | High: stores a whole level, roughly O(b^d) |
| DFS | Not in infinite or cyclic spaces without checks | No | Low: only the current path |
| Uniform Cost | Yes, with positive step costs | Yes | High, similar to BFS |
| Greedy Best-First | No | No | Can be high |
| A* | Yes | Yes, with an admissible heuristic | High: keeps the frontier in memory |
Iterative deepening DFS is a useful middle option: it repeats depth-limited DFS with increasing limits, giving BFS-like completeness with DFS-like memory use.
Inside A*: f(n) = g(n) + h(n)
A* ranks each node by g(n), the cost already paid to reach it, plus h(n), a guess of the remaining cost. It always expands the node with the lowest total. If h(n) never overestimates the true remaining cost, the heuristic is called admissible and A* is guaranteed to return an optimal path.
On a grid where you can move up, down, left or right, Manhattan distance (the sum of horizontal and vertical gaps to the goal) is admissible because no path can be shorter than it. Straight-line distance is admissible when diagonal moves are allowed too.
import heapq
def a_star(grid, start, goal):
def h(p):
return abs(p[0] - goal[0]) + abs(p[1] - goal[1])
frontier = [(h(start), 0, start)]
best_g = {start: 0}
while frontier:
f, g, node = heapq.heappop(frontier)
if node == goal:
return g
r, c = node
for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):
if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] == 0:
ng = g + 1
if ng < best_g.get((nr, nc), float("inf")):
best_g[(nr, nc)] = ng
heapq.heappush(frontier, (ng + h((nr, nc)), ng, (nr, nc)))
return None # goal unreachable
Cells with 0 are open and 1 are walls. Setting h to zero turns this into uniform cost search, which shows how closely the two are related.
Picking an Algorithm for a Problem
- All steps cost the same and the space is small: BFS is simple and finds the shortest path.
- Steps have different costs, no good estimate available: uniform cost search, which is essentially Dijkstra's algorithm.
- You can estimate distance to the goal: A* usually explores far fewer nodes.
- Memory is tight and any solution will do: DFS or iterative deepening.
- Optimisation with no clear goal state, such as scheduling: local search like hill climbing or simulated annealing.
Errors That Cost Correctness
- Using a heuristic that overestimates, which makes A* faster but can return a longer path.
- Forgetting a visited set in graph search, so the algorithm loops around cycles.
- Stopping when the goal is first added to the frontier rather than when it is removed; with uneven costs this can miss a cheaper route.
Ready to master Artificial Intelligence?
Build real-world AI skills with hands-on projects and mentor-guided training.