Letysite.ru

IT Новости с интернет пространства
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Лекции динамическое программирование

Динамическое программирование для начинающих

    Статьи, 7 июня 2016 в 15:04

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

О чём вообще речь? Что такое динамическое программирование?

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

Хорошо, как это использовать?

Решение задачи динамическим программированием должно содержать следующее:

  • Зависимость элементов динамики друг от друга. Такая зависимость может быть прямо дана в условии (так часто бывает, если это задача на числовые последовательности). В противном случае вы можете попытаться узнать какой-то известный числовой ряд (вроде тех же чисел Фибоначчи), вычислив первые несколько значений вручную. Если вам совсем не повезло – придётся думать
  • Значение начальных состояний. В результате долгого разбиения на подзадачи вам необходимо свести функцию либо к уже известным значениям (как в случае с Фибоначчи — заранее определены первые два члена), либо к задаче, решаемой элементарно.

И что, мне для решения рекурсивный метод писать надо? Я слышал, они медленные.

Конечно, не надо, есть и другие подходы к реализации динамики. Разберём их на примере следующей задачи:

Идея решения

Здесь нам даны и начальные состояния (a = a1 = 1), и зависимости. Единственная сложность, которая может возникнуть — понимание того, что 2n — условие чётности числа, а 2n+1 — нечётности. Иными словами, нам нужно проверять, чётно ли число, и считать его в зависимости от этого по разным формулам.

Рекурсивное решение

Очевидная реализация состоит в написании следующего метода:

И она отлично работает, но есть нюансы. Если мы захотим вычислить f(12) , то метод будет вычислять сумму f(6)+f(5) . В то же время, f(6)=f(3)+f(2) и f(5)=f(2)-f(1) , т.е. значение f(2) мы будем вычислять дважды. Спасение от этого есть — мемоизация (кеширование значений).

Рекурсивное решение с кэшированием значений

Идея мемоизации очень проста — единожды вычисляя значение, мы заносим его в какую-то структуру данных. Перед каждым вычислением мы проверяем, есть ли вычисляемое значение в этой структуре, и если есть, используем его. В качестве структуры данных можно использовать массив, заполненный флаговыми значениями. Если значение элемента по индексу N равно значению флага, значит, мы его ещё не вычисляли. Это создаёт определённые трудности, т.к. значение флага не должно принадлежать множеству значений функции, которое не всегда очевидно. Лично я предпочитаю использовать хэш-таблицу — все действия в ней выполняются за O(1), что очень удобно. Однако, при большом количестве значений два числа могут иметь одинаковый хэш, что, естественно, порождает проблемы. В таком случае стоит использовать, например, красно-чёрное дерево.

Для уже написанной функции f(int) кэширование значений будет выглядеть следующим образом:

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

Последовательное вычисление

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

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

LATOKEN, Москва, от 200 000 до 360 000 ₽

Суть метода в следующем: мы создаём массив на N элементов и последовательно заполняем его значениями. Вы, наверное, уже догадались, что таким образом мы можем вычислять в том числе те значения, которые для ответа не нужны. В значительной части задач на динамику этот факт можно опустить, так как для ответа часто бывают нужны как раз все значения. Например, при поиске наименьшего пути мы не можем не вычислять путь до какой-то точки, нам нужно пересмотреть все варианты. Но в нашей задаче нам нужно вычислять приблизительно log2(N) значений (на практике больше), для 922337203685477580-го элемента (MaxLong/10) нам потребуется 172 вычисления.

Ещё одним минусом такого подхода является сравнительно большой расход памяти.

Создание стека индексов

Сейчас нам предстоит, по сути, написать свою собственную рекурсию. Идея состоит в следующем — сначала мы проходим «вниз» от N до начальных состояний, запоминая аргументы, функцию от которых нам нужно будет вычислять. Затем возвращаемся «вверх», последовательно вычисляя значения от этих аргументов, в том порядке, который мы записали.

Зависимости вычисляются следующим образом:

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

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

Все необходимые значения вычислены, осталось только написать

Конечно, такое решение гораздо более трудоёмкое, однако это того стоит.

Хорошо, математика — это красиво. А что с задачами, в которых не всё дано?

Для больше ясности разберём следующую задачу на одномерную динамику:

На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных «маршрутов» мячика с вершины на землю.

Идея решения

На первую ступеньку можно попасть только одним образом — сделав прыжок с длиной равной единице. На вторую ступеньку можно попасть сделав прыжок длиной 2, или с первой ступеньки — всего 2 варианта. На третью ступеньку можно попасть сделав прыжок длиной три, с первой или со втрой ступенек. Т.е. всего 4 варианта (0->3; 0->1->3; 0->2->3; 0->1->2->3). Теперь рассмотрим четвёртую ступеньку. На неё можно попасть с первой ступеньки — по одному маршруту на каждый маршрут до неё, со второй или с третьей — аналогично. Иными словами, количество путей до 4-й ступеньки есть сумма маршрутов до 1-й, 2-й и 3-й ступенек. Математически выражаясь, F(N) = F(N-1)+F(N-2)+F(N-3). Первые три ступеньки будем считать начальными состояниями.

Реализация через рекурсию

Здесь ничего хитрого нет.

Реализация через массив значений

Исходя из того, что, по большому счёту, простое решение на массиве из N элементов очевидно, я продемонстрирую тут решение на массиве всего из трёх.

Так как каждое следующее значение зависит только от трёх предыдущих, ни одно значение под индексом меньше i-3 нам бы не пригодилось. В приведённом выше коде мы записываем новое значение на место самого старого, не нужного больше. Цикличность остатка от деления на 3 помогает нам избежать кучи условных операторов. Просто, компактно, элегантно.

Там вверху ещё было написано про какую-то двумерную динамику.

С двумерной динамикой не связано никаких особенностей, однако я, на всякий случай, рассмотрю здесь одну задачу и на неё.

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

Идея решения

Логика решения полностью идентична таковой в задаче про мячик и лестницу — только теперь в клетку (x,y) можно попасть из клеток (x-1,y) или (x, y-1). Итого F(x,y) = F(x-1, y)+F(x,y-1). Дополнительно можно понять, что все клетки вида (1,y) и (x,1) имеют только один маршрут — по прямой вниз или по прямой вправо.

Реализация через рекурсию

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

Реализация через массив значений

Классическое решение динамикой, ничего необычного — проверяем, является ли клетка краем, и задаём её значение на основе соседних клеток.

Отлично, я всё понял. На чём мне проверить свои навыки?

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

Взрывоопасность

При переработке радиоактивных материалов образуются отходы двух видов — особо опасные (тип A) и неопасные (тип B). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Стопка считается безопасной, если она не является взрывоопасной. Для заданного количества контейнеров N определить количество возможных типов безопасных стопок.

Решение

Ответом является (N+1)-е число Фибоначчи. Догадаться можно было, просто вычислив 2-3 первых значения. Строго доказать можно было, построив дерево возможных построений.

Каждый основной элемент делится на два — основной (заканчивается на B) и побочный (заканчивается на A). Побочные элементы превращаются в основные за одну итерацию (к последовательности, заканчивающейся на A, можно дописать только B). Это характерно для чисел Фибоначчи.

Реализация

Подъём по лестнице

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

Читать еще:  Компонентный подход в программировании
Решение

Очевидно, что сумма, которую мальчик отдаст на N-ой ступеньке, есть сумма, которую он отдал до этого плюс стоимость самой ступеньки. «Сумма, которую он отдал до этого» зависит от того, с какой ступеньки мальчик шагает на N-ую — с (N-1)-й или с (N-2)-й. Выбирать нужно наименьшую.

Реализация

Калькулятор

Имеется калькулятор, который выполняет три операции:

  • Прибавить к числу X единицу;
  • Умножить число X на 2;
  • Умножить число X на 3.

Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N. Выведите это число, и, на следующей строке, набор исполненных операций вида «111231».

Решение

Наивное решение состоит в том, чтобы делить число на 3, пока это возможно, иначе на 2, если это возможно, иначе вычитать единицу, и так до тех пор, пока оно не обратится в единицу. Это неверное решение, т.к. оно исключает, например, возможность убавить число на единицу, а затем разделить на три, из-за чего на больших числах (например, 32718) возникают ошибки.

Правильное решение заключается в нахождении для каждого числа от 2 до N минимального количества действий на основе предыдущих элементов, иначе говоря: F(N) = min(F(N-1), F(N/2), F(N/3)) + 1. Следует помнить, что все индексы должны быть целыми.

Для воссоздания списка действий необходимо идти в обратном направлении и искать такой индекс i, что F(i)=F(N), где N — номер рассматриваемого элемента. Если i=N-1, записываем в начало строки 1, если i=N/2 — двойку, иначе — тройку.

Реализация

Самый дешёвый путь

В каждой клетке прямоугольной таблицы N*M записано некоторое число. Изначально игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько килограммов еды, какое число записано в этой клетке (еду берут также за первую и последнюю клетки его пути).

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

Решение

В любую клетку таблицы мы можем попасть либо из клетки, находящейся непосредственно над ней, либо из клетки, находящейся непосредственно слева. Таким образом, F(x,y) = min(F(x-1,y), F(x,y-1)). Чтобы не обрабатывать граничные случаи, можно добавить первую строку и столбец, заполненные некоторой константой — каким-то числом, заведомо большим содержимого любой из клеток.

Лекция 26 Динамическое программирование

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

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

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

С помощью динамического программирования решаются задачи, связанные с процессами, которые можно разделить на некоторое число этапов (шагов). Оптимизация управления на каждом этапе в отдельности не обеспечивает ещё оптимизации процесса в целом.

Алгоритм реализации метода построен на разделение общей задачи на отдельные этапы.

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

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

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

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

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

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

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

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

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

Для знакомства с методиками приведём примеры решения задач.

Рассмотрим пример геометрической интерпретации (рис.18.1) метода (источник информации [3]) Смысл её состоит в следующем.

Рис. 18.1. Геометрическая интерпретация задачи

Вертикальным линиям соответствуют моменты времени, в которые рассматривают исследуемую задачу.

В начальный момент t = 0 процесс (система) находится в одном из возможных начальных состояний, множеству которых соответствует множество точек Аi .Начальное состояние может быть задано либо областью возможных состояний, либо одним конкретным значением, в нашем случае четырьмя А1 А2 А3 и А4 . Будем также считать, для простоты, что в каждый момент времени система находится так же в одном из четырех возможных состояний, которые показаны точками на соответствующих вертикалях.

Конечное состояние системы — одна из четырех точек В1 В2 В3 и В4

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

Эта функция — количественная характеристика перехода в следующее состояние в зависимости от предыдущего — выражает либо выигрыш, либо затраты. Поскольку значение функции перехода зависит от предыдущего х(i) и от последующего х (i + 1) состояний системы, ее можно записать в общем случае так:

Каждая допустимая стратегия выражается ломаной линией, соединяющей вертикаль t= 0 с вертикалью tn = Т.

Состоит она из набора управлений на каждом этапе, т. е. ей можно сопоставить число:

Оптимальной стратегии соответствует ломаная с наименьшим значением F.

Следовательно, исходную задачу можно сформулировать в следующем виде: требуется из всех допустимых ломаных, соединяющих вертикаль t0= c вертикалью tn = T выбрать такую, которой соответствует наименьшее значение F.

Решают задачу в таком порядке.

Для всех возможных состояний системы в начале последнего этапа х(n — 1) определяют оптимальное управление — выбирают функцию перехода в одно из

конечных состояний с минимальным значением. Переходы, соответствующие минимальному значению Qn-1 для каждого состояния (n — 1),показаны на рис. 18.1 жирной линией. Таким образом, в какой бы точке не оказалась система в начале последнего этапа, всегда можно предложить оптимальную стратегию для перевода ее в конечное состояние, получить ряд условно-оптимальных решений. Условие оптимальности каждого такого решения — состояние системы в начале рассматриваемого периода.

Теперь для каждого состояния системы в начале предпоследнего этапа Х(n-2)можно определить условно-оптимальные стратегии для перевода в одно из конечных состояний уже по общему минимуму функций перехода на двух последних этапах: min

При этом значения Qn-1 уже известны в результате предыдущих вычислений. Затем аналогично определяют условно-оптимальные стратегии на трех последних этапах по условию min(Qn-2 + Qn-1), причем Qn-1 уже известна. Расчеты продолжают до тех пор, пока не будет пройден весь процесс в обратном направлении.

Каждая из полученных ломаных (жирная линия), соответствует условно-оптимальной стратегии для всего процесса. Поскольку множеству начальных состояний системы соответствует множество точек на вертикали, то каждой условно-оптимальной стратегии соответствует свое начальное состояние системы (точка, из которой она выходит). Таким образом, условно-оптимальная стратегия будет оптимальной, при условии, что начальное состояние системы находится в соответствующей точке. Каждая условно-оптимальная стратегия оценивается значением функции F:

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

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

Математическая постановка задачи выглядит следующим образом.

В качестве примера реализации методики динамического программирования можно привести решение задачи по оптимизации режима ведения поезда на одном из участков (рис. 18.2.).

Рис. 18.2 Определение наивыгоднейшего режима ведения поезда по участку

Лекции динамическое программирование

1. Какие основные принципы заложены в методе?

2. Как он применяется при решении задач?

… Математик может считать свою проблему

решенной тогда, только когда поймет суть

оптимального подхода к решению

(Р. Беллман)

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

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

8.1 Суть метода динамического программирования и его особенности

Суть метода динамического программирования (ДП) заключается в следующем.

Задача погружается в семейство задач той же природы. Другими словами, разбивается на зависимые (могут пересекаться) подзадачи.

Каждая подзадача решается отдельно один раз. Оптимальные значения решений всех подзадач запоминаются.

Читать еще:  Не работает безопасный режим

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

Таким образом, основные отличия данной техники от техники «разделяй и властвуй «заключаются в следующем:

Таблица 8.1 — Отличительные особенности методов «разделяй и властвуй» и ДП.

Разделяй и властвуй

Не зависимые подзадачи

Решение всех подзадач не запоминается

Решение всех подзадач запоминается

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

Показатель эффективности задачи в целом обозначим через W, а показатели эффективности на отдельных шагах—через φi, i=1..m. Если W обладает свойством аддитивности, т.е.

Переменная xi, от которой зависят выигрыши на i-м шаге и, следовательно, выигрыш в целом, называется шаговым управлением, i=1..m.

Управлением процесса в целом (x) называется последовательность шаговых управлений (вектор управлений) x = (x1, x2,…, xi,…, xm).

Оптимальное управление x* — это значение управления x, при котором значение W(x*) является максимальным (или минимальным, если требуется уменьшить проигрыш).

где X—область допустимых управлений.

Оптимальное управление x* определяется последовательностью оптимальных шаговых управлений x*=(x1*, x2*,…, xi*,…, xm*).

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

Можно определить следующие основные этапы составления математической модели задачи динамического программирования.

  1. Разбиение задачи на шаги (этапы). Шаг не должен быть слишком мелким, чтобы не проводить лишних расчетов и не должен быть слишком большим, усложняющим процесс шаговой оптимизации.
  2. Выбор переменных, характеризующих состояние s моделируемого процесса перед каждым шагом, и выявление налагаемых на них ограничений. В качестве таких переменных следует брать факторы, представляющие интерес для исследователя, например годовую прибыль при планировании деятельности предприятия.
  3. Определение множества шаговых управлений xi, i=1..m и налагаемых на них ограничений, т.е. области допустимых управлений X.
  4. Определение выигрыша φ(s, xi), который принесет на i-м шаге управление xi, если система перед этим находилась в состоянии s.
  5. Определение состояния s’, в которое переходит система из состояния s под влиянием управления xi : s’=fi(s, xi), где fi—функция перехода на i-м шаге из состояния s в состояние s’.
  6. Составление уравнения, определяющего условный оптимальный выигрыш на последнем шаге, для состояния s моделируемого процесса
  • (8.3) [TEX]rm Wm(S)=max[/TEX]

7. Составление основного функционального уравнения динамического программирования, определяющего условный оптимальный выигрыш для данного состояния s с i-го шага и до конца процесса через уже известный оптимальный выигрыш с (i+1)-го шага и до конца:

В уравнении (8.4) в уже известную функцию Wi+1(s), характеризующую условный оптимальный выигрыш с (i+1)-го шага до конца процесса, вместо состояния s подставлено новое состояние s’=fi(s, xi), в которое система переходит на i-м шаге под влиянием управления xi.

После того как выполнены пункты 1-7, и математическая модель составлена, приступают к ее расчету. Укажем основные этапы решения задачи динамического программирования.

  1. Определение множества возможных состояний Sm для последнего шага.
  2. Проведение условной оптимизации для каждого состояния s, принадлежащей Sm на последнем m-м шаге по формуле (8.3) и определение условного оптимального управления x(s), s принадлежит Sm.
  3. Определение множества возможных состояний Si для i-го шага, i=2, 3,…m-1.
  4. Проведение условной оптимизации для i-го шага, i=2, 3,…m-1 для каждого состояния s, принадлежащей Si,, по формуле (8.4) и определение условного оптимального управления xi(s), s принадлежит Si, i=2, 3,…m-1.
  5. Определение начального состояния системы s1, оптимального выигрыша W1(S1) и оптимального управления x1(S1) по формуле (8.4) при i=1. Это есть оптимальный выигрыш для всей задачи W*=W1(x1*).
  6. Проведение безусловной оптимизации управления. Для проведения безусловной оптимизации необходимо найденное на первом шаге оптимальное управление x1*=x1(s1) подставить в формулу (8.2) и определить следующее состояние системы s2=f2(s1, x1). Для измененного состояния найти оптимальное управление x2*=x2(s2), подставить в формулу и т.д. Для i-го состояния si найти si+1=fi+1(si,xi*) и x*i+1(si+1) и т.д.
  7. Динамическое программирование дает достаточно эффективный метод последовательного принятия решений об оптимизации работы системы с помощью решения серии связанных между собой одношаговых задач Это позволяет говорить о многошаговом процессе принятия решения . Таким способом могут быть оптимизированы динамические системы , для которых фактор времени играет существенную роль . Однако специфичный способ решения задач динамического программирования , который оперирует рекуррентными соотношениями , позволяет оптимизировать не только реальные динамические системы .

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

Перечислим основные требования к задачам, выполнение которых позволяет применить данный подход:

а) объектом исследования должна cлужить управляемая систем а(объект) с заданными допустимыми состояниями и допустимыми управлениями;

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

в) задача не должна зависеть от количества шагов и быть определенной на каждом из них ;

г) состояние системы на каждом шаге должно описываться одинаковым ( по составу ) набором параметров;

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

Одной из наиболее известных сфер приложения методов динамического программирования является такая область математической экономики как теория управления запасами. Ее предметом является разработка и исследование математических моделей систем, занимающих промежуточное положение между источниками ( производителями ) тех или иных ресурсов и их потребителями. К динамическим задачам управления запасами относятся: задача поиска оптимального маршрута доставки товара, задача оптимального обеспечения спроса потребителей на некоторый продукт на n периодов, задача оптимального распределения средств на реконструкцию и модернизацию между несколькими объектами и другие задачи.

8.2 Применение метода в конкретных задачах

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

Задача 8.1 Задача о возврате сдачи. Необходимо вернуть сдачу покупателю 10 грн. Сколько способов существует для возврата сдачи, если у продавца имеется неограниченные количества разменных монет достоинством 1, 2 и 5 грн. ? При этом способы различаются и порядком следования монет, т.е. сдача набором монет <1, 2, 2, 5>и сдача — <5, 2, 2, 1>– это разные способы.

Решение. Введем обозначения F(n) – количество способов, которыми можно вернуть сдачу достоинством n. Тогда в задаче требуется найти F(10).

Перейдем к задачам меньшей размерности. Рассмотрим случаи, когда n=1, n=2, n=3, n=4 и даже n=0. Эти задачи меньшей размерности решим методом перебора, результат приведем в таблице 8.2.

Таблица 8.2 Решение подзадач к задаче 8.1 для n

Урок 50
Динамическое программирование
(§45. Динамическое программирование)

Содержание урока

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

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

Мы уже встречались с последовательностью чисел Фибоначчи (см. учебник для 10 класса):

Для их вычисления можно использовать рекурсивную функцию:

Каждое из этих чисел связано с предыдущими, вычисление Fa приводит к рекурсивным вызовам, которые показаны на рис. 6.35. Таким образом, мы два раза вычислили F3, три раза — F2 и два раза — F1 Рекурсивное решение очень простое, но оно неоптимально по быстродействию: компьютер выполняет лишнюю работу, повторно вычисляя уже найденные ранее значения.

Рис. 6.35

Где же выход? Например, можно хранить все предыдущие числа Фибоначчи в массиве. Пусть этот массив называется F:

Тогда для вычисления всех чисел Фибоначчи от Fx до FN можно использовать цикл:

Динамическое программирование — это способ решения сложных задач путем сведения их к более простым подзадачам того же типа.

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

Например, пусть нужно перейти из пункта А в пункт Е через один из пунктов В, С или D (на рис. 6.36 числами обозначена «стоимость» маршрута).

Рис. 6.36

Пусть уже известны оптимальные маршруты из пунктов В, С и D в пункт Е (они обозначены сплошными линиями) и их «стоимость». Тогда для нахождения оптимального маршрута из А в Е нужно выбрать вариант, который даст минимальную стоимость по сумме двух шагов. В данном случае это маршрут А-В-Е, стоимость которого равна 25. Как видим, такие задачи решаются «с конца», т. е. решение начинается от конечного пункта.

В информатике динамическое программирование часто сводится к тому, что мы храним в памяти решения всех задач меньшей размерности. За счёт этого удаётся ускорить выполнение программы. Например, на одном и том же компьютере вычисление F45 с помощью рекурсивной функции требует около 8 секунд, а с использованием массива — менее 0,01 с.

Заметим, что в данной простейшей задаче можно обойтись вообще без массива:

Задача 1. Найти количество KN цепочек, состоящих из N нулей и единиц, в которых нет двух стоящих подряд единиц.

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

1) выразить KN через предыдущие значения последовательности K1, K2, . KN-1;

2) выделить массив для хранения всех предыдущих значений Кi (i = 1, . N- 1).

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

Рис. 6.37

Поскольку дополнительный O не может привести к появлению двух соседних единиц, подходящих последовательностей длины N с нулём в начале существует столько, сколько подходящих последовательностей длины N — 1, т. е. KN-1 Если же первый символ — это 1, то вторым обязательно должен быть 0, а остальная цепочка из N — 2 битов должна быть правильной, без двух соседних единиц (рис. 6.38). Поэтому подходящих последовательностей длиной N с единицей в начале существует столько, сколько подходящих последовательностей длины N — 2, т. е. KN-2.

Рис. 6.38

В результате получаем: KN = KN-1 + KN-2. Значит, для вычисления очередного числа нам нужно знать два предыдущих.

Теперь рассмотрим простые случаи. Очевидно, что есть две последовательности длины 1 (0 и 1), т. е. К1 = 2. Далее, есть 3 подходящих последовательности длины 2 (00, 01 и 10), поэтому К2 = 3. Легко понять, что решение нашей задачи — число Фибоначчи: KN = Fn+2.

Следующая страница Поиск оптимального решения

Cкачать материалы урока

Лекции динамическое программирование

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

Что такое компьютерная программа?

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

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

  • Последовательность инструкций
  • Язык компьютерного программирования

Чтобы понять значение этих терминов, представьте ситуацию, в которой кто-то обращается к вам с просьбой объяснить, где находится ближайшее кафе McDonald’s. Как вы будете объяснять дорогу в кафе?

Используя естественный язык, вы скажете что-то наподобие:

Сначала поезжайте прямо, через полкилометра на светофоре поверните налево, через километр по правой стороне вы увидите кафе McDonald’s.

В данном случае, используя русский язык, вы перечислили действия, которые позволят добраться до кафе. Найти кафе можно только в случае, если действия будут выполнены в такой последовательности:

2. Проехать полкилометра

3. Повернуть налево

4. Проехать около километра

5. Найти McDonald’s на правой стороне дороги

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

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

Что такое программирование?

Если вы поняли, что такое компьютерная программа, то процесс написания компьютерных программ и называется компьютерным программированием.

Существуют сотни языков программирования, которые применяются для написания компьютерных программ, и вот некоторые из них:

Что такое алгоритм?

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

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

Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой ( англ. ), выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.

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

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

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

Оптимальная подструктура в динамическом программировании означает, что оптимальное решение подзадач меньшего размера может быть использовано для решения исходной задачи. К примеру, кратчайший путь в графе из одной вершины (обозначим s) в другую (обозначим t) может быть найден так: сначала считаем кратчайший путь из всех вершин, смежных с s, до t, а затем, учитывая веса ребер, которыми s соединена со смежными вершинами, выбираем лучший путь до t (через какую вершину лучше всего пойти). В общем случае мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага.

1. Разбиение задачи на подзадачи меньшего размера.

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

3. Использование полученного решения подзадач для конструирования решения исходной задачи.

Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1).

Перекрывающиеся подзадачи в динамическом программировании означают подзадачи, которые используются для решения некоторого количества задач (не одной) большего размера (то есть мы несколько раз проделываем одно и то же). Ярким примером является вычисление последовательности Фибоначчи , и — даже в таком тривиальном случае вычисления всего двух чисел Фибоначчи мы уже посчитали дважды. Если продолжать дальше и посчитать , то посчитается ещё два раза, так как для вычисления будут нужны опять и . Получается следующее: простой рекурсивный подход будет расходовать время на вычисление решения для задач, которые он уже решал.

Чтобы избежать такого хода событий мы будем сохранять решения подзадач, которые мы уже решали, и когда нам снова потребуется решение подзадачи, мы вместо того, чтобы вычислять его заново, просто достанем его из памяти. Этот подход называется мемоизацией . Можно проделывать и дальнейшие оптимизации — например, если мы точно уверены, что решение подзадачи нам больше не потребуется, можно выкинуть его из памяти, освободив её для других нужд, или если процессор простаивает и мы знаем, что решение некоторых, ещё не посчитанных подзадач, нам понадобится в дальнейшем, мы можем решить их заранее.

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

· возможность запоминания решения часто встречающихся подзадач.

Динамическое программирование обычно придерживается двух подходов к решению задач:

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

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

Существует три порядка пересчёта:
1) Прямой порядок:
Состояния последовательно пересчитывается исходя из уже посчитанных.

2) Обратный порядок:
Обновляются все состояния, зависящие от текущего состояния.

3) Ленивая динамика:
Рекурсивная мемоизированная функция пересчёта динамики. Это что-то вроде поиска в глубину по ацикличному графу состояний, где рёбра — это зависимости между ними.

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

Языки программирования могут запоминать результат вызова функции с определенным набором аргументов ( мемоизация ), чтобы ускорить «вычисление по имени». В некоторых языках такая возможность встроена (например, Scheme , Common Lisp , Perl ), а в некоторых требует дополнительных расширений ( C++ ).

Известны сериальное динамическое программирование, включённое во все учебники по исследованию операций , и несериальное динамическое программирование (НСДП), которое в настоящее время слабо известно, хотя было открыто в 1960-х годах.

Обычное динамическое программирование является частным случаем несериального динамического программирования, когда граф взаимосвязей переменных — просто путь. НСДП, являясь естественным и общим методом для учета структуры задачи оптимизации, рассматривает множество ограничений и/или целевую функцию как рекурсивно вычислимую функцию. Это позволяет находить решение поэтапно, на каждом из этапов используя информацию, полученную на предыдущих этапах, причём эффективность этого алгоритма прямо зависит от структуры графа взаимосвязей переменных. Если этот граф достаточно разрежен, то объём вычислений на каждом этапе может сохраняться в разумных пределах.

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

Ссылка на основную публикацию
Adblock
detector