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

From MaRDI portal
Revision as of 04:01, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
scientific article
Language Label Description Also known as
English
An efficient algorithm for searching implicit AND/OR graphs with cycles
scientific article

    Statements

    An efficient algorithm for searching implicit AND/OR graphs with cycles (English)
    0 references
    0 references
    0 references
    12 December 2000
    0 references
    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 [\textit{A. Mahanti} and \textit{A. Bagchi}, J. Assoc. Comput. Math. 32, 28-51 (1985; Zbl 0633.68098)], whereas its bottom-up revision process is inspired in Chakrabarti's \(\text{REV}^{*}\) [\textit{P. P. Chakrabarti}, Artif. Intell. 65, No. 2, 329-345 (1994; Zbl 0803.68123)]. 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.
    0 references
    AND/OR graphs
    0 references
    cyclic graphs
    0 references
    heuristic search
    0 references
    assembly/disassembly problems
    0 references

    Identifiers