Карпов Дмитрий Анатольевич, кандидат технических наук, заведующий кафедрой общей информатики Института кибернетики
119454, Москва, пр-т Вернадского, д. 78
Dmitry A. Karpov, Cand. Sci. (Engineering), Head of the Department of General Informatics of the Institute of Cybernetics
78, Vernadskogo pr., Moscow 119454
Струченков Валерий Иванович, доктор технических наук, профессор кафедры общей информатики Института кибернетики
119454, Москва, пр-т Вернадского, д. 78
Valeriy I. Struchenkov, Dr. Sci. (Engineering), Professor of the Department of General Informatics of the Institute of Cybernetics
78, Vernadskogo pr., Moscow 119454
В статье рассматривается разработанный Р. Беллманом алгоритм динамического программирования, основанный на поиске оптимальной траектории, соединяющей узлы предварительно заданной регулярной сетки состояний. Анализируются возможности резкого повышения эффективности применения динамического программирования при решении прикладных задач, обладающих специфическими особенностями, что позволяет отказаться от разбиения регулярной сетки состояний и реализовать алгоритм поиска оптимальной траектории при отбраковке не только бесперспективных вариантов путей, приводящих в каждое из состояний, и всех их продолжений, как в алгоритме Р. Беллмана, но и собственно бесперспективных состояний и всех вариантов исходящих из них путей. Сформулированы и обоснованы условия, при которых возможна отбраковка бесперспективных состояний. Установлено, что многие прикладные задачи удовлетворяют этим условиям. Для решения подобных задач предложен и реализован новый алгоритм динамического программирования. Приводятся конкретные примеры таких прикладных задач: оптимальное распределение однородного ресурса между несколькими потребителями, оптимальная загрузка транспортных средств, оптимальное распределение финансов при выборе инвестиционных проектов. Для решения этих задач ранее предлагались алгоритмы динамического программирования с отбраковкой бесперспективных путей, но без отбраковки состояний. Число бесперспективных состояний, появляющихся на различных этапах динамического программирования, и, соответственно, эффективность нового алгоритма, зависит от конкретных числовых значений исходных данных. Для двухпараметрической задачи оптимальной загрузки транспортных средств при ограничении по весу и объёму приведены результаты сопоставительных расчётов по алгоритму Р. Беллмана и по новому алгоритму динамического программирования. В качестве исходных данных для серии расчётов использовались псевдослучайные числа. В результате анализа показано, что сравнительная эффективность алгоритма с отбраковкой состояний растёт при увеличении размерности задачи. Так в задаче оптимального выбора предметов для загрузки транспортного средства заданной грузоподъёмности при числе предметов 150 количество запоминаемых состояний и время счёта снижаются в 50 и 57 раз, соответственно, при использовании нового алгоритма по сравнению с классическим алгоритмом Р. Беллмана. Для 15 предметов соответствующие числа равны 13 и 4.
The article discusses the dynamic programming algorithm developed by R. Bellman, based on the search for the optimal trajectory connecting the nodes of a predefined regular grid of states. Possibilities are analyzed for a sharp increase in the effectiveness of using dynamic programming in solving applied problems with specific features, which allows us to refuse to split a regular grid of states and implement an algorithm for finding the optimal trajectory when rejecting not only unpromising options for paths leading to each of the states, and all of them continuations, as in R. Bellmanʼs algorithm, but also actually hopeless states and all variants of paths emanating from them. The conditions are formulated and justified under which the rejection of hopeless states is possible. It has been established that many applied problems satisfy these conditions. To solve such problems, a new dynamic programming algorithm described in the article is proposed and implemented. Concrete examples of such applied problems are given: the optimal distribution of a homogeneous resource between several consumers, the optimal loading of vehicles, the optimal distribution of finances when choosing investment projects. To solve these problems, dynamic programming algorithms with rejecting unpromising paths, but without rejecting states, were previously proposed. The number of hopeless states that appear at various stages of dynamic programming and, accordingly, the effectiveness of the new algorithm depends on the specific numerical values of the source data. For the two-parameter problem of optimal loading of vehicles with weight and volume constraints, the results of comparative calculations by the R. Bellman algorithm and the new dynamic programming algorithm are presented. As a source of data for a series of calculations, pseudorandom numbers were used. As a result of the analysis, it was shown that the comparative efficiency of the algorithm with rejection of states increases with increasing dimension of the problem. So, in the problem of the optimal choice of items for loading a vehicle of a given carrying capacity with a number of items of 150, the number of memorized states and the counting time are reduced by 50 and 57 times, respectively, when using the new algorithm compared to the classical algorithm of R. Bellman. And for 15 items, the corresponding numbers are 13 and 4.
The authors declare that there are no conflicts of interest present.