×

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.)
PDFBibTeX XMLCite