AND/OR graph heuristic search methods

Abstract

Two new marking algorithms for AND/OR graphs called CF and CS are presented. For admissible heuristics CS is not needed, and CF is shown to be preferable to the marking algorithms of Martelli and Montanari. When the heuristic is not admissible, the analysis is carried out with the help of the notion of the first and second discriminants of an AND/OR graph. It is proved that in this case CF can be followed by CS to get optimal solutions, provided the sumcost criterion is used and the first discriminant equals the second. Estimates of time and storage requirements are given. Other cost measures, such as maxcost, are also considered, and a number of interesting open problems are enumerated.