Istituto di Scienza e Tecnologie dell'Informazione     
Martelli A., Montanari U. Additive and/or graphs. Internal note IEI-B73-02, 1973.
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 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 method 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 solution exists.
Subject AND/OR graphs. problem-reduction approach, dynamic programming, optimal solution, heuristic search.

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional