Search Algorithms: Trees, States, and Optimal Paths

TAKEAWAYS:

• Search spaces are modeled as trees/graphs where nodes represent states and edges represent actions; state spaces grow exponentially with problem complexity.
• Uninformed (blind) search (BFS, DFS, UCS) explores without heuristics, while informed search (Greedy, A*) uses heuristics to guide efficiency.
• Game trees alternate between player moves (minimax with alpha-beta pruning) to predict optimal strategies.
• Costs (path length, branching factor) determine algorithm choice; trade-offs exist between completeness, optimality, and time/space complexity.
• Real-world applications include pathfinding (Pathao delivery routes), game AI (chess engines), and automated planning (robotics).
• Exam focus: Trace search steps visually, compare algorithms via tables, and justify choices for given problems (e.g., "Why BFS over DFS for a maze?").

---

1. Search Problems: States, Actions, and Goals

A search problem defines how an agent solves a problem by moving through a state space:

• Initial state: Starting configuration (e.g., robot at (0,0)).
• Actions: Legal moves (e.g., UP, DOWN, LEFT, RIGHT).
• Transition model: How actions change states (e.g., UP from (0,0) → (0,1)).
• Goal test: Checks if a state is the solution (e.g., reach (3,3)).
• Path cost: Numerical value of traversing an edge (e.g., time/distance).

Visual: State Space as a Graph

Example: A robot in a grid must navigate from (0,0) to (3,2) avoiding obstacles (e.g., (2,0) is blocked). The state space above shows all possible positions.

---

2. Search Algorithms: Uninformed vs. Informed

Algorithms differ in how they explore the space. Uninformed search uses no problem-specific knowledge; informed search uses heuristics.

A. Uninformed Search

Worked Example: BFS for a Maze Problem: Find the shortest path from S to G in this grid (1 = wall, 0 = path):

S 0 0 0
0 1 0 0
0 0 0 0
0 0 0 G

Steps:

1. Start at S, explore neighbors: (1,0), (1,1) (blocked), (0,1).
2. Enqueue (1,0) and (0,1) with cost=1.
3. Dequeue (1,0), explore (2,0), (1,1) (blocked), (0,0) (visited).
4. Enqueue (2,0) with cost=2.
5. Dequeue (0,1), explore (0,2), (-1,1) (invalid), (1,1) (blocked).
6. Enqueue (0,2) with cost=2.
7. Dequeue (2,0), explore (3,0), (2,1), (1,0) (visited).
8. Enqueue (3,0) and (2,1) with cost=3.
9. Dequeue (0,2), explore (0,3), (-1,2) (invalid), (1,2).
10. Enqueue (0,3) and (1,2) with cost=3.
11. Dequeue (3,0), explore (3,1), (2,0) (visited), (4,0) (invalid).
12. Enqueue (3,1) with cost=4.
13. Dequeue (2,1), explore (2,2), (3,1), (1,1) (blocked).
14. Enqueue (2,2) and (3,1) with cost=4 (but (3,1) already in queue).
15. Dequeue (0,3), explore (0,4) (invalid), (1,3), (-1,3) (invalid).
16. Enqueue (1,3) with cost=4.
17. Dequeue (1,2), explore (1,3), (0,2) (visited), (2,2).
18. Enqueue (2,2) with cost=5.
19. Dequeue (3,1), explore (3,2), (2,1) (visited), (4,1) (invalid).
20. Enqueue (3,2) with cost=5 → Goal found!

Path: S → (1,0) → (2,0) → (3,0) → (3,1) → (3,2) = G Cost: 5 steps.

---

B. Informed Search: Heuristics Guide the Way

Heuristics (h(n)) estimate the cost from state n to the goal. Admissible heuristics never overestimate.

Worked Example: A for Pathao Delivery* Scenario: A Pathao rider at (0,0) must deliver to (4,4). Traffic costs:

• Moving horizontally/vertically: 1 unit.
• Moving diagonally: 1.414 units (Pythagorean theorem). Heuristic: Manhattan distance (h(n) = |x_G − x_n| + |y_G − y_n|). Trace:

1. Start at (0,0), g(n)=0, h(n)=8, f(n)=8.
2. Expand (1,0): g(n)=1, h(n)=7, f(n)=8 → tied with parent; keep both.
3. Expand (0,1): g(n)=1, h(n)=7, f(n)=8.
4. Expand (1,1) diagonally: g(n)=1.414, h(n)=6, f(n)=7.414 → better path.
5. Continue until (4,4) is reached via (3,3) → (4,4) with g(n)=5.656 (optimal).

Visual: A Search Tree*

---

3. Game Playing: Minimax and Alpha-Beta Pruning

Games involve adversarial search where players alternate moves. Minimax assumes opponents play optimally.

Minimax Algorithm

1. Tree structure: Alternate between maximizing player (MAX) and minimizing player (MIN).
2. Evaluation: Leaf nodes get a score (e.g., material advantage in chess).
3. Backpropagation: Propagate the best score up the tree.

Example: Tic-Tac-Toe

Trace:

1. If the current player is MAX (X), choose the move with the highest MIN value.
2. If MIN (O), choose the lowest MAX value.
3. Optimal move: The root’s best child (e.g., X wins if available).

Alpha-Beta Pruning

Reduces search by eliminating branches that cannot affect the final decision.

• Alpha: Best value MAX can guarantee so far.
• Beta: Best value MIN can guarantee so far.
• Prune if MAX ≥ Beta or MIN ≤ Alpha.

Example: Chess Endgame

---

4. Real-World Applications

A. Pathfinding in Delivery Apps (Pathao, Daraz)

• Problem: Find the shortest route avoiding traffic.
• Algorithm: A* with dynamic heuristics (real-time traffic data as edge costs).
• Example: A Daraz order in Kathmandu from Thapathali to Lakshmi Narayan might use:
  • Heuristic: Euclidean distance + traffic delays.
  • Cost: Time = distance + (traffic_weight × congestion_factor).

B. Game AI (Chess Engines, Poker Bots)

• Problem: Predict opponent moves and counter optimally.
• Algorithm: Minimax with alpha-beta pruning (e.g., Stockfish in chess).
• Example: Ncell’s poker bot uses minimax to evaluate hand strengths and bluff probabilities.

C. Robotics (Nepal’s NRC’s Autonomous Vehicles)

• Problem: Navigate unknown environments (e.g., disaster zones).
• Algorithm: DFS for exploration + A* for pathfinding.
• Example: A robot mapping a collapsed building uses:
  1. DFS to explore uncharted corridors.
  2. A* to return to base with minimal battery use.

---

5. Comparing Search Algorithms

---

6. Exam Tips

1. Trace searches step-by-step: For any algorithm, show the explored nodes, queue/stack order, and path cost.
   • Example: For BFS, list nodes in the order they’re dequeued.
2. Justify algorithm choice: Explain why BFS is better than DFS for a maze (avoids infinite loops) or why A* is better than Greedy (guarantees optimality).
3. Draw trees/graphs: Label nodes with (state, g(n), h(n), f(n)) for A* or (player, value) for minimax.
4. Calculate costs: For UCS or A*, show how g(n) accumulates (e.g., g(n) = g(parent) + edge_cost).
5. Alpha-beta pruning: Highlight pruned branches in game trees and explain why they’re cut.

---

7. Common Pitfalls

• Assuming DFS is complete: It fails in infinite spaces (e.g., cycles).
• Using non-admissible heuristics in A*: Leads to suboptimal paths.
• Ignoring edge costs: UCS and A* require summing costs; BFS assumes uniform cost.
• Misapplying minimax: Forgetting to alternate players (MAX/MIN) leads to incorrect scores.

---

8. Practice Problems

1. BFS Trace: Apply BFS to find the shortest path in this graph (edges = weights):

   A --2-- B
   | \    |
   1  3   1
   |   \  |
   C --2-- D
   

   Answer: A → C → D (cost = 3).

2. A Heuristic*: For the grid below, design an admissible heuristic to reach (4,4) from (0,0).

   0 0 1 0 0
   0 1 0 0 0
   0 0 0 1 0
   0 0 0 0 0
   

   Hint: Use Manhattan distance but account for walls.

3. Minimax Tree: Draw the minimax tree for this game and find the optimal move for MAX:

   Root (MAX)
   ├── Child1 (MIN): [Leaf1 = 3, Leaf2 = -1]
   └── Child2 (MIN): [Leaf3 = 2, Leaf4 = 4]
   

   Answer: Choose Child2 (value = 2).

---

9. Key Formulas

1. Branching Factor (b): Average number of successors per node.
2. Depth (d): Number of actions to reach the goal.
3. A Cost Function*: $f(n)=g(n)+h(n)$
   • $g(n)$: Cost from start to n.
   • $h(n)$: Heuristic estimate from n to goal.
4. Minimax Value: $\text{MAX}(\text{MIN}(v_1,v_2),\text{MIN}(v_3,v_4))$

---

10. Summary Table