Problem Solving & Search Techniques: Algorithms, Heuristics & State Spaces

Core Concepts

What is a Problem in AI?

A problem in AI is defined by:

• Initial state: Starting configuration (e.g., scrambled blocks in a puzzle).
• Goal state: Desired configuration (e.g., solved puzzle).
• Actions: Legal moves (e.g., sliding blocks).
• State space: All possible states reachable from the initial state.
• Path cost: Cost of moving from one state to another (e.g., time or steps).

Example: Solving the 8-puzzle (3×3 grid with 8 tiles and 1 empty space).

State Space Representation

A state space graph is a directed graph where:

• Nodes = states.
• Edges = actions (with associated costs).
• Goal = a node marked as terminal.

graph TD
    A["Initial State"] --> B["State 1"]
    A --> C["State 2"]
    B --> D["State 3"]
    C --> D
    D --> E["Goal State"]

Key Properties:

• Branching factor (b): Average number of successors per state.
• Depth (d): Length of the shortest path from initial to goal.
• Solution cost (c): Sum of edge costs along the path.

Uninformed Search Algorithms

These algorithms ignore problem-specific knowledge and explore the state space blindly.

1. Breadth-First Search (BFS)

• How it works: Explores all nodes at the present depth before moving deeper.
• Data structure: Queue (FIFO).
• Completeness: Yes (if branching factor is finite and step costs are positive).
• Optimality: Yes (finds the least-cost path if all edge costs are equal).
• Time complexity: $O(b^d)$ (exponential in depth).

Worked Example: Find the shortest path in a traffic grid (e.g., Kathmandu’s Thapathali to Koteshwor). Assume:

• Grid size: 3×3.
• Start at (0,0), Goal at (2,2).
• Cost to move right/down = 1.

BFS Expansion Order:

1. (0,0) → (0,1), (1,0)
2. (0,1) → (0,2), (1,1)
3. (1,0) → (1,1)
4. (1,1) → (1,2), (2,1)
5. (1,2) → (2,2) Goal found!

Path: (0,0) → (1,0) → (1,1) → (1,2) → (2,2) (Cost = 4).

2. Depth-First Search (DFS)

• How it works: Explores as far as possible along each branch before backtracking.
• Data structure: Stack (LIFO).
• Completeness: No (may loop infinitely in infinite state spaces).
• Optimality: No (may find a long path before a shorter one).
• Time complexity: $O(b^m)$ (m = maximum depth).

Worked Example: Same grid as above. DFS Expansion Order:

1. (0,0) → (0,1) → (0,2) → Dead end.
2. Backtrack to (0,1) → (1,1) → (1,2) → (2,2) Goal found!

Path: (0,0) → (0,1) → (1,1) → (1,2) → (2,2) (Cost = 4).

3. Uniform Cost Search (UCS)

• How it works: Expands the least-cost node first (priority queue).
• Completeness: Yes (if edge costs ≥ ε > 0).
• Optimality: Yes (finds the least-cost path).
• Time complexity: $O(b^{1+\lfloor c\ast /ϵ\rfloor })$ (c* = optimal cost).

Worked Example: Modified grid with unequal costs.

• Costs: Right = 2, Down = 1.

UCS Expansion:

1. (0,0) → (1,0) [Cost = 1] (cheaper than (0,1)).
2. (1,0) → (1,1) [Cost = 2].
3. (1,1) → (2,1) [Cost = 3] or (1,2) [Cost = 4].
4. (2,1) → (2,2) Goal found! [Total cost = 4].

Optimal Path: (0,0) → (1,0) → (1,1) → (2,1) → (2,2).

4. Depth-Limited Search (DLS) and Iterative Deepening (IDDFS)

• DLS: DFS with a depth limit to avoid infinite loops.
  • Problem: May miss shallow solutions if the limit is too low.
• IDDFS: Repeatedly runs DLS with increasing depth limits.
  • Advantages:
    • Completeness: Yes.
    • Optimality: Yes (if step costs are equal).
    • Time complexity: $O(b^d)$ (same as BFS, but with lower memory).

Worked Example: IDDFS for the 8-puzzle (depth limit starts at 0).

1. Depth 0: Only initial state → No goal.
2. Depth 1: Explore all neighbors → No goal.
3. Depth 2: Explore grandchildren → Find goal at depth 3.

Informed Search Algorithms

These use heuristics (problem-specific knowledge) to guide the search.

Heuristics

A heuristic function $h(n)$ estimates the cost from state $n$ to the goal.

• Admissible heuristic: Never overestimates the true cost ($h(n)\le h^{\ast }(n)$).
• Inadmissible heuristic: May overestimate.

Example: For the 8-puzzle, $h(n)$ = number of misplaced tiles.

• Admissible because the true cost ≥ number of moves needed to fix misplaced tiles.

1. Greedy Best-First Search (GBFS)

• How it works: Expands the node with the lowest $h(n)$ (greedy).
• Completeness: No (may get stuck in loops if no admissible heuristic).
• Optimality: No (may not find the least-cost path).

Worked Example: 8-puzzle with heuristic $h(n)$ = misplaced tiles. Initial state:

1 2 3
4 0 6
7 5 8

Goal state:

1 2 3
4 5 6
7 8 0

• $h(\text{initial})=5$ (tiles 5,6,7,8,0 are misplaced).
• Expand the state with the fewest misplaced tiles first.

Trace:

1. Expand initial state → 3 possible moves (swap 0 with 1,4,5).
2. Choose the move that minimizes $h(n)$:
   • Swap 0 and 5 → New state:

     1 2 3
     4 5 6
     7 0 8
     

     $h(n)=1$ (only 0 is misplaced).
3. Swap 0 and 8 → Goal reached!

Path: Initial → Swap(0,5) → Swap(0,8).

Limitation: Not optimal (may take a longer path than UCS/A*).

2. A* Search

Combines UCS and GBFS:

• Cost function: $f(n)=g(n)+h(n)$, where:
  • $g(n)$ = cost from start to $n$.
  • $h(n)$ = heuristic estimate from $n$ to goal.
• Completeness: Yes (if $h(n)$ is admissible and edge costs ≥ ε > 0).
• Optimality: Yes (if $h(n)$ is admissible).

Worked Example: Same 8-puzzle with $g(n)$ and $h(n)$. Assume each move costs 1.

1. Initial state: $g=0$, $h=5$, $f=5$.
2. Expand neighbors:
   • Swap(0,1): $g=1$, $h=4$, $f=5$.
   • Swap(0,4): $g=1$, $h=3$, $f=4$ → Choose this.
3. New state:

   1 2 3
   0 5 6
   7 4 8
   

   $h=3$ (tiles 4,5,0 misplaced).
4. Continue until goal is reached.

Why A is Optimal*:

• If $h(n)$ is admissible, A* never expands a node with $f(n)>f\ast (n)$ (optimal cost).

Comparison Table: Search Algorithms

*If step costs are equal.

In the Real World

1. eSewa (Nepal):

   • Idea Used: A Search* for optimal route planning in delivery logistics.
   • How: When you book a service (e.g., electricity bill payment), eSewa’s backend uses A* to find the shortest/fastest route for the delivery agent, balancing distance and traffic conditions (heuristic: estimated time to destination).

2. Pathao (Ride-Hailing App):

   • Idea Used: Uniform Cost Search (UCS) for dynamic ride matching.
   • How: When you request a ride, Pathao’s algorithm assigns the nearest available driver using UCS to minimize wait time. The "cost" here is a combination of distance, driver availability, and traffic (real-time data).

3. NTC (Nepal Telecom) Network Routing:

   • Idea Used: Dijkstra’s Algorithm (a variant of UCS) for packet routing.
   • How: When you send data through NTC’s network, packets are routed via the least-cost path (lowest latency or fewest hops) using Dijkstra’s algorithm on the network topology graph. Heuristics like signal strength or congestion levels guide the search.

4. Daraz (E-Commerce) Inventory Management:

   • Idea Used: Best-First Search (Greedy) for stock replenishment.
   • How: Daraz uses heuristics (e.g., sales velocity, seasonality) to prioritize which products to restock first. A greedy approach ensures high-demand items are replenished before low-demand ones, minimizing stockouts.

5. Nepal Rastra Bank’s Loan Approval:

   • Idea Used: Hill Climbing for risk assessment.
   • How: When evaluating loan applications, the bank starts with a baseline risk score and iteratively adjusts it (e.g., increasing if credit history is poor, decreasing if collateral is strong). The "hill" is the optimal approval decision (maximizing profit while minimizing default risk).

Adversarial Search: Minimax and Alpha-Beta Pruning

Used in two-player games (e.g., chess, tic-tac-toe).

Minimax Algorithm

• How it works:
  • Maximizing player (e.g., AI) tries to maximize score.
  • Minimizing player (e.g., opponent) tries to minimize score.
  • Recursively evaluate all possible moves to depth $d$.
• Formula:

  minimax(node, depth):
      if node is terminal or depth = 0:
          return heuristic_value(node)
      if node is maximizing:
          return max(minimax(child, depth-1) for child in node.children)
      else:
          return min(minimax(child, depth-1) for child in node.children)
  

Worked Example: Tic-Tac-Toe (X is maximizing, O is minimizing). Initial board:

X |   |
---------
  | O |
---------
  |   |

• X’s possible moves: Top-center, bottom-left, bottom-right.
• Evaluate each move recursively to depth 2 (assuming O plays optimally).

Trace:

1. If X plays bottom-left (C), O can block by playing top-center → X wins next turn.
   • Score for C: +1 (X wins).
2. If X plays bottom-right (D), O can block by playing top-center → X wins next turn.
   • Score for D: +1.
3. If X plays top-center (B), O can win immediately by playing bottom-right.
   • Score for B: -1 (X loses).

• Minimax chooses C or D (both lead to X winning).

Alpha-Beta Pruning

Optimizes Minimax by cutting off branches that cannot influence the final decision.

• Alpha: Best value so far for the maximizer.
• Beta: Best value so far for the minimizer.
• Prune if a child’s value ≤ alpha (maximizer) or ≥ beta (minimizer).

Worked Example: Same tic-tac-toe board.

1. Evaluate B (top-center) first:
   • O responds by playing bottom-right → X loses.
   • Alpha = -1.
2. Evaluate C (bottom-left):
   • O’s best response is top-center → X wins.
   • Alpha = +1.
   • Since +1 > -1, prune D (bottom-right) because even if D leads to a win, it’s worse than C.

Result: Alpha-beta prunes 2 out of 3 branches, reducing computation.

Exam Tip

1. State Space Graphs: Always draw the graph for any problem. Label nodes, edges, and costs clearly. Examiners love visual proofs!

   • Example: For the 8-puzzle, show 3-4 states and their connections.

2. Heuristic Functions:

   • Define admissible vs. inadmissible with examples.
   • For A*, prove optimality by showing $f(n)=g(n)+h(n)\le f\ast (n)$.

3. Algorithm Traces:

   • Show step-by-step expansion for BFS/DFS/A*/Minimax.
   • Use tables to compare $g(n)$, $h(n)$, and $f(n)$ for A*.

4. Real-World Applications:

   • Link search algorithms to Nepali examples (e.g., Pathao’s UCS, eSewa’s A*).
   • For Minimax, use tic-tac-toe or chess (but simplify to 2-3 moves).

5. Common Pitfalls:

   • GBFS is not complete: State this explicitly and give an example where it fails (e.g., a state space with loops and no admissible heuristic).
   • DFS may miss solutions: Show a case where DFS with depth limit $d$ misses a solution at depth $d+1$.
   • A requires admissible heuristics: If $h(n)$ is inadmissible, A may not be optimal.

6. Short-Answer Questions:

   • Memorize definitions:
     • Admissible heuristic: $h(n)\le h^{\ast }(n)$.
     • Informed vs. uninformed: Informed uses $h(n)$, uninformed does not.
     • Minimax: Alternating maximizer/minimizer in game trees.