There is a vast literature on search techniques in operations research, computer science, and AI. Search was seen early on as one of the foundations of AI. The AI literature emphasizes the use of heuristics in search.

Breadth-first search was invented by Moore [1959]. Lowest-cost-first search with multiple path pruning is one of the variants of Dijkstra’s algorithm [Dijkstra, 1959], and is also equivalent to $A^{\ast }$ with a heuristic of zero. The $A^{\ast }$ algorithm was developed by Hart et al. [1968]. The optimality of $A^{\ast }$ is investigated by Dechter and Pearl [1985]. For a detailed analysis of heuristic search, see Pearl [1984].

Depth-first iterative deepening is described in Korf [1985]. Branch-and-bound search, developed in the operations research community, is described in Lawler and Wood [1966].

Dynamic programming is a general algorithm that will be used as a dual to search algorithms in other parts of this book. See Cormen et al. [2022] for more details on the general class of dynamic programming algorithms.

Bidirectional search was pioneered by Pohl [1971]. Chen et al. [2017] provide a bidirectional search algorithm with provable optimality.

The idea of using pattern databases as a source of heuristics for $A^{\ast }$ search was proposed by Culberson and Schaeffer [1998] and further developed by Felner et al. [2004]. Minsky [1961] discussed islands and problem reduction.

Dolgov et al. [2010] and Delling et al. [2015] describe real-world route planning for autonomous vehicles and Bing maps, respectively.