Problem Solving & Searching Techniques: Algorithms, Trees & Real-World AI

TAKEAWAYS:

• State spaces model problems as graphs where nodes = states and edges = actions (e.g., Pathao’s ride states: "waiting" → "driver assigned" → "reached").
• Search algorithms (BFS/DFS/A*) trade memory/time: BFS explores all levels first (like Daraz’s order queue), DFS dives deep (like Ncell’s call routing), and A* optimizes using heuristics (like Google Maps’ shortest path).
• Game trees represent adversarial decisions (e.g., chess) with minimax and alpha-beta pruning to cut explored branches (saving 90% of calculations in tic-tac-toe).
• Constraint satisfaction solves puzzles like Sudoku or NTC’s frequency allocation by assigning values that meet all constraints (e.g., no two stations share the same frequency).
• Heuristics (e.g., Manhattan distance in the 8-puzzle) guide searches but risk local optima (e.g., hill climbing getting stuck in Kathmandu traffic jams).
• Evaluation metrics (completeness, optimality, time/space complexity) let you compare algorithms—critical for choosing between eSewa’s fast but memory-heavy BFS and a bank’s slower but optimal DFS for loan approvals.

1. Problem Solving in AI: The State Space Framework

AI problems are solved by exploring state spaces: a graph where:

• Nodes = possible states of the problem (e.g., positions of tiles in the 8-puzzle, or a user’s location in Pathao).
• Edges = actions/transitions between states (e.g., "move tile left," or "assign driver to ride").

How State Spaces Work

graph TD
    A["Initial State\n(e.g., unsorted tiles)"] -->|"Action 1"| B["State 1\n(tile moved)"]
    A -->|"Action 2"| C["State 2\n(different move)"]
    B --> D["State 3"]
    C --> D
    D --> E["Goal State\n(solved puzzle)"]

Example: The 8-puzzle (3×3 grid with 8 tiles + 1 empty space). Goal: reach the solved state from a scrambled start. Real-world tie-in:

• Pathao’s ride allocation: States = "waiting for ride" → "driver assigned" → "reached destination." Actions = "match user with driver," "update GPS."
• eSewa transactions: States = "user selects service" → "OTP sent" → "payment processed" → "service delivered."

2. Search Algorithms: How AI Finds Solutions

Search algorithms traverse the state space to find a goal state. Key types:

A. Uninformed Searches (Blind Search)

No extra info (heuristics) about the problem. Two classic approaches:

1. Breadth-First Search (BFS)
   • Explores all nodes at the present depth before moving deeper.
   • Visual trace (solving the 8-puzzle):

• Pros: Guarantees shortest path (optimal for unweighted graphs).
• Cons: High memory use (stores all nodes at current depth).
• Real-world use:
  • Daraz order processing: BFS ensures orders are fulfilled in the order they arrive (FIFO queue).
  • NTC’s frequency allocation: Explores all possible station assignments level by level to avoid conflicts.

2. Depth-First Search (DFS)
   • Explores as far as possible along a branch before backtracking.
   • Visual trace:

• Pros: Low memory (only stores current path).
• Cons: May never find the goal if the state space is infinite (e.g., recursive descent in a maze with loops).
• Real-world use:
  • Ncell’s call routing: DFS tries to connect calls through the deepest possible path first (though modern systems use BFS for reliability).

B. Informed Searches (Heuristic Search)

Uses a heuristic function (h(n)) to estimate cost from node n to the goal. Two key algorithms:

1. Greedy Best-First Search

   • Always expands the node with the lowest h(n) (most promising).
   • Heuristic for 8-puzzle: Manhattan distance (sum of horizontal/vertical distances of tiles from their goal positions).
   • Visual trace (Manhattan distance guide):

     graph TD
         A["Start\n(h=5)"] --> B["Node 1\n(h=3)"]
         A --> C["Node 2\n(h=1)"]
         C --> D["Goal\n(h=0)"]

   • Pros: Fast, often finds solutions quickly.
   • Cons: Not optimal (may miss shorter paths if heuristic is misleading).

2. A Search (A-Star)*

   • Combines cost so far (g(n)) + heuristic (h(n)) → f(n) = g(n) + h(n).
   • Example: Solving the 8-puzzle with A*:
     • Start: g(n)=0, h(n)=5 (Manhattan distance) → f(n)=5.
     • Expand node with lowest f(n).
   • Visual trace:

     graph TD
         A["Start\n(f=5)"] --> B["Node 1\n(f=4)"]
         A --> C["Node 2\n(f=2)"]
         C --> D["Goal\n(f=0)"]

   • Pros: Optimal if heuristic is admissible (never overestimates) and consistent (satisfies triangle inequality).
   • Cons: Computationally expensive if h(n) is complex.
   • Real-world use:
     • Google Maps: Uses A* with heuristics like "traffic data" + "distance" to find the fastest route.
     • Khalti’s fraud detection: A* explores transaction paths (e.g., "user → merchant → bank") with h(n) = "risk score."

C. Depth-Limited Search (DLS)

• Fixes DFS’s infinite-loop problem by setting a depth limit.
• If the goal isn’t found within the limit, it backtracks.
• Real-world use:
  • Bank loan approvals: DFS explores "customer → credit score → collateral" but limits depth to avoid infinite loops (e.g., recursive checks on joint applicants).

D. Iterative Deepening Depth-First Search (IDDFS)

• Repeatedly runs DFS with increasing depth limits.
• Pros: Combines DFS’s efficiency with BFS’s optimality.
• Real-world use:
  • NEPSE stock analysis: Explores possible price movements iteratively to predict trends without exhaustive computation.

3. Game Trees and Adversarial Search

Games (e.g., chess, tic-tac-toe) involve two players (maximizer/minimizer). AI uses:

• Minimax: Assumes the opponent plays optimally.
  • Example: Tic-tac-toe game tree (simplified):

• Problem: Explodes exponentially (chess has ~10¹²⁰ possible games).
• Alpha-Beta Pruning: Cuts off branches that won’t affect the final decision.
  • Saves ~90% of calculations in tic-tac-toe.
  • Real-world use:
    • Pathao’s fare negotiation: Uses minimax to predict driver acceptance of fares (maximizer = Pathao, minimizer = driver).

4. Constraint Satisfaction Problems (CSP)

Problems where variables must satisfy a set of constraints (e.g., Sudoku, NTC’s frequency allocation). Key terms:

• Variables: Unknowns to assign (e.g., tile positions, station frequencies).
• Domains: Possible values for variables (e.g., digits 1–9 for Sudoku).
• Constraints: Restrictions (e.g., "no duplicate frequencies in NTC’s 100MHz–108MHz band").

Example: NTC’s frequency allocation CSP

• Variables: 5 stations (S1–S5).
• Domains: Frequencies 100–108 MHz (9 options).
• Constraints:
  • No two stations share the same frequency.
  • Stations within 50 km must be ≥1 MHz apart.
• Solution: Backtracking search assigns frequencies while checking constraints.

Visual trace (backtracking):

graph TD
    A["Assign S1=100MHz"] --> B["Check constraints"]
    B -->|"Valid"| C["Assign S2=101MHz"]
    C --> D["Check constraints"]
    D -->|"Conflict"| E["Backtrack\nTry S2=102MHz"]
    E --> F["Success"]

5. Evaluating Search Algorithms

Real-world trade-offs:

• eSewa: Uses BFS for transaction queues (optimal for FIFO) but may run out of memory during peak hours.
• Google Maps: Uses A* (optimal) but with a simplified heuristic to balance speed and accuracy.

6. Hill Climbing and Local Optima

• Idea: Move to the "best" neighboring state iteratively.
• Example: 8-puzzle hill climbing with Manhattan distance heuristic.
  • Trace:

• Problem: Local optima (e.g., getting stuck in Kathmandu traffic jams).
• Solutions:
  • Stochastic hill climbing: Randomly perturb moves to escape optima.
  • Simulated annealing: Gradually reduces "temperature" (randomness) over time.

Real-world use:

• Khalti’s fraud detection: Hill climbing adjusts risk scores iteratively, but may get stuck on false positives.

7. Real-World Applications

A. eSewa’s Transaction Routing

• Problem: Route transactions through servers with minimal delay.
• Algorithm: BFS (FIFO queue) ensures fairness and avoids infinite loops.
• Why not DFS?: DFS might get stuck in recursive validation loops (e.g., "user → bank → merchant → user").

B. Pathao’s Ride Optimization

• Problem: Match users to drivers with minimal wait time.
• Algorithm: A* with heuristics:
  • g(n) = time taken so far.
  • h(n) = estimated time to destination (using traffic data).
• Result: Faster matches than greedy (which might ignore traffic).

C. NTC’s Frequency Allocation

• Problem: Assign frequencies to 50+ stations without interference.
• Algorithm: Backtracking CSP solver.
• Constraint: Stations within 50 km must differ by ≥1 MHz.
• Visual:

  graph TD
      A["Assign S1=100MHz"] --> B["Check S2\n(50km away)"]
      B -->|"Conflict"| C["Backtrack\nTry S2=101MHz"]
      C --> D["Success"]

D. Google Maps’ Route Planning

• Problem: Find the fastest route from A to B.
• Algorithm: A* with:
  • g(n) = distance traveled.
  • h(n) = straight-line distance to goal (Euclidean heuristic).
• Optimization: Precomputes heuristics for common routes.

8. Worked Example: Solving the 8-Puzzle with A*

Initial state:

1 2 3
4 0 5
6 7 8

Goal state:

1 2 3
4 5 6
7 8 0

Steps:

1. Heuristic: Manhattan distance (sum of tile displacements).
   • For the initial state: h(initial) = 4 (tile 1) + 2 (tile 2) + 2 (tile 3) + 2 (tile 4) + 0 (tile 5) + 2 (tile 6) + 2 (tile 7) + 2 (tile 8) = 16.
2. A expansion*:
   • Move tile 5 left (swap with 0):

     1 2 3
     4 5 0
     6 7 8
     

     h(new) = 4 + 2 + 2 + 2 + 0 + 2 + 2 + 1 = 15 → f(n) = g(n)=1 + h(n)=15 = 16.
   • Continue until h(n) = 0 (goal reached).

Trace:

Exam Tip

1. Definitions:

   • State space: Graph of problem states/actions. Always draw a small example (e.g., 8-puzzle or Pathao ride states).
   • Heuristic: A function to estimate cost (e.g., Manhattan distance). Admissible = never overestimates; consistent = satisfies triangle inequality.

2. Algorithms:

   • Compare BFS vs. DFS vs. A* in a table (completeness, optimality, time/space).
   • AO* (Admissible Ordering A*): Used in matrix multiplication to avoid redundant calculations. Example: For 3 matrices A, B, C, compute (AB)C vs. A(BC) and choose the cheaper path.

3. Game Trees:

   • Minimax: Assume opponent plays optimally. Draw a tic-tac-toe tree and prune with alpha-beta.
   • Alpha-beta pruning: Cuts branches that won’t affect the final decision. Saves 90% of calculations in symmetric games.

4. CSPs:

   • Backtracking: Assign values while checking constraints. Example: NTC frequency allocation.
   • Arc consistency: Reduce domains by eliminating values that violate constraints.

5. Hill Climbing:

   • Limitations: Gets stuck in local optima (e.g., Kathmandu traffic jams).
   • Solutions: Stochastic hill climbing or simulated annealing.

6. Real-world ties:

   • eSewa: BFS for transactions.
   • Pathao: A* for ride matching.
   • NTC: CSP for frequency allocation.
   • Google Maps: A* with traffic heuristics.

7. Common exam questions:

   • Solve the 8-puzzle using hill climbing/A* (show steps with h(n)).
   • Draw a game tree for tic-tac-toe and apply minimax/alpha-beta.
   • Compare greedy best-first and A* search.
   • Explain how DFS leads to infinite loops and how DLS/IDDFS fix it.