An efficient algorithm for searching implicit AND/OR graphs with cycles

摘要

We present an efficient AO∗-like algorithm that handles cyclic graphs without neither unfolding the cycles nor looping through them. Its top-down search strategy is based on Mahanti and Bagchi's CF [J. ACM 32 (1985) 28], whereas its bottom-up revision process is inspired in Chakrabarti's REV∗ [Artificial Intelligence 65 (1994) 329]. However, important modifications have been introduced in both algorithms to attain a true integration and gain efficiency. Proofs of correctness and completeness are included. Up to our knowledge, the resulting algorithm—called CFCREV∗—is the most efficient one available for this problem.