𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by P. Jiménez; C. Torras

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
371 KB
Volume
124
Category
Article
ISSN
0004-3702

No coin nor oath required. For personal study only.

✦ Synopsis

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 CFC REV * -is the most efficient one available for this problem.

📜 SIMILAR VOLUMES

Algorithms for searching explicit AND/OR
Algorithms for searching explicit AND/OR graphs and their applications to problem reduction search
✍ P.P. Chakrabarti 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 756 KB

Chakrabarti, P.P., Algorithms for searching explicit AND/OR graphs and their applications to problem reduction search, Artificial Intelligence 65 (1994) 329-345. We present algorithms for finding out optimal cost solutions of an explicit AND/OR graph. We show that these new algorithms can work on A