Mathematics and Statistics Vol. 8(3), pp. 339 - 346
DOI: 10.13189/ms.2020.080313
Reprint (PDF) (216Kb)

High-speed Dynamic Programming Algorithms in Applied Problems of a Special Kind

V. I. Struchenkov ^*, D. A. Karpov
Department of General Informatics, Institute of Cybernetics of the Russian Technological University (MIREA), Russia

ABSTRACT

The article discusses the solution of applied problems, for which the dynamic programming method developed by R. Bellman in the middle of the last century was previously proposed. Currently, dynamic programming algorithms are successfully used to solve applied problems, but with an increase in the dimension of the task, the reduction of the counting time remains relevant. This is especially important when designing systems in which dynamic programming is embedded in a computational cycle that is repeated many times. Therefore, the article analyzes various possibilities of increasing the speed of the dynamic programming algorithm. For some problems, using the Bellman optimality principle, recurrence formulas were obtained for calculating the optimal trajectory without any analysis of the set of options for its construction step by step. It is shown that many applied problems when using dynamic programming, in addition to rejecting unpromising paths lead to a specific state, also allow rejecting hopeless states. The article proposes a new algorithm for implementing the R. Bellman principle for solving such problems and establishes the conditions for its applicability. The results of solving two-parameter problems of various dimensions presented in the article showed that the exclusion of hopeless states can reduce the counting time by 10 or more times.

KEYWORDS
Dynamic Programming, System State, Optimal Trajectory (path), Optimality Principle, Pareto Sets

Cite This Paper in IEEE or APA Citation Styles
(a). IEEE Format:
[1] V. I. Struchenkov , D. A. Karpov , "High-speed Dynamic Programming Algorithms in Applied Problems of a Special Kind," Mathematics and Statistics, Vol. 8, No. 3, pp. 339 - 346, 2020. DOI: 10.13189/ms.2020.080313.

(b). APA Format:
V. I. Struchenkov , D. A. Karpov (2020). High-speed Dynamic Programming Algorithms in Applied Problems of a Special Kind. Mathematics and Statistics, 8(3), 339 - 346. DOI: 10.13189/ms.2020.080313.