Martelli A., Montanari U. From dynamic programming to search algorithms with functional costs. Internal note IEI-B75-01, 1975. |

Abstract (English) |
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. | |

Subject |

1) Download Document PDF |

Open access Restricted Private