Problem Solving & Search Techniques: Algorithms, Heuristics & CSPs

TAKEAWAYS:

• Search algorithms explore state spaces to find solutions, with uninformed methods (BFS/DFS) and informed methods (A*/heuristics) balancing completeness and efficiency.
• A* combines cost-to-go heuristics with path cost to optimize search, while IDDFS avoids infinite depth by iteratively deepening DFS.
• CSPs model problems as variables, domains, and constraints (e.g., Sudoku, cryptarithmetic puzzles) and use backtracking or constraint propagation.
• Heuristics (e.g., admissible, consistent) guide search but must avoid overestimating costs to ensure optimality.
• Real-world examples include Pathao’s route optimization (A*) and eSewa’s transaction validation (CSPs).
• Always analyze time/space complexity (e.g., BFS: O(b^d), A*: O(b^m)) and trade-offs between completeness, optimality, and efficiency.

1. Problem Solving in AI: State Space and Search

AI problems are often framed as search problems over a state space:

• State: A configuration of the problem (e.g., a chessboard position, a robot’s location).
• Start state: Initial configuration (e.g., "Pawn at (2,2)").
• Goal state: Desired configuration (e.g., "King at (8,8)").
• Operators: Actions that transform one state to another (e.g., "move pawn forward").
• Path: Sequence of operators from start to goal.

Example: Solving a 8-puzzle (sliding tiles to reach a goal arrangement).

State space tree for the 8-puzzle (partial):

figure:

        Start
       /   |   \
     A    B    C
    / \  / \  / \
   D  E F  G H  I

• Leaf nodes = goal states or dead ends.
• Branching factor (b): Average number of successors per state (e.g., 3 for the 8-puzzle).

2. Uninformed Search Techniques

These methods explore the state space without prior knowledge of the goal.

A. Breadth-First Search (BFS)

• Mechanism:
  • Explores all states at depth d before moving to depth d+1.
  • Uses a queue (FIFO) to track frontier states.
  • Complete: Finds a solution if one exists.
  • Optimal: Returns the shortest path (if all edges have equal cost).
  • Time: O(b^d) (exponential in depth d).
  • Space: O(b^d) (stores all nodes at depth d).

Example: Solving the 8-puzzle from start state:

Start: [1 2 3 | 4 5 6 | 7 8 _]
Goal:  [1 2 3 | 8 _ 6 | 7 4 5]

BFS trace:

1. Enqueue Start → Dequeue → Enqueue successors (A, B, C).
2. Dequeue A → Enqueue its successors (D, E, F).
3. Dequeue B → Enqueue (G, H, I).
4. Dequeue C → Goal found via path Start → C → I.

Mermaid diagram:

graph TD
    Start["[1 2 3 | 4 5 6 | 7 8 _]"] --> A["[1 2 3 | 4 5 6 | 7 _ 8]"]
    Start --> B["[1 2 3 | 4 5 _ | 7 8 6]"]
    Start --> C["[1 2 3 | 4 _ 6 | 7 8 5]"]
    C --> I["[1 2 3 | 8 _ 6 | 7 4 5]"] -->|"Goal"| Goal

B. Depth-First Search (DFS)

• Mechanism:
  • Explores as far as possible along one branch before backtracking.
  • Uses a stack (LIFO) or recursion.
  • Not complete for infinite-depth spaces (e.g., infinite grids).
  • Not optimal (may find longer paths).
  • Time/Space: O(b^m) (worst case, where m = max depth).

Example: DFS on the 8-puzzle (may miss the goal if it explores Start → A → D first).

graph TD
    Start --> A --> D
    Start --> B --> G
    Start --> C --> I -->|"Goal"| Goal

C. Depth-Limited Search (DLS)

• Fix: Limits DFS depth to d to avoid infinite loops.
• Problem: May cut off the solution if it’s deeper than d.

D. Iterative Deepening Depth-First Search (IDDFS)

• Combines DFS + BFS:
  1. Run DLS with d = 0 → 1 → 2 → ... until solution found.
  2. Complete and optimal (like BFS) but more efficient (avoids storing all nodes at depth d).
• Time: O(b^d) (same as BFS but with fewer nodes explored).

Comparison Table:

3. Informed Search Techniques

Use heuristics (cost estimates) to guide search toward the goal.

A. Heuristic Functions

• f(n) = g(n) + h(n):
  • g(n): Cost from start to node n.
  • h(n): Estimated cost from n to goal (heuristic).
• Admissible heuristic: Never overestimates true cost (e.g., Manhattan distance for grids).
• Consistent heuristic: h(n) ≤ cost(n → goal) (implies admissible).

Example: Heuristic for the 8-puzzle:

• h(n) = number of misplaced tiles (admissible but not consistent).

B. Best-First Search

• Mechanism:
  • Always expands the node with the lowest f(n).
  • Not complete unless h(n) is admissible.
  • Optimal if h(n) is admissible and consistent.

Example: Searching for the goal in the 8-puzzle with h(n) = misplaced tiles.

Start (f=0) → A (f=1) → C (f=2) → I (f=3) → Goal

C. A Search*

• Best-first search with admissible heuristics.
• Optimal and complete if h(n) is admissible and consistent.
• Pseudocode:

  function A*(start, goal):
      open_set = PriorityQueue([start], f=g(start)+h(start))
      closed_set = {}
      while open_set:
          n = open_set.pop()  # lowest f(n)
          if n == goal: return path
          for neighbor in successors(n):
              tentative_g = g(n) + cost(n → neighbor)
              if neighbor not in closed_set and tentative_g < g(neighbor):
                  g(neighbor) = tentative_g
                  f(neighbor) = g(neighbor) + h(neighbor)
                  open_set.push(neighbor)
      return failure
  

Example: A* on a grid (Manhattan distance heuristic).

Trace:

1. Start at (0,0), h = 5 (Manhattan distance to (4,4)).
2. Expand (0,1) (f = 1 + 4 = 5) → (1,1) (f = 2 + 3 = 5) → Goal at (4,4).

D. Comparison: Uninformed vs. Informed Search

4. Constraint Satisfaction Problems (CSPs)

Model problems as variables, domains, and constraints. Example: Cryptarithmetic puzzle BASE + BALL = GAMES.

A. CSP Components

• Variables: B, A, S, E, G, M, L, D, R (digits 0-9).
• Domains: Each letter ∈ {0,1,...,9}, but B,A,G,M ≠ 0.
• Constraints:
  1. Unary: B ≠ A, S ≠ E, etc.
  2. Binary: BASE + BALL = GAMES (arithmetic constraint).

B. Solving CSPs

1. Backtracking Search:
   • Assign values to variables one by one.
   • Prune branches where constraints fail.
2. Constraint Propagation:
   • Narrow domains using constraints (e.g., if B + B ends with G, G must be even).

Worked Example: Solve TWO + TWO = FOUR.

1. Variables: T, W, O, F, U, R.
2. Domains: T,F ∈ {1,...,9}, others ∈ {0,...,9}.
3. Constraints:
   • TWO + TWO = FOUR → 2×TWO = FOUR (carryover).
   • O + O must end with R (e.g., O=5 → R=0).
4. Solution: T=1, W=0, O=5, U=2, R=0, F=2 → 105 + 105 = 210.

Mermaid CSP diagram:

erDiagram
    VARIABLES ||--o{ CONSTRAINTS : "satisfies"
    VARIABLES {
        int value PK
        string name
    }
    CONSTRAINTS {
        string type PK
        string description
    }

5. Real-World Applications

In the real world

1. Pathao’s Route Optimization:

   • Uses A* with Manhattan distance to find the fastest driver route from pickup to drop-off, avoiding traffic hotspots.
   • Heuristic: Estimates travel time based on GPS data and historical traffic patterns.

2. eSewa’s Transaction Validation:

   • Models transaction rules (e.g., "balance ≥ amount") as a CSP where:
     • Variables = account balances, transaction amounts.
     • Constraints = "balance ≥ amount", "sum(transactions) = 0".
   • Solves in real-time to flag fraudulent transactions.

3. Nepal Rastra Bank’s Loan Interest Calculation:

   • Treated as a CSP where:
     • Variables = monthly payments, interest rate, loan term.
     • Constraints = "total_payments × (1 + r)^n = loan_amount".
   • Backtracking finds feasible payment plans for borrowers.

Worked Example: NTC’s Bus Route Scheduling

• Problem: Assign buses to routes to minimize delays.
• CSP Model:
  • Variables = buses, routes.
  • Domains = available time slots.
  • Constraints:
    1. Each route has exactly one bus.
    2. Bus departure times ≥ arrival times + travel time.
• Solution: Assign buses to routes using constraint propagation (e.g., Bus1 → RouteA at 8 AM).

6. Exam Tips

1. Diagrams are mandatory:

   • Always draw state space trees for BFS/DFS/A* (highlight the solution path).
   • For CSPs, show variable domains and constraints in a table.

2. Compare algorithms:

   • Use a table (like above) to contrast BFS, DFS, A*, IDDFS.
   • Highlight trade-offs (e.g., BFS is optimal but slow; A* is fast but needs a good heuristic).

3. Heuristic analysis:

   • For A*, state whether h(n) is admissible or consistent.
   • Example: Manhattan distance is admissible but not consistent for non-Euclidean grids.

4. CSPs require structure:

   • Clearly define variables, domains, and constraints.
   • Show backtracking steps (e.g., "Assign B=1 → check constraints → fail → backtrack").

5. Time/space complexity:

   • Memorize:
     • BFS: O(b^d) time/space.
     • DFS: O(b^m) (worst case).
     • A*: O(b^m) (if h is admissible).

6. Practice puzzles:

   • Solve N-Queens, 8-puzzle, and cryptarithmetic problems step-by-step.
   • For N-Queens, define:
     • Variables = queen positions.
     • Constraints = no two queens share a row/column/diagonal.

Example Answer Structure for Exams: Q: Explain A* with an example. Differentiate informed vs. uninformed search. A:

1. A Definition*: Optimal informed search using f(n) = g(n) + h(n).
2. Example: Grid search with Manhattan distance heuristic.
   • Start at (0,0), goal at (3,3).
   • Path: (0,0) → (0,1) → (0,2) → (0,3) → (1,3) → (2,3) → (3,3).
3. Comparison:

   Type	Uses Heuristic?	Optimal?	Complete?
   Uninformed	❌	❌*	✅*
   Informed	✅	✅**	✅**
   *BFS is optimal/uninformed; **if h(n) is admissible/consistent.