Artificial Intelligence Search Algorithms
Richard E. Korf · Chapman & Hall/CRC applied algorithms and data structures series · 1998
Introduction Search is a universal problem-solving mechanism in artificial intelligence (AI). In AI problems, the sequence of steps required for solution of a problem are not known a priori, but often must be determined by a systematic 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, two-player games, and constraint-satisfaction problems. Classic examples in the AI literature of pathfinding problems are the sliding-tile puzzles, including the 3 \\Theta 3 Eight Puzzle (see Fig. 1) and its larger relatives the 4 \\Theta 4 Fifteen Puzzle, and 5 \\Theta 5 Twenty-Four Puzzle. The Eight Puzzle consists of a 3 \\Theta 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 h