ML Anthology

Additive AND/OR Graphs

Alberto Martelli, Ugo Montanari
IJCAI 1973 pp. 1-11
/ijcai/1973/martelli1973ijcai-additive/

Abstract

Additive AND/OR graphs are defined as AND/ OR graphs without circuits, which can be considered as folded AND/OR trees; i. e. the cost of a common subproblem is added to the cost as many times as the subproblem occurs, but it is computed only once. Additive AND/OR graphs are naturally obtained by reinterpreting the dynamic programming method in the light of the problem-reduction approach. An example of this reduction is given. A top-down and a bottom-up method are proposed for searching additive AND/OR graphs. These methods are, respectively, extensions of the arrow method proposed by Nilsson for searching AND/OR trees and Dijkstra's algorithm for finding the shortest path. A proof is given that the two methods find an optimal solution whenever a solution exists.

PDF Semantic Scholar

Cite

Text

Martelli and Montanari. "Additive AND/OR Graphs." International Joint Conference on Artificial Intelligence, 1973.

Markdown

[Martelli and Montanari. "Additive AND/OR Graphs." International Joint Conference on Artificial Intelligence, 1973.](https://mlanthology.org/ijcai/1973/martelli1973ijcai-additive/)

BibTeX

@inproceedings{martelli1973ijcai-additive,
  title     = {{Additive AND/OR Graphs}},
  author    = {Martelli, Alberto and Montanari, Ugo},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {1973},
  pages     = {1-11},
  url       = {https://mlanthology.org/ijcai/1973/martelli1973ijcai-additive/}
}