Динамическое программирование в экономике кратко

Обновлено: 04.07.2024

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

Рассмотрим общее описание задачи динамического программирования.
Пусть многошаговый процесс принятия решений разбивается на n шагов. Обозначим через ε 0 – начальное состояние системы, через ε 1 , ε 2 , … ε n – состояния системы после первого, второго, n-го шага. В общем случае состояние ε k – вектор (ε k ₁, …, ε k _s).
Управлением в многошаговом процессе называется совокупность решений (управляющих переменных) u k = (u k ₁, . u k _r), принимаемых на каждом шаге k и переводящих систему из состояния ε k -1 = (ε k- 1 ₁, …, ε k -1 _s) в состояние ε k = (ε k ₁, …, ε k _s).
В экономических процессах управление заключается в распределении и перераспределении средств на каждом этапе. Например, выпуск продукции любым предприятием – управляемый процесс, так как он определяется изменением состава оборудования, объемом поставок сырья, величиной финансирования и т. д. Совокупность решений, принимаемых в начале года, планируемого периода, по обеспечению предприятия сырьем, замене оборудования, размерам финансирования и т. д. является управлением. Казалось бы, для получения максимального объема выпускаемой продукции проще всего вложить максимально возможное количество средств и использовать на полную мощность оборудование. Но это привело бы к быстрому изнашиванию оборудования и, как следствие, к уменьшению выпуска продукции. Следовательно, выпуск продукции надо спланировать так, чтобы избежать нежелательных эффектов. Необходимо предусмотреть мероприятия, обеспечивающие пополнение оборудования по мере изнашивания, т. е. по периодам времени. Последнее хотя и приводит к уменьшению первоначального объема выпускаемой продукции, но обеспечивает в дальнейшем возможность расширения производства. Таким образом, экономический процесс выпуска продукции можно считать состоящим из нескольких этапов (шагов), на каждом из которых осуществляется влияние на его развитие.
Началом этапа (шага) управляемого процесса считается момент принятия решения (о величине капитальных вложений, о замене оборудования определенного вида и т. д.). Под этапом обычно понимают хозяйственный год.
Обычно на управление на каждом шаге u k накладываются некоторые ограничения. Управления, удовлетворяющие этим ограничениям, называются допустимыми.
Предполагая, что показатель эффективности k-го шага процесса зависит от начального состояния на этом шаге k -1 и от управления на этом шаге u k , получим целевую функцию всего многошагового процесса в виде:
.

Я был крайне удивлён, найдя мало статей про динамическое программирование (далее просто динамика) на хабре. Мне всегда казалось, что эта парадигма довольно сильно распространена, в том числе и за пределами олимпиад по программированию. Поэтому я постараюсь закрыть этот пробел своей статьёй.

Основы

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

Динамическое программирование — это когда у нас есть задача, которую непонятно как решать, и мы разбиваем ее на меньшие задачи, которые тоже непонятно как решать. (с) А. Кумок.

Чтобы успешно решить задачу динамикой нужно:
1) Состояние динамики: параметр(ы), однозначно задающие подзадачу.
2) Значения начальных состояний.
3) Переходы между состояниями: формула пересчёта.
4) Порядок пересчёта.
5) Положение ответа на задачу: иногда это сумма или, например, максимум из значений нескольких состояний.

Порядок пересчёта

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

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

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

Элементарный пример: числа Фибоначчи. Состояние — номер числа.

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

Многомерная динамика

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

Пример №1: Количество СМСок

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

Прямой пересчёт:
Обратный пересчёт:

4) Порядок пересчёта:
Если писать прямым методом, то надо отдельно подумать о выходе за границу динамики, к примеру, когда мы обращаемся к dp[n - 1][m - 4] , которого может не существовать при малых m . Для обхода этого можно или ставить проверки в пересчёте или записать туда нейтральные элементы (не изменяющие ответа).

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

5) Ответ — это сумма всех состояний.

Пример №2: Конь

Шахматный конь стоит в клетке (1, 1) на доске размера N x M . Требуется подсчитать количество способов добраться до клетки (N, M) передвигаясь четырьмя типами шагов:

1) Состояние динамики: dp[i][j] — количество способов добраться до (i, j) .
2) Начальное значение: В клетку (1, 1) можно добраться одним способом — ничего не делать.
3) Формула пересчёта:
Для прямого порядка:
Для обратного порядка:

4) А теперь самое интересное в этой задаче: порядок. Здесь нельзя просто взять и пройтись по строкам или по столбцам. Потому что иначе мы будем обращаться к ещё не пересчитанным состояниям при прямом порядке, и будем брать ещё недоделанные состояния при обратном подходе.

Есть два пути:
1) Придумать хороший обход.
2) Запустить ленивую динамику, пусть сама разберётся.

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

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

5) Ответ просто лежит в dp[n][m] .

Динамика и матрица переходов

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

Допустим, есть задача, которую мы уже решили динамическим программированием, например, извечные числа Фибоначчи.
Давайте немного переформулируем её. Пусть у нас есть вектор , из которого мы хотим получить вектор . Чуть-чуть раскроем формулы: . Можно заметить, что из вектора можно получить вектор путем умножения на какую-то матрицу, ведь в итоговом векторе фигурируют только сложенные переменные из первого вектора. Эту матрицу легко вывести, вот она: . Назовём её матрицей перехода.

Это значит, что если взять вектор и умножить его на матрицу перехода n - 1 раз, то получим вектор , в котором лежит fib[n] — ответ на задачу.

А теперь, зачем всё это надо. Умножение матриц обладает свойством ассоциативности, то есть (но при этом не обладает коммутативностью, что по-моему удивительно). Это свойство даёт нам право сделать так: .

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

А теперь пример посерьёзнее:

Пример №3: Пилообразная последовательность

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

Для начала решение без матрицы перехода:

1) Состояние динамики: dp[n][last][less] — количество пилообразных последовательностей длины n , заканчивающихся на цифру last . Причём если less == 0 , то последняя цифра меньше предпоследней, а если less == 1 , значит больше.
2) Начальные значения:
3) Пересчёт динамики:
4) Порядок пересчёта: мы всегда обращаемся к предыдущей длине, так что просто пара вложенных for 'ов.
5) Ответ — это сумма dp[N][0..9][0..1] .

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

Динамика по подотрезкам

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

Пример №4: Запаковка строки

Вот Развернутое условие. Я вкратце его перескажу:

Определим сжатую строку:
1) Строка состоящая только из букв — это сжатая строка. Разжимается она в саму себя.
2) Строка, являющаяся конкатенацией двух сжатых строк A и B . Разжимается она в конкатенацию разжатых строк A и B .
3) Строка D(X) , где D — целое число, большее 1 , а X — сжатая строка. Разжимается она в конкатенацию D строк, разжатых из X .
Пример: “3(2(A)2(B))C” разжимается в “AABBAABBAABBC” .

Необходимо по строке s узнать длину самой короткой сжатой строки, разжимающийся в неё.

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

1) Состояние динамики: d[l][r] — сжатая строка минимальной длины, разжимающаяся в строку s[l:r]
2) Начальные состояния: все подстроки длины один можно сжать только в них самих.
3) Пересчёт динамики:
У лучшего ответа есть какая-то последняя операция сжатия: либо это просто строка из заглавных букв, или это конкатенация двух строк, или само сжатие. Так давайте переберём все варианты и выберем лучший.

4) Порядок пересчёта: прямой по возрастанию длины подстроки или ленивая динамика.
5) Ответ лежит в d[0][len(s)] .

Пример №5: Дубы

Динамика по поддеревьям

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

Пример №6: Логическое дерево

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

1) Состояние динамики: d[v][x] — количество операций, требуемых для получения значения x в вершине v . Если это невозможно, то значение состояния — +inf .
2) Начальные значения: для листьев, очевидно, что своё значение можно получить за ноль изменений, изменить же значение невозможно, то есть возможно, но только за +inf операций.
3) Формула пересчёта:
Если в этой вершине уже значение x , то ноль. Если нет, то есть два варианта: изменить в текущей вершине операцию или нет. Для обоих нужно найти оптимальный вариант и выбрать наилучший.

4) Порядок пересчёта: легче всего реализуется лениво — в виде поиска в глубину из корня.
5) Ответ — d[root][value[root] xor 1] .

Динамика по подмножествам

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

Пример №7: Гамильтонов цикл минимального веса, или задача коммивояжера

Задан взвешенный (веса рёбер неотрицательны) граф G размера N . Найти гамильтонов цикл (цикл, проходящий по всем вершинам без самопересечений) минимального веса.

1) Состояние динамики: dp[mask][v] — путь минимального веса из вершины 0 в вершину v , проходящий по всем вершинам, лежащим в mask и только по ним.
2) Начальные значения: dp[1][0] = 0 , все остальные состояния изначально — +inf .
3) Формула пересчёта: Если i -й бит в mask равен 1 и есть ребро из i в v , то:
Где w[i][v] — вес ребра из i в v .
4) Порядок пересчёта: самый простой и удобный способ — это написать ленивую динамику, но можно поизвращаться и написать перебор масок в порядке увеличения количества единичных битов в ней.
5) Ответ лежит в d[(1 .

Динамика по профилю

Классическими задачами, решающимися динамикой по профилю, являются задачи на замощение поля какими-нибудь фигурами. Причём спрашиваться могут разные вещи, например, количество способов замощения или замощение минимальным количеством фигур.

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

Профиль — это k (зачастую один) столбцов, являющиеся границей между уже замощённой частью и ещё не замощённой. Эта граница заполнена только частично. Очень часто является частью состояния динамики.

Почти всегда состояние — это профиль и то, где этот профиль. А переход увеличивает это местоположение на один. Узнать, можно ли перейти из одного профиля в другой можно за линейное от размера профиля время. Это можно проверять каждый раз во время пересчёта, но можно и предподсчитать. Предподсчитывать будем двумерный массив can[mask][next_mask] — можно ли от одной маски перейти к другой, положив несколько фигурок, увеличив положение профиля на один. Если предподсчитывать, то времени на выполнение потребуется меньше, а памяти — больше.

Пример №8: Замощение доминошками

Найти количество способов замостить таблицу N x M с помощью доминошек размерами 1 x 2 и 2 x 1 .

Здесь профиль — это один столбец. Хранить его удобно в виде двоичной маски: 0 — не замощенная клетка столбца, 1 — замощенная. То есть всего профилей .

0) Предподсчёт (опционально): перебрать все пары профилей и проверить, что из одного можно перейти в другой. В этой задаче это проверяется так:

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

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

Примеры переходов (из верхнего профиля можно перейти в нижние и только в них):

После этого сохранить всё в массив can[mask][next_mask] — 1 , если можно перейти, 0 — если нельзя.
1) Состояние динамики: dp[pos][mask] — количество полных замощений первых pos - 1 столбцов с профилем mask .
2) Начальное состояние: dp[0][0] = 1 — левая граница поля — прямая стенка.
3) Формула пересчёта:

4) Порядок обхода — в порядке увеличения pos .
5) Ответ лежит в dp[pos][0].

Динамика по изломанному профилю

Это очень сильная оптимизация динамики по профилю. Здесь профиль — это не только маска, но ещё и место излома. Выглядит это так:

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

Переходы в динамике по изломанному профилю на примере задачи про замощение доминошками (пример №8):

Восстановление ответа

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

Небольшие оптимизации

Память

Зачастую в динамике можно встретить задачу, в которой состояние требует быть посчитанными не очень большое количество других состояний. Например, при подсчёте чисел Фибоначчи мы используем только два последних, а к предыдущим уже никогда не обратимся. Значит, можно про них забыть, то есть не хранить в памяти. Иногда это улучшает асимптотическую оценку по памяти. Этим приёмом можно воспользоваться в примерах №1, №2, №3 (в решении без матрицы перехода), №7 и №8. Правда, этим никак не получится воспользоваться, если порядок обхода — ленивая динамика.

Время

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

Замена состояния

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

Пример №9: Разложение числа

7
3 + 4
2 + 5
1 + 7
1 + 2 + 4

Решение №1:

1) Состояние динамики: dp[n][k] — количество разложений числа n на числа, меньшие или равные k . Параметр k нужен, чтобы брать всегда только большие числа, чем уже имеющиеся.
2) Начальные значения: dp[1][1] = 1 , dp[1][i] = 0 .
3) Формула пересчёта:

4) Порядок: прямой, в порядке увеличения n .
5) Ответ — сумма dp[N][1..N] .

Состояний: , переходов: . Асимптотика: .

Решение №2:

1) Поменяем состояние. Теперь dp[n][k] — это количество разложений числа n на k различных чисел. Казалось бы незачем, но сейчас будет понятно.
2) Начальные значения: dp[1][1] = 1 , dp[1][i] = 0 .
3) Формула пересчёта:

Все уже имеющиеся числа увеличить на 1 .
Все уже имеющиеся числа увеличить на 1 . Добавить число 1 в разложение.

Строки здесь обозначают слагаемые.

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

4) Порядок пересчёта: прямой, в порядке увеличения n .

Невооруженным взглядом кажется, что у этого решения асимптотика , ведь есть два измерения в состоянии и переходов. Но это не так, ведь второй параметр — k ограничен сверху не числом N , а формулой (сумма чисел от 1 до k меньше или равна разлагаемого числа). Из этой формулы видно, что количество состояний .

5) Ответ — это сумма dp[N][1..k_max] .

Заключение

Основным источником была голова, а туда информация попала с лекций в Летней Компьютерной Школе (для школьников), а также кружка Андрея Станкевича и спецкурса Михаила Дворкина (darnley).

Спасибо за внимание, надеюсь эта статья кому-нибудь пригодится! Хотя мне уже пригодилась — оказывается, написание статьи это хороший способ всё вспомнить.

Свидетельство и скидка на обучение каждому участнику

Зарегистрироваться 15–17 марта 2022 г.

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

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

Регулярное изучение многошаговых процессов восходит к работам русского математика А. А. Маркова начала XX века. Его исследования были продолжены в 40-х годах американским математиком А. Вальдом (A. Wald), что привело к возникновению так называемого последовательного анализа. Впервые основные принципы оптимального управления многошаговыми процессами наиболее полно и систематизированно были сформулированы в 50-х годах XX века американским математиком Р. Беллманом (R. Bellman). Теория динамического программирования родилась из ряда технико-экономических задач, таких, как задача о наиболее эффективном использовании оборудования или задача о наиболее выгодной политике закупок (управление запасами).

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

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

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

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

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

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

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

Решающие правила — это правила которые описывают элементы последовательности в виде формул.

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

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

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

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

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

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

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

решение каких-либо практических задач, построение сложных экономических моделей; адаптация данного метода для решения задач различных предметных областей.

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

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

капитальное бюджетирование инвестиций (формирование портфеля реальных инвестиций);

формирование оптимального портфеля рисковых финансовых инвестиций;

управление активами и пассивами финансовых организаций (банки, инвестиционные фонды, страховые компании);

планирование производственной мощности предприятий;

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

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

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

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

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

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

Задачи комбинаторики, как правило, отвечают на вопрос, сколько существует объектов, обладающих теми или иными свойствами, или сколько существует комбинаторных объектов, обладающих заданными свойствами.

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

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

Неформальное объяснение свойства оптимальности у подзадач может быть продемонстрировано с помощью диаграммы:
Есть задача, которую мы хотим решить при помощи ДП, т.е. найти какой-то план ее решения. Допустим эта задача сложна и сразу решить мы ее не можем. Мы берем малую подзадачу и решаем сначала ее (для x1 ). Затем используя это малое решение x1 , и не меняя структуру этого решения, решаем следующую задачу уже с x1 и x2 . И т.д.

Рис. 1.1. Неформальное объяснение свойства оптимальности у подзадач

Более подробно неформальное объяснение рассматривается ниже.

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

Сначала рассмотрим задачи оптимизации (задачи 1-5):

Пример: Есть некоторая карта дорог, представленная в виде графа. Наша цель: добраться из пункта А в пункт Б. Это сделать надо так, чтобы минимизировать расстояние или потраченное топливо.

Целевой функцией здесь является расстояние от А до Б. Т.е. наша цель — минимизировать расстояние.

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

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

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

Целевая функция: минимизация расходов (либо на издержки на поддержку старого автомобиля, либо на покупку нового).

Переменная выбора: каждый год принимать решение продать машину или оставить.

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

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

Пример: Есть завод, изготавливающий мебель. На заводе работает определенное количество работников, которые могут изготовить соответствующее кол-во определенной мебели (стулья, столы, шкафы и т.п.)

Целевая функция: максимизация прибыли.

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

Целевая функция: максимизация вероятности выигрыша или максимизация среднего выигрыша и т.д.

Переменная выбора здесь зависит от конкретной игры.

Задачи 1 — 5 — это примеры задач оптимизации.

Комбинаторика:

Пример: Задача на решение того, сколько существует деревьев, у которых определенное число листьев; или сколько существует графов для решения такого-то задания и т.п.

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

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

Неформальное объяснение оптимальности подзадач ДП.

Рассмотрим неформальную идею ДП.

Итак, возьмем пример с заводом, изготавливающим мебель.

Для достижения цели максимизации прибыли необходимо решить множество подзадач:

сколько стульев произвести — переменная X1 ,
сколько столов произвести — переменная X2 ,
сколько нанять работников — переменная X3 ,
… Хn .

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

Поэтому ДП предлагает следующее:

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

Важно: Ключевым моментом здесь является использование выполненного решения для малой подзадачи при решении очередного шага — большей подзадачи

Формальная идея ДП

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

1, 1, 2, 3, 5, 8… , т.е. ряда Фибоначчи

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

function fact (a: integer): integer; begin if (a

Кроме того, может возникнуть такой вопрос: для того чтобы найти, например, минимум или максимум, почему бы нам не найти производную? или не использовать множества Ла-Гранжа, или другие методы аппарата математического анализа? Зачем нужно ДП, если есть большой арсенал средств?

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

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

Важно: По этой причине разделение задачи на подзадачи и решение этих подзадач только один раз (!), сокращая этим количество общих вычислений — более оптимальный способ, который и заложен в динамическом программировании

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

Простой пример решения задач при помощи ДП

Рассмотрим вариант решения задачи с помощью динамического программирования.

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

Начнем с суммы одного первого элемента, т.е. просто берем первый элемент:
F(1) = 1
теперь с помощью решения для первого элемента, решим
F(2) = F(1) + 2 = 1 + 2 = 3 , т.е. надо взять сумму первого элемента и добавить к нему второй элемент
F(3) = F(2) + 3 = 6
по аналогии продолжаем и получаем целевую функцию:
F(n) = F(n-1) + An

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

Простой пример, где пока неоправданно используется ДП (искусственно), демонстрирует принцип идей ДП.

Рассмотрим еще один пример.

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

Решение:

Рассмотрим самые простые варианты (подзадачи):

Рассмотрим пример из i ступенек

Как мы можем попасть на i ступеньку:

с i-1 ступеньки, а на i-1 ступеньку мы могли попасть a_i-1 способами
с i-2 ступеньки, а на i-2 ступеньку мы могли попасть a_i-2 способами

Например, как попасть на 4-ю ступеньку:

Т.о., общее количество способов попасть на i ступеньку:
f(a_i) = f(a_i-1) + f(a_i-2)

Определим начальные значения, с которых следует начинать решать задачу.
Если начинать с 1, то формула соответствует нахождению последовательности чисел Фибоначчи.

А можем посчитать и a0 , начав с 0 , т.е. с нулевой ступеньки попасть на нулевую — такой способ 1, просто стоять на месте.

Мы видим, что задача по сути комбинаторная (т.е. количество способов сделать что-либо) свелась к вычислению некоторой рекуррентной последовательности.

Задание 1: реализовать пример для первых десяти ступенек (по сути, первые 10 чисел ряда Фибоначчи), используя рекурсию.

Дополните код:

var c:integer; procedure getKolSposob(i,n: integer); begin writeln (i+n,' '); inc(c); if . then getKolSposob(. ) end; begin c:=1; getKolSposob(0,1); end.

Читайте также: