zbMATH — the first resource for mathematics

Automated dynamic programming. (English) Zbl 1180.90354
Summary: Since the first book in dynamic programming was published in 1957, this algorithm design strategy has become a current problem solving method in several fields of science. The dynamic programming problem solving process can be divided into two steps. Firstly, we establish the functional equation of the problem, a recursive formula that implements the principle of the optimality (mathematical part). Secondly, a computer program is elaborated that processes the recursive formula in bottom-up way (programming part). In this paper we are going to present a method and a software tool that automates the programming part of the dynamic programming process in case of several problems.
90C39 Dynamic programming
68W40 Analysis of algorithms
68R10 Graph theory (including graph drawing) in computer science
05C12 Distance in graphs