AI Search Algorithms
Understanding How AI Finds
Solutions
[Your Name] | [Date] | [Institution]
Introduction to Search in AI
• Search is fundamental to problem-solving in
AI.
• Many AI problems can be modeled as search
problems.
• Examples: Finding a route on a map, Solving
puzzles, Game playing
Components of a Search Problem
• Initial State
• Goal State
• State Space
• Successor Function
• Path Cost
Types of Search Algorithms
• Uninformed (Blind) Search - No domain-
specific knowledge
• Informed (Heuristic) Search - Uses domain
knowledge to guide the search
Breadth-First Search (BFS)
• Explores neighbors first before going deeper
• Uses a queue (FIFO)
• Completeness: Yes
• Optimality: Yes (if cost = 1)
• Time/Space: O(b^d)
Depth-First Search (DFS)
• Explores as far as possible down one branch
• Uses a stack (LIFO)
• Completeness: No
• Optimality: No
• Time: O(b^m)
• Space: O(bm)
Uniform Cost Search (UCS)
• Expands the node with the lowest path cost
• Uses a priority queue
• Completeness & Optimality: Yes
• Time/Space: O(b^C*/ε)
Comparison Table (Uninformed)
• BFS - Complete: Yes, Optimal: Yes, Time:
O(b^d), Space: O(b^d)
• DFS - Complete: No, Optimal: No, Time:
O(b^m), Space: O(bm)
• UCS - Complete: Yes, Optimal: Yes,
Time/Space: O(b^C*/ε)
Heuristic Search
• Heuristic: estimate of cost from current state
to goal
• Improves efficiency over uninformed methods
Best-First Search
• Selects node with lowest heuristic value h(n)
• Greedy strategy: picks seemingly best path
• Not always optimal
A* Search
• Combines path cost and heuristic: f(n) = g(n) +
h(n)
• Optimal if h(n) is admissible (never
overestimates)
• Widely used in GPS, robotics, games
Example – A* vs. Greedy Search
• Diagram showing pathfinding on a graph
• Highlight different choices made by each
Heuristics
• Admissible: Never overestimates
• Consistent: h(n) ≤ c(n, n') + h(n')
• Good heuristics reduce search time
dramatically
Summary
• Search is key to AI problem-solving
• Choose the right algorithm based on:
• Problem size and structure, Time and space
constraints, Availability of heuristics
Questions / Discussion
Search Problem Example: 8-Puzzle
• Initial State: Random arrangement of tiles
• Goal State: Tiles ordered from 1 to 8, blank at
the end
• State Space: All possible tile configurations (9!
states)
• Successor Function: Move blank tile
up/down/left/right
• Path Cost: Number of moves
BFS Example: 8-Puzzle
• Explores all nodes level by level
• Finds shortest path but uses a lot of memory
• Not practical for deep puzzles (memory
explosion)
DFS Example: 8-Puzzle
• Follows one path deep before backtracking
• Memory efficient but may get stuck in loops
• Not guaranteed to find shortest solution
UCS Example: Route Finding
• Start: Arad, Goal: Bucharest
• Path cost = distance
• UCS expands cities based on total path cost
• Guaranteed to find shortest path
A* Example: Route Finding
• Start: Arad, Goal: Bucharest
• f(n) = g(n) + h(n) where h(n) = straight-line
distance to Bucharest
• A* finds optimal path efficiently if h(n) is
admissible
Heuristic Example: 8-Puzzle
• h1: Number of misplaced tiles
• h2: Sum of Manhattan distances (more
accurate)
• A* with h2 generally performs better than
with h1
