Problem Solving by Searching: Algorithms, Trees & Real-World Applications

TAKEAWAYS:

• Search algorithms (BFS, DFS, UCS) explore state spaces systematically to find solutions, each with trade-offs in memory, speed, and completeness.
• State spaces model problems as graphs where nodes = states and edges = actions; search algorithms traverse these to reach goals (e.g., Pathao’s delivery routes).
• Game trees represent adversarial decisions (like chess) with minimax and alpha-beta pruning to optimize moves—used in AI opponents in mobile games.
• Heuristics (e.g., A*, greedy) guide search by estimating cost; A* combines path cost + heuristic for efficiency (e.g., Google Maps’ route planning).
• Optimality depends on the algorithm: UCS guarantees the cheapest path, while greedy may fail if the heuristic is misleading.
• Real-world impact: Search algorithms power logistics (Daraz deliveries), fraud detection (bank transaction paths), and even NTC’s network routing.

1. Problem Solving by Searching: Core Concepts

Searching is the process of exploring possible states (solutions) of a problem to find a goal. It’s foundational in AI for tasks like:

• Pathfinding (e.g., shortest route in Pathao’s delivery system).
• Game playing (e.g., AI opponents in mobile games).
• Automated planning (e.g., robot navigation in warehouses).

Key Definitions

• State space: A graph where each node = a problem state, and edges = possible actions/transitions. Example: A robot in a grid world (nodes = grid cells, edges = moves up/down/left/right).
• Initial state: Starting point (e.g., robot at (0,0)).
• Goal state: Desired outcome (e.g., robot at (4,4)).
• Operators: Actions that transform one state to another (e.g., "move right").
• Path cost: Sum of costs of actions in a path (e.g., time/distance).

2. Search Algorithms: How They Work

Algorithms differ in how they explore the state space. Below are the four core algorithms from the syllabus, with visual traces and comparisons.

A. Breadth-First Search (BFS)

• How it works: Explores all nodes at the present depth before moving deeper (uses a queue).
• Properties:
  • Complete: Finds a solution if one exists.
  • Optimal: Finds the shortest path in an unweighted graph.
  • Memory-intensive: Stores all nodes at the current depth.
• When to use: Unweighted graphs (e.g., shortest path in a grid with equal-cost moves).

graph TD
    A["Start (0,0)"] --> B["(0,1)"]
    A --> C["(1,0)"]
    B --> D["(0,2)"]
    B --> E["(1,1)"]
    C --> F["(1,1)"]
    C --> G["(2,0)"]
    E --> H["Goal (1,2)"]

Trace: BFS explores (0,0) → (0,1), (1,0) → (0,2), (1,1), (2,0) → (1,2) [Goal].

B. Depth-First Search (DFS)

• How it works: Explores as far as possible along a branch before backtracking (uses a stack).
• Properties:
  • Complete: Only if the branching factor is finite and no cycles (e.g., in trees).
  • Not optimal: May find a long path before a shorter one.
  • Memory-efficient: Stores only one path at a time.
• When to use: Deep but narrow state spaces (e.g., maze solving).

graph TD
    A["Start (0,0)"] --> B["(0,1)"]
    B --> D["(0,2)"]
    D --> E["(0,3)"]
    E --> F["(0,4)"]
    F --> G["Goal (0,5)"]
    A --> C["(1,0)"]

Trace: DFS goes (0,0) → (0,1) → (0,2) → (0,3) → (0,4) → (0,5) [Goal], ignoring other branches until backtracking.

C. Uniform Cost Search (UCS)

• How it works: Like BFS but prioritizes paths with the lowest total cost (uses a priority queue).
• Properties:
  • Complete and optimal: Guarantees the cheapest path in weighted graphs.
  • Slower than BFS: Expands more nodes if costs vary.
• When to use: Weighted graphs (e.g., NTC’s network routing with varying link costs).

graph TD
    A["Start (0,0)"] -->|"cost=1"| B["(0,1)"]
    A -->|"cost=2"| C["(1,0)"]
    B -->|"cost=1"| D["(0,2)"]
    B -->|"cost=3"| E["(1,1)"]
    C -->|"cost=1"| F["(1,1)"]
    E -->|"cost=1"| G["Goal (1,2)"]

Trace: UCS picks the cheapest path: (0,0) → (0,1) [cost=1] → (1,1) [cost=3] → (1,2) [cost=4].

D. Comparison Table

*Only for unweighted graphs. **Only if no cycles and finite branches.

3. State Spaces and Problem Representation

A state space is a graph where:

• Nodes = states of the problem.
• Edges = legal actions/transitions.
• Start node = initial state.
• Goal node(s) = solution(s).

Example: The 8-Puzzle (Sliding Tiles)

• States: Arrangements of 8 tiles + 1 empty space.
• Actions: Slide a tile into the empty space (up/down/left/right).
• Goal: Solve the puzzle (e.g., tiles in order 1-8).

graph TD
    A["Initial\n1 2 3\n4 5 6\n7 8 _"] --> B["Move 8 down\n1 2 3\n4 5 6\n7 _ 8"]
    B --> C["Move 6 left\n1 2 3\n4 5 _\n7 8 6"]
    C --> D["Move 5 down\n1 2 3\n4 _ 5\n7 8 6"]
    D --> E["Move 4 right\n1 2 3\n_ 4 5\n7 8 6"]
    E --> F["Move 1 down\n_ 2 3\n1 4 5\n7 8 6"]
    F --> G["Move 2 left\n1 _ 3\n2 4 5\n7 8 6"]
    G --> H["Move 3 up\n1 2 _\n3 4 5\n7 8 6"]
    H --> I["Move 7 right\n1 2 3\n4 5 6\n_ 8 7"]
    I --> J["Move 8 up\n1 2 3\n4 5 6\n8 _ 7"]
    J --> K["Move 7 left\n1 2 3\n4 5 6\n_ 7 8"]
    K --> L["Goal\n1 2 3\n4 5 6\n7 8 _"]

Key Idea: Each node represents a unique board configuration. Search algorithms explore these to reach the goal.

4. Game Trees and Adversarial Search

Games like chess or tic-tac-toe involve two players (maximizer/minimizer). A game tree models possible moves and outcomes.

Minimax Algorithm

• How it works:
  1. Maximizer (e.g., AI) tries to maximize score.
  2. Minimizer (e.g., opponent) tries to minimize score.
  3. Recursively evaluate all possible moves to depth d.
• Assumption: Players play optimally.

graph TD
    A["Root (AI)"] --> B["Move 1\nScore=?"]
    B --> C["Opponent\nScore=3"]
    B --> D["Opponent\nScore=1"]
    C --> E["AI\nScore=5"]
    C --> F["AI\nScore=2"]
    D --> G["AI\nScore=4"]
    D --> H["AI\nScore=0"]

Trace:

• AI evaluates all paths:
  • Path 1: AI → Opponent → AI (scores 5 or 2) → minimizer picks 2.
  • Path 2: AI → Opponent → AI (scores 4 or 0) → minimizer picks 0.
• AI picks the maximum of minimums: max(2, 0) = 2.

Alpha-Beta Pruning

• Optimization: Eliminates branches that cannot affect the final decision.
• How it works:
  • Alpha: Best value found so far for the maximizer.
  • Beta: Best value found so far for the minimizer.
  • Prune if a move’s value ≤ alpha (maximizer) or ≥ beta (minimizer).

graph TD
    A["Root (AI)"] --> B["Move 1\nAlpha=-∞"]
    B --> C["Opponent\nBeta=∞"]
    C --> D["AI\nScore=5\nAlpha=5"]
    C --> E["AI\nScore=2"]
    B --> F["Opponent\nBeta=2"]
    F --> G["AI\nScore=4"]
    F --> H["AI\nScore=0"]

Trace:

• After evaluating Move 1 → Opponent → AI (5), alpha = 5.
• For Move 1 → Opponent → AI (2), since 2 ≤ alpha (5), prune the rest of Move 1’s subtree.

5. Heuristic Search: A and Greedy*

When the state space is large, heuristic functions guide the search toward the goal.

Greedy Best-First Search

• How it works: Expands the node with the lowest heuristic estimate to the goal.
• Heuristic (h(n)): Estimated cost from node n to the goal.
• Problem: May not find the optimal path if the heuristic is misleading.

A Search*

• How it works: Combines path cost (g(n)) + heuristic (h(n)) to prioritize nodes: f(n) = g(n) + h(n).
• Admissible heuristic: Never overestimates the true cost (e.g., Manhattan distance in grids).
• Optimal: If h(n) is admissible, A* finds the optimal path.

graph TD
    A["Start\nf(n)=0+4=4"] --> B["Node 1\nf(n)=2+3=5"]
    A --> C["Node 2\nf(n)=1+5=6"]
    B --> D["Node 3\nf(n)=4+1=5"]
    B --> E["Node 4\nf(n)=3+2=5"]
    C --> F["Node 5\nf(n)=3+2=5"]
    D --> G["Goal\nf(n)=5+0=5"]

Trace:

• A* expands nodes in order of f(n): Start (4) → Node 1 (5) → Node 2 (6) → Node 3 (5) → Goal.

Heuristic Examples

*Not admissible but often used for speed.

6. Real-World Applications

A. Pathao’s Delivery Route Optimization

• Problem: Find the shortest path for a delivery rider from pickup to drop-off.
• Algorithm: A* with heuristic = straight-line distance to the goal.
• Why A*:
  • Combines actual road distance (g(n)) + heuristic (h(n)) for efficiency.
  • Avoids exploring irrelevant paths (e.g., detours).

B. Ncell’s Network Routing

• Problem: Route data packets through the network with minimal delay.
• Algorithm: Uniform Cost Search (UCS) or Dijkstra’s (a variant of UCS).
• Why UCS:
  • Models network links as edges with cost = latency.
  • Finds the lowest-latency path between nodes.

C. Daraz’s Warehouse Robotics

• Problem: Navigate a robot through aisles to pick items.
• Algorithm: BFS (if all moves have equal cost) or A* (if some paths are longer).
• Why BFS/A*:
  • BFS guarantees the shortest path in unweighted grids.
  • A* optimizes for real-world constraints (e.g., wider aisles = lower cost).

D. NTC’s Internet Traffic Routing

• Problem: Direct traffic through the least congested paths.
• Algorithm: Minimax with alpha-beta pruning (for dynamic rerouting).
• Why Minimax:
  • Models "maximizer" = traffic load, "minimizer" = NTC’s goal to minimize delays.
  • Pruning avoids recalculating irrelevant paths.

7. Worked Example: Ncell’s Call Routing

Scenario: A call from Kathmandu to Pokhara must traverse 3 towers with the following costs:

• Tower A → Tower B: Cost 2
• Tower A → Tower C: Cost 3
• Tower B → Tower D: Cost 1
• Tower C → Tower D: Cost 2

Goal: Find the cheapest path from A to D.

Step-by-Step UCS Trace

1. Start at A, explore neighbors:
   • A → B (cost=2)
   • A → C (cost=3)
2. Expand B:
   • B → D (cost=2 + 1 = 3)
3. Expand C:
   • C → D (cost=3 + 2 = 5)
4. Compare paths:
   • A → B → D: Total cost = 3
   • A → C → D: Total cost = 5
5. Optimal path: A → B → D (cost=3).

graph TD
    A["A"] -->|"2"| B["B"]
    A -->|"3"| C["C"]
    B -->|"1"| D["D\nGoal"]
    C -->|"2"| D

8. Exam Tip

How This Unit is Tested:

1. Definitions: Know the difference between BFS, DFS, UCS, A*, and minimax. For example:
   • "Why is BFS not optimal for weighted graphs?" → Answer: It doesn’t consider edge costs; UCS does.
2. Traces: Draw and explain a 3-step trace for BFS/DFS/UCS/A* on a given state space.
   • Example: Given a grid, show how BFS explores nodes level by level.
3. Heuristics: Calculate f(n) = g(n) + h(n) for A* and identify admissible heuristics.
   • Example: For the 8-puzzle, the Manhattan distance is admissible because it never overestimates.
4. Real-world mapping: Link algorithms to scenarios like:
   • "How would Pathao use A to optimize delivery routes?"* → Answer: Heuristic = straight-line distance; g(n) = actual road distance.
5. Game trees: Construct a minimax tree for a simple game (e.g., tic-tac-toe) and prune using alpha-beta.
6. Shortcomings: Discuss why greedy search fails in some cases (e.g., if the heuristic is not monotonic).

Common Pitfalls:

• Confusing completeness (guarantees finding a solution) with optimality (guarantees the best solution).
• Forgetting that DFS is not complete in graphs with cycles.
• Misapplying heuristics (e.g., using a non-admissible heuristic in A* and getting a suboptimal path).

Marks Boosters:

• Draw state space diagrams for problems like the 8-puzzle or grid navigation.
• Compare algorithms in a table (as shown above) for questions asking about trade-offs.
• Relate to Nepali examples: NTC routing, Pathao deliveries, or even Kathmandu traffic (as a state space with congestion costs).