A. Mahanti
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.
- 1 BAGCHI, A., AND MAHANTI, A.Search algorithms under different kinds of heuristics--A comparative study. J. ACM 30, 1 (Jan. 1983), 1-21. Google Scholar
- 2 BAGCHI, A., AND MAHANTI, A.Admissible heuristic search in AND/OR graphs. Theor. Comput. Sci. 24, 2 (July 1983), 207-219.Google Scholar
- 3 BAGCHI, A., AND MAHANTI, A.Three approaches to heuristic search in networks. J. ACM 32, 1 (Jan. 1985), 1-27. Google Scholar
- 4 CHANG, C. L., AND SLAGLE, J. R. An admissible and optimal algorithm for searching AND/OR graphs. Artif Intell. 2 (1971), 117-128.Google Scholar
- 5 HOROWITZ, E., AND SAHNi, S.Fundamentals of Computer Algorithms. Computer Science Press, Woodland Hills, Calif., 1978. Google Scholar
- 6 MARTELLI, A., AND MONTANARI, O.Additive AND/OR Graphs. In Proceedings of the 3rd International Joint Conference on Artificial Intelligence (Stanford, Calif., Aug. 1973), pp. 1-11.Google Scholar
- 7 MARTELLI, A., AND MONTANARi, U.Optimizing decision trees through heuristically guided search. Commun. ACM, 12, 12 (Dec. 1978), 1025-1039 Google Scholar
- 8 NILSSON, N. J.Problem Solving Methods in Artificial intelligence. McGraw-Hill, New York, 1971. Google Scholar
- 9 NILSSON, N. J.Principles of Artificial Intelligence. Tioga, Palo Alto, Calif., 1980. Google Scholar
Index Terms
- AND/OR graph heuristic search methods
Recommendations
Heuristic methods for graph coloring problems
SAC '05: Proceedings of the 2005 ACM symposium on Applied computingIn this work, the Graph Coloring Problem and its generalizations - the Bandwidth Coloring Problem, the Multicoloring Problem and the Bandwidth Multicoloring Problem - are studied. A Squeaky Wheel Optimization with Tabu Search heuristic is developed and ...
Heuristic Search for the Generalized Minimum Spanning Tree Problem
The generalized minimum spanning tree (GMST) problem occurs in telecommunications network planning, where a network of node clusters needs to be connected via a tree architecture using exactly one node per cluster. The problem is known to be NP-hard, ...
Reviews
Gary Carlson
Two new marking algorithms are described. They appear to be better than the ones of Martelli and Montanari [1,2]. To understand this paper it is necessary to know something about directed graphs. This very specific technical paper is not useful to the computer generalist. AND/OR graphs can be seen as a generalization of directed graphs and therefore should be more powerful. This paper does not cover graphs with loops. Overall, the paper is well done, but very narrow in scope. Some statements are not very clear. For example, the authors state, on p. 31, …“a non-terminal leaf node always has an infinite heuristic estimate…”It is not clear why this statement is made, nor its significance. The theorems and proofs seem consistent and correct.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments