Korf, Richard E. Space complexity of combinatorial search. (English) Zbl 1216.68084 Dechter, Rina (ed.) et al., Heuristics, probability and causality. A tribute to Judea Pearl. London: College Publications (ISBN 978-1-90497-66-6/hbk; 978-1-904987-65-9/pbk). Tributes 11, 53-62 (2010). Summary: We present a number of different algorithms, designed over the past 25 years, to deal with the space complexity of brute-force and heuristic search. They fall into two general categories. The linear-space search algorithms, including depth-first search, depth-first iterative-deepening, iterative-deepening-A\(^*\), and recursive best-first search, use very little memory but cannot detect most duplicate nodes. They perform very well on trees, but poorly on highly-connected graphs, such as a grid. The best-first search algorithms, including breadth-first search, A\(^*\), weighted A\(^*\), frontier search, and disk-based algorithms, detect all duplicate nodes, and hence perform well on highly-connected graphs. The best-first algorithms are limited by the amount of memory available, except for the disk-based techniques, which are limited by time in practice.For the entire collection see [Zbl 1202.00091]. MSC: 68P10 Searching and sorting 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) Keywords:linear-space search algorithms; recursive best-first search PDFBibTeX XMLCite \textit{R. E. Korf}, Tributes 11, 53--62 (2010; Zbl 1216.68084)