AND/OR graph heuristic search methods
- 1 January 1985
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 32 (1) , 28-51
- https://doi.org/10.1145/2455.2459
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.Keywords
This publication has 5 references indexed in Scilit:
- Three approaches to heuristic search in networksJournal of the ACM, 1985
- Admissible heuristic search in and/or graphsTheoretical Computer Science, 1983
- Search Algorithms Under Different Kinds of Heuristics—A Comparative StudyJournal of the ACM, 1983
- Optimizing decision trees through heuristically guided searchCommunications of the ACM, 1978
- An admissible and optimal algorithm for searching AND/OR graphsArtificial Intelligence, 1971