Ariel Felner

This paper makes two pedagogical contributions. First, we describe two macro operators for best-first search algorithms: the collapse macro where a subtree is deleted from memory and its best frontier value is stored in its root, and, the restore macro (the inverse of collapse) where the subtree is restored to its previous structure. We show that many known search algorithms can be easily described by using these macros. The second contribution 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 collapse and restore macros. ILBFS and RBFS are identical in the nodes that they visit and have identical properties. But, I believe that ILBFS is pedagogically simpler to describe and understand; it could at least serve as a pedagogical tool for RBFS.