Istituto di Scienza e Tecnologie dell'Informazione     
Martelli A., Montanari U. From dynamic programming to search algorithms with functional costs. Internal note IEI-B75-01, 1975.
In this paper we show that any dynamic programming problem can be reduced to the problem of finding a minimal-cost path in a functionally wighted graph, i.e. a graph with monotone cost functions associated with the arcs. The problem of searching a functionally weighted graph is approached here using artificial intelligence methods. A general heuristic search algorithm with estimate is given, which is a nontrivial extention of algorithm A* by Hart, Nilsson and Raphael. Putting some constraints on cost functions and on the estimate, this algorithm can be simplified until the classical version, with additive cost funcions, is reached. Finally, a construction is given, which reduces a search algorithm with a strictly monotone estimate to a search algorithm without estimate on a modified graph.

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