Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).
3.9 References and Further Reading
There is a lot of information on search techniques in the literature of operations research, computer science, and AI. Search was seen early on as one of the foundations of AI. The AI literature emphasizes heuristic search.
Basic search algorithms are discussed in Nilsson (1971). For a detailed analysis of heuristic search see Pearl (1984). The A* algorithm was developed by [Hart et al. (1968)].
Depth-first iterative deepening is described in Korf (1985).
Branch-and-bound search was developed in the operations research community and 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 the book. The specific algorithm presented here was invented by Dijkstra (1959). See Cormen et al. (2001) for more details on the general class of dynamic programming algorithms.
The idea of using dynamic programming as a source of heuristics for A* search was proposed by Culberson and Schaeffer (1998) and further developed by Felner et al. (2004).
Minsky (1961) discussed islands and problem reduction.
