Search and Problem Solving
Many AI problems can be formulated as search problems: finding a sequence of actions leading from an initial state to a goal state. Search algorithms systematically explore possible solutions.
Problem Formulation
A search problem has: initial state, actions (possible moves), transition model (result of actions), goal test, and path cost. Examples: route finding, 8-puzzle, missionaries and cannibals. The state space is the set of all reachable states.
Uninformed Search
Breadth-First Search (BFS): explores level by level, guarantees shortest path, but uses much memory. Depth-First Search (DFS): explores deeply first, uses less memory, but may not find shortest path. Iterative Deepening: combines BFS optimality with DFS memory efficiency. Uniform Cost Search: expands cheapest-cost node.
Informed Search
Heuristic search uses domain knowledge to guide exploration. Greedy best-first search expands the node closest to the goal (heuristic h(n)). A* search uses f(n) = g(n) + h(n) where g is cost so far and h is estimated remaining cost. A* is optimal when h is admissible (never overestimates).
Local Search
Hill climbing moves to the best neighbour (can get stuck in local optima). Simulated annealing allows occasional bad moves to escape local optima. Genetic algorithms use evolution-inspired operators: selection, crossover, mutation. Local search is used for optimisation problems.
Constraint Satisfaction
CSPs define problems with variables, domains, and constraints. Examples: map colouring, Sudoku, scheduling. Techniques: backtracking, constraint propagation (arc consistency), and heuristics (MRV). CSPs combine search with inference.
Adversarial Search
Game playing uses adversarial search. Minimax finds optimal moves assuming optimal opponent. Alpha-beta pruning reduces search space. Monte Carlo Tree Search (MCTS) is used in Go and complex games.
Summary
Search algorithms are fundamental to AI problem solving. From uninformed BFS/DFS to informed A* and adversarial minimax, choosing the right strategy depends on the problem.