Publication
An efficient algorithm for searching implicit AND/OR graphs with cycles
Journal Article (2000)
Journal
Artificial Intelligence
Pages
1-30
Volume
124
Number
1
Doc link
http://dx.doi.org/10.1016/S0004-3702(00)00063-1
File
Authors
Projects associated
Abstract
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, whereas its bottom-up revision process is inspired in Chakrabarti's REV*. 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.
Categories
artificial intelligence.
Author keywords
AND/OR graphs, assembly/dissassembly problems, cyclic graphs, heuristic search
Scientific reference
P. Jiménez and C. Torras. An efficient algorithm for searching implicit AND/OR graphs with cycles. Artificial Intelligence, 124(1): 1-30, 2000.
Follow us!