Search is the process of finding a sequence of actions that leads from an initial state to a goal state. It is fundamental to AI problem solving.
| Component | Description | Example (Romania Map) |
|---|---|---|
| Initial State | Starting point | Arad |
| Actions | Possible moves from a state | Go to Zerind, Sibiu, Timisoara |
| Transition Model | Result of an action | Go(Arad, Zerind) → Zerind |
| Goal Test | Is this the goal? | At Bucharest? |
| Path Cost | Cost of reaching state | Distance in km |
A sequence of actions leading from initial state to goal state. An optimal solution has the lowest path cost.
Uninformed (blind) search has no additional information beyond the problem definition. It does not know whether one non-goal state is “better” than another.
Expands the shallowest unexpanded node first.
1. Initialize queue with initial state
2. Loop:
a. If queue is empty → return FAILURE
b. Pop node from front of queue
c. If node is GOAL → return solution
d. Expand node, add children to BACK of queue
Initial: A
Goal: G
Tree:
A
/ \
B C
/ \ / \
D E F G
BFS Order: A → B → C → D → E → F → G ✓
| Property | Value |
|---|---|
| Complete? | Yes (if branching factor b is finite) |
| Optimal? | Yes (if path cost = 1 per step) |
| Time Complexity | O(b^d) |
| Space Complexity | O(b^d) — keeps all nodes in memory |
Limitation: Memory intensive — stores all nodes at current depth.
Expands the node with the lowest path cost g(n). Generalizes BFS for varying step costs.
1. Initialize priority queue with initial state (cost=0)
2. Loop:
a. If queue is empty → return FAILURE
b. Pop node with LOWEST cost
c. If node is GOAL → return solution
d. Expand node, add children to priority queue with updated cost
A --1-- B --2-- D
| |
4 1
| |
C ------3------ G
UCS: A(0) → B(1) → C(4) → D(3) → G(4) ✓
Path: A → B → D → G, Cost = 4
| Property | Value |
|---|---|
| Complete? | Yes (if step costs ≥ ε > 0) |
| Optimal? | Yes |
| Time Complexity | O(b^(1+C*/ε)) |
| Space Complexity | O(b^(1+C*/ε)) |
Expands the deepest unexpanded node first.
1. Initialize stack with initial state
2. Loop:
a. If stack is empty → return FAILURE
b. Pop node from TOP of stack
c. If node is GOAL → return solution
d. Expand node, add children to TOP of stack
Tree:
A
/ \
B C
/ \ / \
D E F G
DFS Order: A → B → D → E → C → F → G ✓
| Property | Value |
|---|---|
| Complete? | No (fails in infinite spaces) |
| Optimal? | No |
| Time Complexity | O(b^m) where m = max depth |
| Space Complexity | O(bm) — linear space! |
Advantage: Much less memory than BFS.
| Criterion | BFS | UCS | DFS |
|---|---|---|---|
| Complete | Yes | Yes | No |
| Optimal | Yes* | Yes | No |
| Time | O(b^d) | O(b^C*/ε) | O(b^m) |
| Space | O(b^d) | O(b^C*/ε) | O(bm) |
| Best for | Shallow goals | Varying costs | Memory constraint |
*BFS optimal only when all step costs are equal.
DFS with a depth limit l — prevents infinite loops.
DFS-Limited(problem, limit):
return Recursive-DLS(initial_state, limit)
Recursive-DLS(node, limit):
if GOAL-TEST(node) → return solution
if limit = 0 → return cutoff
for each action in ACTIONS(node):
child = RESULT(node, action)
result = Recursive-DLS(child, limit-1)
if result ≠ cutoff → return result
return cutoff
Combines advantages of BFS and DFS:
| Property | Value |
|---|---|
| Complete | Yes |
| Optimal | Yes (uniform step cost) |
| Time | O(b^d) |
| Space | O(bd) |
Short Answer (2 marks each)
Long Answer (8 marks each)
Think & Apply
S
/ | \
A B C
/\ |
D E F
|
G (goal)