Algorithms for generating ordered solutions for explicit AND/OR structures

DOI10.1613/JAIR.3576zbMATH Open1280.68240arXiv1401.5852OpenAlexW1647983470MaRDI QIDQ2905385

Author name not available (Why is that?)

Publication date: 27 August 2012

Published in: (Search for Journal in Brave)

Abstract: We present algorithms for generating alternative solutions for explicit acyclic AND/OR structures in non-decreasing order of cost. The proposed algorithms use a best first search technique and report the solutions using an implicit representation ordered by cost. In this paper, we present two versions of the search algorithm -- (a) an initial version of the best first search algorithm, ASG, which may present one solution more than once while generating the ordered solutions, and (b) another version, LASG, which avoids the construction of the duplicate solutions. The actual solutions can be reconstructed quickly from the implicit compact representation used. We have applied the methods on a few test domains, some of them are synthetic while the others are based on well known problems including the search space of the 5-peg Tower of Hanoi problem, the matrix-chain multiplication problem and the problem of finding secondary structure of RNA. Experimental results show the efficacy of the proposed algorithms over the existing approach. Our proposed algorithms have potential use in various domains ranging from knowledge based frameworks to service composition, where the AND/OR structure is widely used for representing problems.

Full work available at URL: https://arxiv.org/abs/1401.5852

Mathematics Subject Classification ID

No records found.

This page was built for publication: Algorithms for generating ordered solutions for explicit AND/OR structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2905385)