Какую особенность имеет динамическое программирование как многошаговый метод оптимизации управления

Динамическое программирование: его преимущества и недостатки

Динамическое программирование – это раздел математики, который занимается методами решения многошаговых задач по оптимизации. Данный инструмент вычислений сегодня буквально незаменим во многих сферах человеческой деятельности.

Особенно он важен, когда требуется срочная оценка данных, поступивших из разных источников и значительно отличающихся как по объему, так и характеру. В подобных ситуациях динамическое программирование сложно чем-либо заменить.

Что такое динамическое программирование

Своим возникновением и утверждением в научной среде термин «динамическое программирование» обязан Ричарду Беллману, который впервые применил его в 1940 году для задач, решаемых поэтапно с использованием результатов каждого вычисления на следующем шаге. Впоследствии Беллман усовершенствовал это понятие, предложив общепринятую в настоящее время формулировку.

Сама история возникновения данного термина довольно любопытная. По словам Беллмана, когда он стал придумывать название, перед ним возникла проблема. Дело в том, что чиновник, осуществлявший над ним контроль, откровенно ненавидел математические термины и не пытался в них вникать. Весь коллектив постоянно приходил в ужас, сталкиваясь с насмешками и непониманием со стороны руководителя.

Как следствие, Беллману понадобилось немало времени, чтобы выбрать подходящее название. Вместо слова «планирование», которые вызывало ассоциации с тем, что в это время происходило в Советском Союзе, он предложил вариант «программирование».

А слово «динамическое» оказалось удачным не только потому, что передавало суть методики, но и потому, что оно было понятным и его сложно было подменить чем-либо другим. Для Беллмана было важно, чтобы его термин нельзя было неправильно интерпретировать, исказить смысл. Отсюда и возникло понятие «динамическое программирование».

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

«Более мелкие подзадачи» – это то же самое, что «более простые». Другими словами, это задачи, входные данные для которых имеют меньший размер. Входными данными могут быть число, массив, совокупность настраиваемых параметров и т.д. Как пример, можно привести последовательность чисел Фибоначчи, N-й член которой обозначается как Ф(N).

Чтобы найти пятое число Фибоначчи Ф(5), сначала нужно получить третье Ф(3) и четвертое Ф(4) числа в этой последовательности, то есть необходимо решить те самые мелкие подзадачи.

Узнай, какие ИТ — профессии
входят в ТОП-30 с доходом
от 210 000 ₽/мес
Павел Симонов
Исполнительный директор Geekbrains

Команда GeekBrains совместно с международными специалистами по развитию карьеры подготовили материалы, которые помогут вам начать путь к профессии мечты.

Подборка содержит только самые востребованные и высокооплачиваемые специальности и направления в IT-сфере. 86% наших учеников с помощью данных материалов определились с карьерной целью на ближайшее будущее!

Скачивайте и используйте уже сегодня:

Павел Симонов
Исполнительный директор Geekbrains

Топ-30 самых востребованных и высокооплачиваемых профессий 2023

Поможет разобраться в актуальной ситуации на рынке труда

Подборка 50+ бесплатных нейросетей для упрощения работы и увеличения заработка

Только проверенные нейросети с доступом из России и свободным использованием

ТОП-100 площадок для поиска работы от GeekBrains

Список проверенных ресурсов реальных вакансий с доходом от 210 000 ₽

Получить подборку бесплатно
Уже скачали 25506

В основе динамического программирования лежит выполнение следующих условий:

• Отдельные элементы должны находиться в зависимости друг от друга. Это может следовать непосредственно из условий, что наиболее характерно для задач на числовые последовательности. Если такую зависимость не удается проследить, можно попробовать найти некоторую числовую последовательность наподобие рассмотренных чисел Фибоначчи, рассчитав значения первых ее членов.
• Должны быть определены начальные значения элементов. Для этого необходимо последовательно разделять функцию на подзадачи до тех пор, пока не будут получены уже известные значения, либо функция не сведется к элементарной.

Преимущества и недостатки динамического программирования

Часто бывает так, что решить поставленную задачу быстро не получается, для этого нужно последовательно перебирать все возможные варианты. Такой подход имеет серьезный недостаток – он требует много времени.

Допустим, что хакеру нужно взломать пароль, для чего он поочередно перебирает различные комбинации символов. Если в пароле могут быть 10 цифр, по 26 больших и маленьких букв, а также 32 специальных символа, то существует 94 варианта одного символа.

То есть, если пароль состоит из одного символа, он имеет 94 возможных значения, если из двух символов, то на каждый из них приходится 24 варианта, и всего нужно 94*94 = 8836 комбинаций. Для десятизначного пароля нужно провести уже 94^10 проверок.

В наиболее общем сценарии для взлома пароля из N символов нужно перебрать 94^N комбинаций. Особенность такого подхода в том, что число попыток растет по экспоненте, то есть при увеличении длины на один знак возможных вариантов становится в 94 раза больше. Можно подумать, что взлом пароля – это условный пример, но в реальности задачи, для решения которых необходимо перебрать все варианты, встречаются повсеместно.

При возрастании по экспоненте временные затраты становятся огромными. Даже если на один элемент приходится всего несколько возможных значений, никто не станет заниматься подобными вычислениями – когда в задаче сто элементов, ее решение может занять миллиарды лет. А в действительности число элементов в задаче может быть намного больше. Именно в таких случаях возникает необходимость в динамическом программировании.

Данный метод обладает рядом преимуществ:

• Скорость. Благодаря этому динамическое программирование является эффективным. Сложнейшие задачи можно решить за максимально короткие сроки – достаточно лишь заполнить каждую ячейку таблицы.
• Универсальность. Для решения задачи любой сложности существует определенный набор правил, которые не предусматривают никаких исключений и требуют проведения минимальных расчетов.
• Точность. В процессе динамического программирования охватываются все возможные варианты событий. Это позволяет найти наиболее оптимальное решение без каких-либо погрешностей и неоднозначностей.

Для вас подарок! В свободном доступе до 14.01 —>
Скачайте ТОП-10
бесплатных нейросетей
для программирования
Помогут писать код быстрее на 25%
Чтобы получить подарок, заполните информацию в открывшемся окне

При этом у него есть и слабые стороны:

• Память. Перед тем как запустить алгоритм динамического программирования, нужно построить и заполнить таблицы, которые занимают определенный объем памяти. Возможно, что для решения задачи понадобится строить и размещать в памяти большие таблицы или множество различных таблиц.
• Когнитивная нагрузка. Безусловно, многих привлекает использование компактной системы правил для решения сложных задач. Но в то же время необходимо иметь соответствующий образ мышления, чтобы составлять подобные системы или хотя бы разбираться в них. Из-за этого динамическое программирование зачастую не пользуется большой популярностью.

Пример решения задачи при помощи динамического программирования

Теперь попробуем решить задачу с помощью динамического программирования. Допустим, что нам требуется вычислить сумму n чисел: 1 +2 +3 + … + n

Вначале данная задача может показаться непростой из-за того, что для получения ответа нужно одновременно сложить большое количество чисел. Однако можно решить ее методом динамического программирования, то есть путем разделения на подзадачи.

Динамическое программирование всегда начинается с определения начальных условий. В нашем примере достаточно взять сумму одного первого элемента, равную этому элементу: F(1) = 1

Для нахождения суммы двух элементов надо взять полученную сумму первого элемента и прибавить к ней второй элемент: F(2) = F(1) + 2 = 1 + 2 +3

Для трех элементов сумма равна F(3) = F(2) +3 = 6

Дарим скидку от 60%
на обучение «Инженер-программист» до 14 января
Уже через 9 месяцев сможете устроиться на работу с доходом от 150 000 рублей

Отсюда делаем вывод, что искомая функция имеет вид F(n) = F(n-1) + n

Другими словами, мы определили последовательность действий и выделили подзадачи, каждая из которых решалась на основе предыдущей.

Роль таблиц в динамическом программировании

Принцип динамического программирования состоит в том, что с решениями подзадач необходимо правильно обращаться, а если конкретно – одна и та же подзадача не должна решаться дважды. Все промежуточные решения нужно сохранять в отдельной базе данных . На практике для этих целей чаще всего используется таблица.

В простейшем варианте эта таблица будет представлять собой обычный массив, состоящий из одной строки. Такое динамическое программирование называется одномерным, оно занимает О(n) памяти. Например, в процессе вычисления чисел Фибоначчи лучше всего сохранять результаты отдельных вычислений в обычном массиве. Стандартный алгоритм с использованием рекурсии крайне неудобен – каждый раз приходится заново проводить вычисления, которые уже были сделаны на предыдущих этапах.

В большинстве случаев используется двумерное динамическое программирование, при котором таблицы состоят из строчек и столбиков точно также, как в Excel. Объем потребляемой памяти для таблицы из n строк и n столбцов равен О(n*n) = О(n*2). То есть, таблица в виде квадрата из 10 строк и 10 столбцов состоит из 100 ячеек.

Можно встретить и такие задачи динамического программирования, которые решаются с помощью трехмерных таблиц. Но это скорее исключение, поскольку для многих такие решения связаны с лишними затратами. Если квадратная таблица может занимать несколько мегабайт памяти, то для хранения аналогичной таблицы в форме куба потребуются гигабайты.

Только до 11.01
Скачай подборку материалов, чтобы гарантированно найти работу в IT за 14 дней
Список документов:

ТОП-100 площадок для поиска работы от GeekBrains

20 профессий 2023 года, с доходом от 150 000 рублей

Чек-лист «Как успешно пройти собеседование»

Чтобы зарегистрироваться на бесплатный интенсив и получить в подарок подборку файлов от GeekBrains, заполните информацию в открывшемся окне

Кроме исходных данных, для динамического решения задачи требуется следующее:

1. Таблица для сохранения итогов промежуточных вычислений. При завершении работы среди них будет выбран окончательный результат.
2. Набор правил, по которым заносятся данные в пустые ячейки таблицы, исходя из значений в уже заполненных ячейках. Общих рекомендаций здесь нет, для каждой задачи правила составляются индивидуально.
3. Правило, по которому из заполненной таблицы получается готовый ответ.

Использование динамического программирования в реальной жизни

Динамическое программирование нельзя назвать сугубо теоретической концепцией, используемой только учеными. Оно находит практическое применение во многих сферах деятельности, таких как прикладная информатика, машиностроение, финансовое прогнозирование. Рассмотрим некоторые типичные примеры динамического программирования.

Привлекает мир кодирования и создания программ? На курсе программиста с нуля до Junior вы освоите основы, познакомитесь с языками и инструментами разработки, и станете готовы к созданию своих первых проектов в IT-индустрии.

Довольно часто встречается задача построить маршрут через несколько заданных точек, например, в приложениях для онлайн-карт или вызова такси.

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

Аналогичная ситуация имеет место в компьютерных сетях, когда требуется доставить пакет данных по нескольким адресам. Здесь также необходимо рассчитать маршрут и определить последовательность доставки данных получателям.

Тестовые задания

функции, то двойственная — задачей минимизации целевой функции.

• 8. Критические границы ресурсов соответствуют границам устойчивости статуса ограничений
• 1) при изменении их правых частей;
• 2) при изменении коэффициентов целевой функции;
• 3) при изменении их левых частей;
• 4) это зависит от содержания задачи;
• 9. В общем случае в задачах нелинейного программирования область допустимых решений:
• 1) является выпуклой с конечным числом угловых точек;

• 2) не является выпуклой, но имеет конечное число угловых точек;
• 3) не является выпуклой и не имеет конечное число угловых точек.
• 10. В задаче оптимизации целевая функция /(.х) = 2х_х + 6х₂ — х является:
• 1) строго выпуклой;
• 2) строго вогнутой;
• 3) не строго выпуклой;
• 4) не строго вогнутой.
• 11. В нелинейном программировании выделяют два основных типа задач.
• 1) задачи выпуклого и задачи невыпуклого программирования
• 2) условной и безусловной оптимизации
• 3) однопараметрические и многопараметрические
• 4) детерминированные и недерминированные
• 12. В постановках задач нелинейного программирования предполагается, что переменные оптимизации.
• 1) непрерывны
• 2) могут принимать только положительные значения
• 3) могут принимать только целочисленные значения
• 4) разрывны
• 13. В рамках нелинейного программирования задачу оптимизации называют классической, если предполагается известной аналитическая зависимость функции.
• 1) от аргументов, а также существование обычных или частных производных до первого порядка включительно
• 2) от аргументов, а также существование обычных или частных производных до третьего порядка включительно
• 3) от аргументов, а также существование обычных или частных производных до второго порядка включительно
• 4) от аргументов
• 14. Особенностью задач нелинейного программирования, вызываемая нелинейностью функции z(X), является ее возможная.
• 1) неоднозначность
• 2) стохастичность
• 3) многоэкстремальность
• 15. По количеству локальных критериев в целевой функции методы нелинейного программирования делятся на.
• 1) сходящиеся и расходящиеся
• 2) 1-го порядка и 2-го порядка
• 3) однокритериальные и многокритериальные

• 16. Вычислительная схема метода динамического программирования:
• 1) зависит от способов задания функций;
• 2) зависит от способов задания ограничений;
• 3) связана с принципом оптимальности Веллмана.
• 17. Какую задачу можно решить методом динамического программирования:
• 1) транспортную задачу;
• 2) задачу о замене оборудования;
• 3) принятия решения в конфликтной ситуации.
• 18. Какую особенность имеет динамическое программирование как многошаговый метод оптимизации управления:
• 1) отсутствие последействия;
• 2) наличие обратной связи;
• 3) управление зависит от бесконечного числа переменных.
• 19 Процесс нахождения решений в задачах динамического программирования является.
• 1) знакопеременным;
• 2) асимптотическим;
• 3) расходящимся;
• 4) многоэтапным.
• 20. Модель транспортной задачи закрытая, если
• 1) общий объем потребления больше общего запаса перевозки;
• 2) общий объем потребления не равен общему запаса перевозки;
• 3) общий объем потребления равен общему запаса перевозки;
• 4) общий объем потребления меньше общего запаса перевозки.
• 21. При решении транспортной задачи, которая оптимизируем стоимость перевозки, значение целевой функции должно от итерации к итерации
• 1) уменьшаться или не меняться;
• 2) увеличиваться на y_ij;
• 3) увеличиваться
• 4) увеличиваться или не меняться.

/_ т п

22. В целевой функции транспортной задачи fX) = X 2 с и х у m ^ n

переменные хд — это

• 1) коэффициенты прямых затрат;
• 2) коэффициенты полных затрат;
• 3) тарифы перевозок;
• 4) объем перевозимого груза от i поставщика к j потребителю.

• 23. Целевой функции транспортной задачи, которая оптимизирует стоимость перевозки, определяет
• 1) суммарные поставки;
• 2) суммарную стоимость перевозок;
• 3) суммарные потребности;
• 4) суммарный объем перевозок.

24. В целевой функции транспортной задачи fXJ = ^ ^ с^Ху —» min

коэффициенты Сц — это

• 1) коэффициенты полных затрат;
• 2) стоимость перевозки одной тонны груза от i поставщика к j потребителю;
• 3) коэффициенты прямых затрат;
• 4) общая стоимость перевозки от i поставщика к j потребителю.
• 25. При моделировании работы склада объем партии пополнения в

классической модели формирования заказа величина_

• 1) постоянная;
• 2) любая;
• 3) переменная.
• 26. При моделировании работы склада время разгрузки прибывшей партии пополнения запасов мало, и принято считать его равным
• 1) единице;
• 2) нулю;
• 3) восьми;
• 4) пяти.
• 27. При моделировании работы склада скорость расходования запасов со склада в классической модели формирования заказа величина
• 1) любая;
• 2) постоянная;
• 3) переменная.
• 28. Система управления запасами, применяемая в модели Уилсона — это_
• 1) саморегулирующиеся системы;
• 2) система с фиксированным размером заказа;
• 3) система с фиксированной периодичностью заказа;
• 4) система с фиксированным размером заказа и с фиксированной периодичностью заказа.

29. При моделировании работы склада время от принятия решения о

пополнении до прихода заказанной партии в классической модели формирования заказа величина_.

• 1) переменная;
• 2) любая;
• 3) постоянная.
• 30. Укажите формулу для расчета оптимального размера партии
• 1) Q = h^T ;

Какую особенность имеет динамическое программирование как многошаговый метод оптимизации управления

45. Сущность метода динамического программирования.

Метод динамического программирования.

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

Общая постановка задачи динамического программирования.

— начальное состояние системы, — конечно состояние системы, U — допустимое управление системой (решение по управлению системы), Z — целевая функция .

Требуется определить допустимое управление системой U, приводящее систему из начального состояния в конечное , при котором Z достигает максимума или минимума.

Условия, которым должна удовлетворять задача, описываемая моделью динамического программирования

1. Задача должна интерпретироваться, как n-шаговый процесс управления, а показатель эффективности процесса должен быть представлен в аддитивной форме, например, как сумма показателей эффективности на любом шаге.
2. Структура задачи (или алгоритм решения) должна быть инвариантна относительно числа шагов n, т.е. должна быть определена для любого n и не зависеть от него.
3. На каждом шаге состояние системы определяется конечным числом переменных состояния и управляется конечным числом переменных уравнения.
4. Выбор управления на k-м шаге не влияет на предшествующие шаги, а состояние в начале этого шага есть функция только предшествующего состояния и выбранного на нем управления (отсутствия действия).

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

Метод динамического программирования.

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

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

Среди всех шагов существует один, который может планироваться попросту, “без оглядки на будущее”. Это последний шаг, он единственный из всех, который можно планировать так, что бы он как таковой приносил наибольшую выгоду.

Спланировав оптимальным образом этот последний шаг, можно к нему “пристраивать” предпоследний, к предпоследнему – еще один шаг и т.д.

Процесс динамического программирования всегда разворачивается в обратном по времени направлении: от конца к началу.

Принцип оптимальности Беллмана

Решение на любом шаге выбирается таким образом, чтобы обеспечить максимальную эффективность на данном шаге и на всех последовательных шагах

Основная вычислительная идея метода Беллмана

1. Решение задачи начинается с конца.

2. Исходная задача погружается во множество аналогичных задач с различными начальными вершинами и одной и той же конечной вершиной. При этом предполагается, что в качестве начальной вершины полностью выступает все без исключения вершины графа.

Порядок решения задач динамического программирования

Решение задач динамического программирования обычно включает два цикла

1. от последнего шага к первому (обратная прогонка, или условная оптимизация)

2. от первого шага к последнему (прямая прогонка, или безусловная оптимизация)

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

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

apt.ru

Timeweb — компания, которая размещает проекты клиентов в Интернете, регистрирует адреса сайтов и предоставляет аренду виртуальных и физических серверов. Разместите свой сайт в Сети — расскажите миру о себе!

Виртуальный хостинг

Быстрая загрузка вашего сайта, бесплатное доменное имя, SSL-сертификат и почта. Первоклассная круглосуточная поддержка.

от 196 руб руб. / мес

Аренда VDS и VPS

Виртуальные серверы с почасовой оплатой. Меняйте конфигурацию сервера в любой момент и в пару кликов.