Back to Search Start Over

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

Authors :
V. I. Struchenkov
D. A. Karpov
Source :
Mathematics and Statistics. 8:339-346
Publication Year :
2020
Publisher :
Horizon Research Publishing Co., Ltd., 2020.

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.

Details

ISSN :
23322144 and 23322071
Volume :
8
Database :
OpenAIRE
Journal :
Mathematics and Statistics
Accession number :
edsair.doi...........4dc197b6bc309b654b491bc041870572
Full Text :
https://doi.org/10.13189/ms.2020.080313