An admissible and optimal algorithm for searching AND/OR graphs

摘要

An AND/OR graph is a graph which represents a problem-solving process. A solution graph is a subgraph of the AND/OR graph which represents a derivation for a solution of the problem. Therefore, solving a problem can be viewed as searching for a solution graph in an AND/OR graph. A “cost” is associated with every solution graph. A minimal solution graph in a solution graph with minimal cost. In this paper, an algorithm for searching for a minimal solution graph in an AND/OR graph is described. If the “lower bound” condition is satisfied, the algorithm is guaranteed to find a minimal solution graph when one exists. Furthermore, the “optimality” of the algorithm is also proved.