AI Search: BFS, DFS & A*
AI · Intermediate
Definition
AI search explores a state space to reach a goal. A* combines path cost g(n) with a heuristic h(n).
Used in games, route planning, robotics and puzzles.
Diagram
Flowchart
Example: Manhattan heuristic
h = lambda a, b: abs(a[0]-b[0]) + abs(a[1]-b[1])
print(h((0,0), (3,4)))Output: 7
Key points
- Admissible heuristics keep A* optimal
- BFS optimal for equal costs
- Greedy best-first is fast but not optimal
Interview questions
What is an admissible heuristic?
One that never overestimates the true cost to the goal.