Position Paper: The Collapse Macro in Best-First Search Algorithms and an Iterative Variant of RBFS

Proceedings of the International Symposium on Combinatorial Search, 8

Volume

Vol. 8 No. 1 (2015): Eighth Annual Symposium on Combinatorial Search

Full Papers

This paper makes two pedagogical contributions. First, we describe two macrooperators for best-first search algorithms: the collapse macro where asubtree is deleted from memory and its best frontier value is stored in itsroot, and, the restore macro (the inverse of collapse) where thesubtree is restored to its previous structure. We show that many known searchalgorithms can be easily described by using these macros. The secondcontribution is an algorithm called Iterative Linear Best-first Search (ILBFS). ILBFS is equivalent to RBFS. While RBFS uses a recursive structure,ILBFS uses the regular structure of BFS with occasionally using the collapseand restore macros. ILBFS and RBFS are identical in the nodes that they visitand have identical properties. But, I believe that ILBFS is pedagogicallysimpler to describe and understand; it could at least serve as a pedagogicaltool for RBFS.

10.1609/socs.v6i1.18355