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

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

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

1. Задача распределения инвестиций. Распределении инвестиций между предприятиями П₁, П₂. П_n. Инвестируемая сумма E усл. ден. ед.
2. Задача распределения ресурсов. Планируется работа двух предприятий на n лет. Начальные ресурсы равны s₀ .
3. Метод прогонки.
4. Задача замены оборудования.
5. Складская задача: составить оптимальную программу выпуска продукции X , которая минимизирует суммарные издержки предприятия.
6. Задача Джонсона.
7. Задача о рюкзаке (решение задачи о загрузке транспортного средства).
8. Динамическая оптимизация в планировании работ
   В условиях задачи производственного планирования найти оптимальные сроки начала строительства каждого из объектов так, чтобы суммарный срок строительства всех объектов был бы минимальным.
   

   Объекты / Стадии	№1	№2	№3	№4
   A1	2	5	4	3
   A2	1	4	2	6
   A3	3	4	3	4

Задача распределения инвестиций

Таблицы могут иметь разный вид.
Таблица 1 — Первый вариант таблицы исходных данных

x	f1(x)	f2(x)	f3(x)
1	6.3	4	5
2	5.2	6	7
3	4.3	4.6	7.8
4	5	6	3
5*	7	6.3	8.2

* — здесь значение 5 — максимальное значение (сумма для распределения).

Таблица 2 — Второй вариант таблицы исходных данных

x	0	10	20	30	40
f1(x)	0	4	5	7	8
f2(x)	0	3	3	4	6
f3(x)	0	4	4	5	6

Пример задачи.
Для двух предприятий выделено A единиц средств. Как распределить все средства в течение 4 лет, чтобы доход был наибольшим, если известно, что доход от x единиц средств, вложенных в первое предприятие, равен f₁(х), а доход от y единиц средств, вложенных во второе предприятие, равен f₂(y). Остаток средств к концу года составляет g₁(x) для первого предприятия и g₂(y) для второго предприятия. Задачу решить методом динамического программирования.

При вводе данных первую нулевую строку можно не заполнять.

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

Метод прогонки

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

Источник

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

Описание

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

Динамическое программирование очень похоже на рекурсию, при этом:

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

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

Классическая задача — числа Фибоначчи

Последовательность Фибоначчи Fn задается формулами: F1 = 1, F2 = 1, Fn = Fn – 1 + Fn – 2 при n > 1. Необходимо найти Fn по номеру n.

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

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

Но как можно заметить, такая, казалось бы, простая программа уже при n = 40 работает заметно долго. Это связано с тем, что одни и те же промежуточные данные вычисляются по несколько раз — число операций нарастает с той же скоростью, с какой растут числа Фибоначчи — экспоненциально.

Один из выходов из данной ситуации — сохранение уже найденных промежуточных результатов с целью их повторного использования (кеширование):

Приведенное решение корректно и эффективно. Но можно поступить ещё проще:

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

Именно такое решение и является классическим для динамического программирования: мы сначала решили все подзадачи (нашли все F[i] для i K[n]. Прежде всего заметим, что существует ровно один маршрут из точки 1 в точку 1 — он не содержит ни одного прыжка. В точку 2 можно прыгнуть единственным способом — из точки 1.

Как вычислить K[n]? В точку кузнечик может попасть двумя способами — из точки при помощи прыжка длиной 2 и из точки прыжком длины 1. То есть число способов попасть в точку n равно сумме числа способов попасть в точку (n-1) и (n-2), что позволяет выписать рекуррентное соотношение: K[n] = K[n-1] + K[n-2] .

Можно заметить, что данная задача по сути свелась к числам Фибоначчи, поэтому мы не будем выписывать её решение.

Упражнение №1

Решите задачу о количестве способов достичь точки n из точки 1, если кузнечик умеет прыгать +1, +2 и +3.

Упражнение №2

Решите задачу о количестве способов достичь точки n из точки 1, если кузнечик умеет прыгать +1, +2 и *3.

Задача о кузнечике со стоимостями посещения точек

Пусть кузнечик прыгает на одну или две точки вперед, а за прыжок в каждую точку необходимо заплатить определенную стоимость, различную для различных точек. Стоимость прыжка в точку i задается значением price[i] списка price. Необходимо найти минимальную стоимость маршрута кузнечика из точки 0 в точку n.

На этот раз нам необходимо модифицировать определение целевой функции. Пусть C[n] — минимальная стоимость пути из 1 в n.

Выведем рекуррентное соотношение для этой функции.Чтобы попасть в точку n мы должны попасть в неё последним прыжком из (n-1) или (n-2). Минимальные стоимости этих маршрутов будут равны С[n-1] и С[n-2] соответственно, к ним придется добавить значение price[n] за прыжок в клетку n. Но из двух клеток мы можем выбрать любую.

Нужно выбрать тот маршрут, который имеет наименьшую стоимость: C[n] = min(C[n-1], C[n-2]) + price[n]

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

Упражнение №3

Напишите функцию calculate_min_cost(n, price) вычисления наименьшей стоимость достижения клетки n из клетки 1

Восстановление наиболее выгодной траектории

Итак, мы нашли список С, где будет записана минимальная стоимость маршрута для всех точек от 1 до n.

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

Для восстановления ответа будем для каждой точки запоминать номер точки prev[i], из которой кузнечик попал в точку i, если он будет передвигаться по пути минимальной стоимости. То есть prev[i] — это точка, предшествующая точке с номером i на пути минимальной стоимости (также говорят, что Prev — это массив предшественников). Как определить prev[i]? Если C[i-1] C[i-2] , то кузнечик попал в точку i из точки (i-1), поэтому prev[i] = i — 1, иначе prev[i] = i — 2.

Для восстановления пути необходимо начать с точки n и переходить от каждой точки к ее предшественнику, пока путь не дойдет до начальной точки с номером 0. Номера всех вершин будем добавлять в список path. В конце в список path добавляется начальная вершина номер 1, которая не была обработана в основном цикле, а затем весь список path разворачивается в обратном порядке (т. к. вершины добавляются в обратном порядке, от конечной к начальной).

Упражнение №4

Модифицируйте алгоритм вычисления значений целевой функции так, чтобы вычислить значения prev[i], и восстановите траекторию наименьшей стоимости из точки 1 в точку n.

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

Игра с ферзём

Рассмотрим игру «Ферзя в угол» для двух игроков. В левом верхнем углу доски размером N*M находится ферзь, который может двигаться только вправо-вниз. Игроки по очереди двигают ферзя, то есть за один ход игрок может переместить ферзя либо по вертикали вниз, либо по горизонтали вправо, либо во диагонали вправо-вниз. Выигрывает игрок, который поставит ферзя в правый нижний угол. Необходимо определить, какой из игроков может выиграть в этой игре независимо от ходов другого игрока (имеет выигрышную стратегию).

Будем заполнять доску знаками «+» и «-». Знак «+» будет означать, что данная клетка является выигрышной для ходящего с неё игрока (то есть если ферзь стоит в этой клетке, то игрок, который делает ход, может всегда выиграть), а знак «-» означает, что он проигрывает. Клетки последней строки, последнего столбца и диагонали, ведущей из правого нижнего угла необходимо отметить, как «+», так как если ферзь стоит в этой клетке, то ходящий игрок может выиграть одним ходом.

Но в правом нижнем углу необходимо поставить знак «-» — если ферзь стоит в углу, то тот игрок, которых должен делать ход, уже проиграл.

Теперь рассмотрим две клетки, из которых можно пойти только в те клетки, в которых записан знак «+». В этих клетках нужно записать знак «-» — если ферзь стоит в этих клетках, то какой бы ход не сделал ходящий игрок, ферзь окажется в клетке, в которой стоит знак «+», то есть выигрывает ходящий игрок. Значит, тот, кто сейчас ходит — всегда проигрывает.

Но теперь в те клетки, из которых можно попасть в клетку, в которой стоит знак «-» за один ход, необходимо записать знак «+» — если ферзь стоит в этой клетке, то игрок, который делает ход, может выиграть, если передвинет ферзя в клетку, в которой стоит знак «-»:

Дальше таблица заполняется аналогично. В клетке ставиться знак «+», если есть ход, который ведет в клетку, в которой стоит знак «—». В клетке ставится знак «-», если все ходы из этой клетки ведут в клетки, в которых записан знак «+».

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

Упражнение №5

Реализовать алгоритм поиска выигрышных и проигрышных позиций в игре с ферзём на прямоугольном поле M на N, где N — высота, а M — ширина поля.

Упражнение №6

Реализовать алгоритм поиска выигрышных и проигрышных позиций в аналогичной игре, но ходы делает король (только вправо, вниз и по диагонали).

Источник

Динамическое программирование. Классические задачи

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

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

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

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

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

Классической задачей на последовательности является следующая.

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

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

Но как можно заметить, такая, казалось бы, простая программа уже при n = 40 работает заметно долго. Это связано с тем, что одни и те же промежуточные данные вычисляются по несколько раз — число операций нарастает с той же скоростью, с какой растут числа Фибоначчи — экспоненциально.

Один из выходов из данной ситуации — сохранение уже найденных промежуточных результатов с целью их повторного использования:

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

Такое решение можно назвать решением «с начала» — мы первым делом заполняем известные значения, затем находим первое неизвестное значение (F₃), потом следующее и т.д., пока не дойдем до нужного.

Именно такое решение и является классическим для динамического программирования: мы сначала решили все подзадачи (нашли все F_i для i 2, соответственно.

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

Задача 1. Посчитать число последовательностей нулей и единиц длины n, в которых не встречаются две идущие подряд единицы.

При n 2. То есть данная задача фактически сводится к нахождению чисел Фибоначчи.

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

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

Приведем пару формулировок таких задач:

Задача 2. Дано прямоугольное поле размером n*m клеток. Можно совершать шаги длиной в одну клетку вправо или вниз. Посчитать, сколькими способами можно попасть из левой верхней клетки в правую нижнюю.

Задача 3. Дано прямоугольное поле размером n*m клеток. Можно совершать шаги длиной в одну клетку вправо, вниз или по диагонали вправо-вниз. В каждой клетке записано некоторое натуральное число. Необходимо попасть из верхней левой клетки в правую нижнюю. Вес маршрута вычисляется как сумма чисел со всех посещенных клеток. Необходимо найти маршрут с минимальным весом.

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

Рассмотрим более подробно задачу 2. В некоторую клетку с координатами (i,j) можно прийти только сверху или слева, то есть из клеток с координатами (i – 1, j) и (i, j – 1):

Таким образом, для клетки (i, j) число маршрутов A[i][j] будет равно
A[i – 1][j] + A[i][j – 1], то есть задача сводится к двум подзадачам. В данной реализации используется два параметра — i и j — поэтому применительно к данной задаче мы говорим о двумерном динамическом программировании.

Теперь мы можем пройти последовательно по строкам (или по столбцам) массива A, находя число маршрутов для текущей клетки по приведенной выше формуле. Предварительно в A[0][0] необходимо поместить число 1.

В задаче 3 в клетку с координатами (i, j) мы можем попасть из клеток с координатами
(i – 1, j), (i, j – 1) и (i – 1, j – 1). Допустим, что для каждой из этих трех клеток мы уже нашли маршрут минимального веса, а сами веса поместили в W[i – 1][j], W[i][j – 1],
W[i – 1][j – 1]. Чтобы найти минимальный вес для (i, j), необходимо выбрать минимальный из весов W[i – 1][j], W[i][j – 1], W[i – 1][j – 1] и прибавить к нему число, записанное в текущей клетке:

W[i][j] = min(W[i–1][j], W[i][j – 1], W[i – 1][j – 1]) + A[i][j];

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

На следующем рисунке приведен пример исходных данных и одного из шагов алгоритма.

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

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

Задачи на подпоследовательности

Рассмотрим задачу о возрастающей подпоследовательности.

Задача 4. Дана последовательность целых чисел. Необходимо найти ее самую длинную строго возрастающую подпоследовательность.

Начнем решать задачу с начала — будем искать ответ, начиная с первых членов данной последовательности. Для каждого номера i будем искать наибольшую возрастающую подпоследовательность, оканчивающуюся элементом в позиции i. Пусть исходная последовательность хранится в массиве A. В массиве L будем записывать длины максимальных подпоследовательностей, оканчивающихся текущим элементом. Пусть мы нашли все L[i] для 1

Источник