12. Problem Solving in AI

Problem Solving

Search Algorithms

Many AI problems can be framed as searching through a state space to find a goal state. Search algorithms explore this space systematically.

Breadth-First Search (BFS)

Explores all nodes at the current depth level before moving deeper. Guarantees shortest path (fewest steps) but uses significant memory.

function BFS(initial, goal, expand):
    queue = [initial]
    visited = {initial}

    while queue not empty:
        state = queue.pop_front()
        if state == goal: return path_to(state)

        for next_state in expand(state):
            if next_state not in visited:
                visited.add(next_state)
                queue.push_back(next_state)

    return None  # No solution found

Depth-First Search (DFS)

Explores as deep as possible along each branch before backtracking. Uses less memory but may not find the shortest path.

A* Search (Informed)

Combines actual cost from start (g) and estimated cost to goal (h) to guide search: f(n) = g(n) + h(n). Optimal and complete when heuristic h is admissible.

function AStar(initial, goal, expand, heuristic):
    frontier = PriorityQueue()
    frontier.push(initial, heuristic(initial))
    visited = {}

    while frontier not empty:
        current = frontier.pop()
        if current == goal: return path

        for neighbor in expand(current):
            new_cost = g(current) + cost(current, neighbor)
            if neighbor not in visited or new_cost < visited[neighbor]:
                visited[neighbor] = new_cost
                priority = new_cost + heuristic(neighbor)
                frontier.push(neighbor, priority)

    return None

Constraint Satisfaction Problems (CSPs)

CSPs involve finding values for variables that satisfy a set of constraints. Examples include Sudoku, map coloring, and scheduling.

CSP Components:
- Variables: {A, B, C, ...}
- Domains: {Red, Green, Blue} for each variable
- Constraints: A ≠ B, B ≠ C, A ≠ C

Algorithm: Backtracking with forward checking

Real-World CSPs

• Scheduling — Assigning classes to time slots without conflicts
• Resource Allocation — Assigning tasks to workers with skill constraints
• Configuration — Setting parameters for a product (car options, computer builds)
• Cryptarithmetic — Solving puzzles like SEND + MORE = MONEY