10.14489/vkit.2020.08.pp.003-011

DOI: 10.14489/vkit.2020.08.pp.003-011

Карпов Д. А., Струченков В. И.
ЭФФЕКТИВНЫЕ АЛГОРИТМЫ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
(с. 3-11)

Аннотация. Проанализирована проблема повышения быстродействия алгоритмов динамического программирования при решении прикладных задач большой размерности. Динамическое программирование рассмотрено как методология, которая позволяет с единых теоретических позиций разрабатывать алгоритмы решения задач, допускающих формализацию в виде многоэтапных (многошаговых) процессов. Показано, что традиционные алгоритмы динамического программирования, основанные на предварительном задании регулярной сетки состояний, малоэффективны, особенно, если параметры, определяющие состояния, не являются целочисленными. Рассмотрены задачи, при решении которых целесообразно строить множества состояний в процессе счета, переходя от одного этапа к другому. Сформулированы дополнительные условия, которым должна удовлетворять задача, чтобы в множества состояний на каждом шаге не попадали заведомо бесперспективные состояния. Приведены примеры прикладных задач, которые более эффективно решаются предлагаемым алгоритмом с отбраковкой состояний. Применительо к двухпараметрическим задачам на конкретных примерах продемонстрирована эффективность алгоритма с отбраковкой состояний по сравнению с традиционными алгоритмами, особенно с повышением размерности задачи. Рассмотрена прикладная задача, при решении которой динамическое программирование используется для построения рекуррентных формул расчета оптимального решения без перебора вариантов вообще.

Ключевые слова: динамическое программирование; оптимальная траектория (путь); состояние системы; принцип оптимальности; множества Парето.

Karpov D. A., Struchenkov V. I.
EFFECTIVE DYNAMIC PROGRAMMING ALGORITHMS
(pp. 3-11)

Abstract. This article is devoted to the analysis of the possibilities of increasing the speed of dynamic programming algorithms in solving applied problems of large dimension. Dynamic programming is considered rather than as an optimization method, but as a methodology that allows developing, from a single theoretical point of view, algorithms for solving problems that can be formalized in the form of multi-stage (multi-step) processes in which similar tasks are solved at all steps. It is shown that traditional dynamic programming algorithms based on preliminary setting of a regular grid of states are ineffective, especially if the parameters defining the states are not integer. The problems are considered, in the solution of which it is advisable to build a set of states in the process of counting, moving from one stage to another. Additional conditions are formulated that must be satisfied by the problem so that deliberately hopeless states do not fall into sets of states at each step. This ensures the rejection of not only the paths leading to each of the states, as in traditional dynamic programming algorithms, but also the unpromising states themselves, which greatly increases the efficiency of dynamic programming. Examples of applied problems are given, for the solution of which traditional dynamic programming algorithms were previously proposed, but which can be more efficiently solved by the proposed algorithm with state rejection. As applied to two-parameter problems, the concrete examples demonstrate the effectiveness of the algorithm with rejecting states in comparison with traditional algorithms, especially with increasing the dimension of the problem. An applied problem is considered, in the solution of which dynamic programming is used to construct recurrent formulas for calculating the optimal solution without enumerating options at all.

Keywords: Dynamic programming; Optimal trajectory (path); System state; Optimality principle; Pareto sets.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

Д. А. Карпов, В. И. Струченков (МИРЭА – Российский технологический университет, Москва, Россия) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

D. A. Karpov, V. I. Struchenkov (MIREA – Russian Technological University, Moscow, Russia) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Беллман Р. Динамическое программирование. М.: Изд-во иностр. литературы, 1960. 400 с.
2. Тахо Хедми А. Введение в исследование операций: пер. с англ. 7-е изд. М.: Вильямс, 2007. 912 с.
3. Вентцель Е. С. Исследование операций. Задачи. Принципы. Методология: учеб. пособие. 5-е изд. М.: Кнорус, 2013. 192 c.
4. Косоруков О. А., Мищенко А. В. Исследование операций: учебник. М.: Экзамен, 2013. 448 с.
5. Михалевич В. С. Последовательные алгоритмы оптимизации и их применение // Кибернетика. 1965. № 1. С. 45 – 56.
6. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования / пер. с англ. Н. М. Митрофановой и др.; под ред. А. А. Первозванского. М.: Наука; Гл. ред. физ.-мат. лит., 1965. 460 с.
7. Карпов Д. А., Струченков В. И. Сплайн-аппроксимация в проектировании трасс линейных сооружений // Вестник компьютерных и информационных технологий. 2019. № 6(180). С. 16 – 22. DOI: 10.14489/vkit.2019.06.pp.016-022
8. Лежнев А. В. Динамическое программирование в экономических задачах: учеб. пособие. М.: Бином. Лаб. знаний, 2017. 176 с.
9. Исследование операций в экономике: учеб. пособие для вузов / Н. Ш. Кремер, Б. А. Путко, И. М. Тришин, М. Н. Фридман; под ред. проф. Н. Ш. Кремера. М.: ЮНИТИ, 2005. 407 с.
10. Сигал И. Х., Иванова А. П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: учеб. пособие. М.: ФИЗМАТЛИТ, 2002. 240 с.
11. Martello S., Toth P. Knapsack Problems: Algorithms and Computer Implementation. John Willey & Sons Ltd., Chichester, England, 1990. 308 р.
12. Подиновский В. В., Ногин В. Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982. 256 с.

Eng

1. Bellman R. (1960). Dynamic programming. Moscow: Izdatel'stvo inostrannoy literatury. [in Russian language]
2. Taho Hedmi A. (2007). Introduction to Operations Research. 7th ed. Moscow: Vil'yams. [in Russian language]
3. Venttsel' E. S. (2013). Operations research. Tasks. Principles. Methodology: textbook. 5th ed. Moscow: Knorus. [in Russian language]
4. Kosorukov O. A., Mishchenko A. V. (2013). Operations research: a textbook. Moscow: Ekzamen. [in Russian language]
5. Mihalevich V. S. (1965). Sequential optimization algorithms and their application. Kibernetika, (1), pp. 45 – 56. [in Russian language]
6. Pervozvanskiy A. A. (Ed.), Bellman R., Dreyfus S. (1965). Applied Problems of Dynamic Programming. Moscow: Nauka; Glavnaya redaktsiya fiziko-matematicheskoy literatury. [in Russian language]
7. Karpov D. A., Struchenkov V. I. (2019). Spline Approximation in the Design of Alignments of Linear Structures. Vestnik komp'yuternyh i informatsionnyh tekhnologiy, 180(6), pp. 16 – 22. [in Russian language] DOI: 10.14489/vkit.2019.06.pp.016-022
8. Lezhnev A. V. (2017). Dynamic programming in economic problems: a textbook. Moscow: BINOM. Laboratoriya znaniy. [in Russian language]
9. Kremer N. Sh. (Ed.), Putko B. A., Trishin I. M., Fridman M. N. (2005). Operations Research in Economics: a textbook for universities. Moscow: YuNITI. [in Russian language]
10. Sigal I. H., Ivanova A. P. (2002). Introduction to applied discrete programming: models and computational algorithms: a textbook. Moscow: FIZMATLIT. [in Russian language]
11. Martello S., Toth P. (1990). Knapsack Problems: Algorithms and Computer Implementation. Chichester: John Wiley & Sons Ltd.
12. Podinovskiy V. V., Nogin V. D. (1982). Pareto-optimal solutions to multi-criteria problems. Moscow: Nauka. [in Russian language]

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа скопируйте doi статьи:

10.14489/vkit.2020.08.pp.003-011

и заполните форму

Отправляя форму вы даете согласие на обработку персональных данных.

Eng

This article is available in electronic format (PDF).

The cost of a single article is 350 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please copy the article doi:

10.14489/vkit.2020.08.pp.003-011

and fill out the form