ABSTRACT
Search is a universal problem-solving mechanism in artificial intelligence (AI). In AI problems, the sequence of steps required for the solution of a problem is not known a priori, but often must be determined by a trial-and-error exploration of alternatives. The problems that have been addressed by AI search algorithms fall into three general classes: single-agent pathfinding problems, game playing, and constraint-satisfaction problems. Classic examples in the AI literature of single-agent pathfinding problems are the sliding-tile
puzzles, including the 3 × 3 eight puzzle (see Figure 22.1) and its larger relatives the 4 × 4 fifteen 22-1
puzzle and 5 × 5 twenty-four puzzle. The eight puzzle consists of a 3 × 3 square frame containing eight numbered square tiles and an empty position called the blank. The legal operators are to slide any tile that is horizontally or vertically adjacent to the blank into the blank position. The problem is to rearrange the tiles from some random initial configuration into a particular desired goal configuration. The sliding-tile puzzles are common testbeds for research inAI search algorithms because they are very simple to represent andmanipulate, yet finding optimal solutions to theN×N generalization of the sliding-tile puzzles is NP-complete [38]. Another well-known example of a single-agent pathfinding problem is Rubik’s cube. Real-world examples include theorem proving, the traveling salesman problem, and vehicle navigation. In each case, the task is to find a sequence of operations that maps an initial state to a goal state. A second class of search problems include games, such as chess, checkers, Othello, backgammon,
bridge, poker, and Go. The third category is constraint-satisfaction problems, such as the N-queens problem or Sudoku. The task in the N-queens problem is to placeN queens on anN×N chessboard, such that no two queens are on the same row, column, or diagonal. The Sudoku task is to fill each empty cell in a 9 × 9 matrix with a digit from zero through nine, such that each row, column, and nine 3 × 3 submatrices contain all the digits zero through nine. Real-world examples of constraintsatisfaction problems are ubiquitous, including boolean satisfiability, planning, and scheduling applications. We begin by describing the problem-space model on which search algorithms are based. Brute-
force searches are then considered including breadth-first, uniform-cost, depth-first, depth-first iterative-deepening, bidirectional, frontier, and disk-based search algorithms. Next, we introduce heuristic evaluation functions, including pattern databases, and heuristic search algorithms including pure heuristic search, the A∗ algorithm, iterative-deepening-A∗, depth-first branch-and-bound, the heuristic path algorithm, and recursive best-first search. We then consider single-agent algorithms that interleave search and execution, including minimin lookahead search, real-time-A∗, and learning-real-time-A∗. Next, we consider game playing, including minimax search, alpha-beta pruning, quiescence, iterativedeepening, transposition tables, special-purposehardware,multiplayer games, and imperfect and hidden information.We then examine constraint-satisfaction algorithms, such as chronological backtracking, intelligent backtracking techniques, constraint recording, and local search algorithms. Finally, we consider open research problems in this area. The performance of these algorithms, in terms of the costs of the solutions they generate, the amount of time the algorithms take to execute, and the amount of computer memory they require are of central concern
throughout. Since search is a universal problem-solving method, what limits its applicability is the efficiency with which it can be performed.
