Preview

Russian Technological Journal

Расширенный поиск

Динамическое программирование в прикладных задачах, допускающих сокращение перебора вариантов

https://doi.org/10.32362/2500-316X-2020-8-4-96-111

Полный текст:

Аннотация

В статье рассматривается разработанный Р. Беллманом алгоритм динамического программирования, основанный на поиске оптимальной траектории, соединяющей узлы предварительно заданной регулярной сетки состояний. Анализируются возможности резкого повышения эффективности применения динамического программирования при решении прикладных задач, обладающих специфическими особенностями, что позволяет отказаться от разбиения регулярной сетки состояний и реализовать алгоритм поиска оптимальной траектории при отбраковке не только бесперспективных вариантов путей, приводящих в каждое из состояний, и всех их продолжений, как в алгоритме Р. Беллмана, но и собственно бесперспективных состояний и всех вариантов исходящих из них путей. Сформулированы и обоснованы условия, при которых возможна отбраковка бесперспективных состояний. Установлено, что многие прикладные задачи удовлетворяют этим условиям. Для решения подобных задач предложен и реализован новый алгоритм динамического программирования. Приводятся конкретные примеры таких прикладных задач: оптимальное распределение однородного ресурса между несколькими потребителями, оптимальная загрузка транспортных средств, оптимальное распределение финансов при выборе инвестиционных проектов. Для решения этих задач ранее предлагались алгоритмы динамического программирования с отбраковкой бесперспективных путей, но без отбраковки состояний. Число бесперспективных состояний, появляющихся на различных этапах динамического программирования, и, соответственно, эффективность нового алгоритма, зависит от конкретных числовых значений исходных данных. Для двухпараметрической задачи оптимальной загрузки транспортных средств при ограничении по весу и объёму приведены результаты сопоставительных расчётов по алгоритму Р. Беллмана и по новому алгоритму динамического программирования. В качестве исходных данных для серии расчётов использовались псевдослучайные числа. В результате анализа показано, что сравнительная эффективность алгоритма с отбраковкой состояний растёт при увеличении размерности задачи. Так в задаче оптимального выбора предметов для загрузки транспортного средства заданной грузоподъёмности при числе предметов 150 количество запоминаемых состояний и время счёта снижаются в 50 и 57 раз, соответственно, при использовании нового алгоритма по сравнению с классическим алгоритмом Р. Беллмана. Для 15 предметов соответствующие числа равны 13 и 4.

Для цитирования:


Карпов Д.А., Струченков В.И. Динамическое программирование в прикладных задачах, допускающих сокращение перебора вариантов. Russian Technological Journal. 2020;8(4):96-111. https://doi.org/10.32362/2500-316X-2020-8-4-96-111

For citation:


Karpov D.A., Struchenkov V.I. Dynamic programming in applied tasks which are allowing to reduce the options selection. Russian Technological Journal. 2020;8(4):96-111. (In Russ.) https://doi.org/10.32362/2500-316X-2020-8-4-96-111

Просмотров: 1479


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2782-3210 (Print)
ISSN 2500-316X (Online)