Динамическое программирование Лекция 17. Динамическим программированием называется способ программирования, при котором задача разбивается на подзадачи, - презентация

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

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

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

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

5 Пример 1: Рассмотрим пример. Требуется вычислить сумму s следующего ряда при x 0: s=1 +1/x+ 1/x 2 + 1/x 3 +…+ 1/x n. Подзадача: вычислим сумму заданного ряда с параметром n=1. Введем переменную a, в которую запишем значение 1/x, а сумму ряда запишем в s. Далее решим подзадачу с параметром n=2, используя значение, записанное в s: s= s + a/x. Затем решим подзадачу с параметром n=3 и т.д. s = 1, a = 1, a = a/x, s = s + a.

6 Пример 2: Имеется n неделимых предметов, вес i-го предмета есть w i. Определить cуществует ли набор предметов, суммарная масса которого равна W килограмм. Если такой набор существует, то определить список предметов в наборе. Обозначим через T(n, W) функцию, значение которой равно 1, если искомый набор имеется, и равно 0, если набора нет. Аргументами функции будут количество предметов n, по которому можно определить вес каждого предмета, и суммарный вес набора W. Определим подзазачи, решением которых будут функции T(i, j), где i обозначает количество начальных предметов, j – требуемый суммарный вес, где 0 i n, 1 j W. Определим начальные значения функции T: T(0, j) = 0 при j 1 (нельзя без предметов набрать массу j > 0), T(i, 0) = 1 при i 1 (всегда можно набрать вес, равный 0).

7 Для решения подзадачи, соответствующей функции T(i, j), рассмотрим два случая. 1)i-ый предмет в набор не берется. Решение задачи с I предметами сводится к решению задачи с i – 1 предметом: T(i, j) = T(i - 1, j). 2) i-ый предмет в набор берется. Масса оставшихся предметов уменьшается на величину w i : T(i, j) = T(i -1, j - w i ). При этом нужно учитывать, что эта ситуация возможна только тогда, когда масса i-го предмета не больше значения j. Для оптимального решения из двух возможных вариантов нужно выбрать наилучший. Рекурентное соотношение при i 1 и j 1: T(i, j)= T(i -1, j) при j < w i T(i, j)= max (T(i -1, j), T(i -1, j - w i )) при j w i.

8 W = 16; w 1 = 4; w 2 = 5; w 3 = 3; w 4 = 7; w 5 = 6. i\j Решение нашего примера определяется T[5, 16] = 1. T[5, 16] = T[4, 16], то 5-ый предмет можно в набор не включать. T[4, 16] T[3, 16] –> 4-ый предмет включается. Оставшаяся масса равна 16-w 4 = 16-7 = 9. T[3, 9] =T[2, 9] –> 3-ый предмет в набор не включаем. T[2, 9] T[1, 9] ] –> 2-oй предмет включается. Оставшаяся масса равна 9-w 2 = = 4. T[1, 4] T[0, 4] –> 1-oй предмет включается, оставшаяся масса равна 0.

9 Задача о рюкзаке Задача состоит в том, чтобы определить наиболее ценную выборку из n предметов, подлежащих упаковке в рюкзак, имеющий ограничение по весу, равное W килограмм. При этом i-ый предмет характеризуется стоимостью с i и весом wi.wi. Итак, необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины W, а суммарная стоимость была максимальна. Если перебирать всевозможные подмножества данного набора из n предметов, то получится решение сложности не менее чем O(2 n ). В настоящее время неизвестен алгоритм решения этой задачи, сложность которого является полиномиальной. Мы рассмотрим алгоритм решения данной задачи для случая, когда все входные данные – целые числа. Его быстродействие есть O(nW).

10 Решение Обозначим через T(n, W) функцию, значение которой соответствует решению нашей задачи. Аргументами функции является количество предметов n, по которому можно определить стоимость и массу каждого предмета, и ограничение по весу W. Определим подзазачи, решением которых будут функции T(i, j), а именно, определим максимальную стоимость предметов, которые можно уложить в рюкзак с ограничением по весу j килограмм, если можно использовать только первые i предметов из заданных, где 0 i n, 0 j n. Определим начальные значения функции T : T(0, 0) = 0, T(0, j) = 0 при j 1 (нет предметов, максимальная стоимость равна 0), T(i, 0) = 0 при i 1 (можно брать любые из первых i предметов, но ограничение по весу равно 0).

11 Для решения подзадачи, соответствующей функции T(i, j), рассмотрим два случая. 1) i-ый предмет не упаковывается в рюкзак. Решение задачи с i предметами сводится к решению задачи с i – 1 предметом: T(i, j) = T(i - 1, j). 2) i-ый предмет упаковывается в рюкзак. Масса оставшихся предметов уменьшается на величину w i, а при добавлении i-го предмета стоимость выборки увеличивается на c i : T(i, j) = T(i -1, j - w i ) + c i. При этом нужно учитывать, что эта ситуация возможна только тогда, когда масса i-го предмета не больше значения j.

12 Для оптимального решения из двух возможных вариантов упаковки рюкзака нужно выбрать наилучший. Рекурентное соотношение при i 1 и j 1: T(i, j)= T(i -1, j) при j < w i T(i, j)= max (T(i -1, j), T(i -1, j - w i ) + c i ) при j w i.

13 Пример W = 16, c1 = 5, w1 = 4; c2 = 7, w2 = 5; c3 = 4, w3 = 3; c4 = 9, w4 = 7; c5 = 8, w5 = 6. i\j Решение примера определяется T[5, 16] = 21. В примере суммарная масса предметов, подлежащих упаковке в рюкзак, совпадает с W, в общем-же случае она не должна превосходить величину W.

14 Обратный ход Требуется определить набор предметов, которые подлежат упаковке в рюкзак. Сравним значение T[n, W] со значением T[n-1, W]. 1) Если T[n, W] T[n-1, W], то предмет c номером n обязательно упаковывается в рюкзак, после чего переходим к сравнению элементов T[n-1, W - w n ] и T[n-2, W- w n ] и т.д. 2) Если T[n-1, W] = T[n-1, W], то n-ый предмет можно не упаковывать в рюкзак. В этом случае следует перейти к рассмотрению элементов T[n-1, W] и T[n-2, W].

15 Пример В примере T[5, 16] = T[4, 16], поэтому 5-ый предмет в рюкзак не упаковывается. Переходим к сравнению элементов таблицы T[4, 16] и T[3, 16]. Их значения не равны, следовательно, четвертый предмет должен быть включен в искомый набор, а ограничение на вес становится равным 16 – w 4 = 16 – 7 =9. Далее сравним элементы T[3, 9] и T[2, 9], они равны, поэтому третий предмет в рюкзак не упаковывается и сравниваем T[2, 9] и T[1, 9], они не совпадают, следовательно, второй предмет должен быть взят в рюкзак, а ограничение на вес становится равным 9 - w 2 = 9 – 5 =4. И наконец сравниваем элементы T[1, 4] и T[0, 4], они не равны, поэтому второй предмет включатся в искомый набор, при этом, ограничение по весу становится равным 0. Итак, для нашего примера в рюкзак упакуются предметы с номерами 1, 2, 4.

16 void Print_item(int i, int j) { if (T[i][j]==0) // максимальный рюкзак для параметров return; // имеет нулевую ценность else if (T[i-1][j] == T[i][j]) Print_item (i-1,j); // можно составить // рюкзак без i-го предмета else { Print_item(i-1,j-w[i]); // Предмет i //упаковывается в рюкзак Printf( %d, i); // печать i-го предмета } } В программе нужно вызвать функцию Print_item с параметрами (n,W). Заметим, что рассуждения были приведены для случая, когда все предметы различны. Cамостоятельно рассмотрите, какие изменения будут внесены в таблицу в противном случае.

17 Алгоритм Ахо Пусть даны две строки S 1 и S 2. Необходимо за минимальное число допустимых операций преобразовать строку S 1 в строку S 2. Допустимой операцией являются следующие операции удаления символа из строки и вставки символа в строку: DEL(S, i) – удалить i-ый элемент строки S; INS(S, i, c) – вставить символ c после i-го элемента строки S. Обозначим через S [i..j] – подстроку от i-го символа до j-го. Пусть M(i,j) – минимальное количество операций, которые требуются, чтобы преобразовать начальные i символов строки S 1 в начальные j символов строки S 2 : S 1 [0..i] –> S 2 [0..j]. S 1 [0..0] и S 2 [0..0] – пустые строки.

18 Заметим, что для преобразования пустой строки в строку длины j требуется j операций вставки, т.е. M (0, j) = j. Аналогично для преобразования строки длины i в пустую строку требуется i операций удаления, т.е. M (i, 0) = i. Пусть мы решили подзадачу c параметрами i –1 и j – 1. Это означает, что из строки S 1 [0..i–1] построена строка S 2 [0..j–1] за минимальное число допустимых операций M(i –1, j –1). I) Пусть S 1 [i] = S 2 [j]. Тогда для получения строки S 2 [0..j] из строки S 1 [0..i] не требуется никаких дополнительных операций. Следовательно, M (i, j) = M (i – 1, j – 1).

19 II) Пусть S 1 [i] S 2 [j]. Возможны два способа получения строки S 2 [0..j]. 1. Пусть из строки S 1 [0..i–1] построена строка S 2 [0..j] за минимальное количество операций M (i–1, j ). Тогда для получения строки S 2 [0..j] из строки S 1 [0..i] требуется удалить i-ый символ из строки S Пусть из строки S 1 [0..i] построена строка S 2 [0..j–1] за минимальное количество операций M (i, j–1). Тогда для получения строки S 2 [0..j] из строки S 1 [0..i] потребуется одна операция вставки i-го символа строки S 1 после символа S 2 [j–1]. Из 2-х возможностей нужно выбрать лучшую. Получим следующие рекуррентные соотношения:

20 M (0, j) = j; M (i, 0) = i; M (i, j) = min (M (i – 1, j – 1), M (i – 1, j ) + 1, M (i, j – 1) +1), если S 1 [i] = S 2 [j]; M (i, j) = min (M (i – 1, j ), M (i, j – 1)) + 1, если S 1 [i] S 2 [j]; Решением задачи будет значение M(m,n), где m длина строки S 1, а n длина строки S 2.

21 Пример S 1 = abc, S 2 = aabddc Построим таблицу M, нумерация строк и столбцов которой начинается с нуля и элементами которой будут числа, равные значениям функции, описанной выше c d d b a a a b c

22 Обратный ход М[1,3] = 2, означает, что из строки a можно получить строку aab, используя две допустимых операции. В примере за три допустимых операции можно преобразовать строку S 1 в S 2. Для определения операций нужно встать на последний символ строки S 1 и начать движение по таблице от правого верхнего угла. В примере движение начнется с ячейки М[3,6]. Находясь в ячейке М[i, j], будем рассматривать два случая. 1) Если М[-1, i] = М[j, -1], то будем сдвигаться по диагонали влево-вниз, попадая в ячейку М[i-1, j-1]. При этом будем перемещаться по строке S 1 на один символ влево, т.е. сделаем текущим в строке символ, находящийся в i-1 позиции. 2) Если М[-1, i] М[j, -1], то будем сдвигаться по таблице на одну позицию либо влево, попадая в ячейку М[i, j-1], либо вниз в ячейку М[i-1, j]. Этот выбор будет зависеть от того, какой из элементов, находящихся в этих ячейках, меньше. При движении влево будем удалять i-ый символ в строке S 1, перемещась на один символ влево. При движении вниз будем вставлять после i-го символа в строке S 1 символ S 2 [j].

23 Последовательность действий для примера Изначально текущим в строке S 1 является последний символ – символ c. Так как М[-1, 3] = М[6, -1], то осуществляем переход в ячейку М[5, 2] и текущим в S 1 становится предпослений символ – b. Далее, так как М[-1, 2] М[5, -1], передвигаемся в ячейку М[4, 2]. При этом вставим после текущего символа b символ S 2 [5] = d (j=5). Продолжая этот процесс вставим символ S 2 [4] = d, затем в строке S 1 сделаем текущим сивол a, вставим в строку S 1 символ a. Процесс продолжается до тех пор, пока не достигнем ячейки M[0,0]. Для нашего примера последовательность операций будет следующая: INS(S 1, 2, d), INS(S 1, 2, d), INS(S 1, 1, a). abc –> abc –> abdc –> abddc –> abddc –> aabddc

24 Отметим, что решений в данной задаче может быть несколько. Движение по таблице представлено ниже. вниз по i-му столбцу из j-ой строки в j–1-ю INS(S 1, i, S 2 [j]) вставка после i-й позиции в S 1 символа S 2 [j] движение влево по j-й строке из i-го столбца в i–1-й DEL(S 1, i)удаление i-го символа в S 1 и передвижение на i– 1-ю позицию движение по диагонали влево вниз перемещение текущей позиции в S 1 на один символ влево

25 Задача о телефонном номере (подключена в системе тестирования NSUTS в школьных тренировках) Если вы обратили внимание, то клавиатура многих телефонов выглядит как показано –> Использование изображенных на клавишах букв позволяет представить номер телефона в виде легко запоминающихся слов. Многие фирмы пользуются этим и стараются подобрать себе номер телефона так, чтобы он содержал как можно больше букв из имени фирмы. Напишите программу, которая преобразует исходный цифровой номер телефона в соответствующую последовательность букв и цифр, содержащую как можно больше символов из названия фирмы. При этом буквы из названия фирмы должны быть указаны в полученном номере в той же последовательности, в которой они встречаются в названии фирмы. Например, если фирма называется IBM, а исходный номер телефона 246, то замена его на BIM не допустима, тогда как замена его на 2IM или В4М является правильной. S 1 = IBM, S 2 = 246. При этом, если в S 1 встречаются буквы, которые соответствуют цифрам номера телефона в нужном порядке, то они останутся без изменения. 1 2 АВС 3 DEF 4 GHI 5 JKL б MN 7 PRS 8 TUV 9 WXY 0 OQZ

26 Формат входных данных: Первая строка входного файла содержит название фирмы. Она состоит только из заглавных букв латинского алфавита, количество которых не превышает 80 символов. Вторая прока содержит номер телефона в виде последовательности цифр. Цифр в номере телефона также не более 80. Формат выходных данных: В единственной строке выходного файла должно содержаться число букв из измененного номера. Пример файла входных данных: IBM 246 Пример файла выходных данных: 2

27 Задача о расстановке скобок Рассмотрим вычисление произведения n матриц M = M 1 x M 2 x... x M n. (1) Порядок, в котором матрицы перемножаются, может cущественно сказаться на общем числе операций, требуемых для вычисления матрицы М, независимо от алгоритма, применяемого для умножения матриц. Умножение матрицы размера [р q] на матрицу размера [q r] требует pqr операций.

28 Пример Рассмотрим произведение матриц: М = M 1 М 2 М 3 М 4 [10 20] [20 50] [50 1] [1 100] Если вычислять матрицу М в порядке: M1 ( М2 ( М3 М4,)), то потребуется операций. (50*1*100) [50 100], 5000; (20*50*100) [20 100], ; (10*20*100) [10 100], Вычисление же в порядке: ( M1 (М2 М3 )) М4 требует лишь операций. (20*50*1) [20 1], 1000; (10*20*1) [10 1], 200; (10*1*100) [10 100], 1000.

29 Перебор с целью минимизировать число операций имеет экспоненциальную сложность. На первом этапе определим за какое минимальное количество операций можно получить матрицу М из равенства (1). Будем считать подзадачами вычисление минимального количества операций при перемножении меньшего, чем n, количества матриц. В качестве параметров рассматриваемой задачи возьмем индексы i и j (1 i j n), обозначающие номера первой и последней матриц в цепочке M i М i+1... М j. Сначала решим поздачи, когда j=i+1, т.е. когда перемножаются две рядом стоящие матрицы. Решения – количество затраченных операций, запишем в ячейке таблицы T с номерами (i. j). T ij будет содержать число, равное количеству операций при умножении цепочки матриц M i М i+1, где 1 i 3.

30 Для примера из четырех матриц в таблице будут определены следующие элементы T: t 1,2, t 2,3 и t 3, M 1 М 2 М 3 М 4 [10 20] [20 50] [50 1] [1 100] Далее перейдем к решению подзадач с параметрами j=i+2. Рассмотрим, например, цепочку матриц M 1 М 2 М 3. Решением этой подзадачи будет минимальное количество операций, выбранное из двух возможных порядков перемножения матриц: (M 1 М 2 ) М 3 и M 1 (М 2 М 3 ). При этом для выражений в скобках ответы уже записаны в таблице T. Результат запишем в ячейку T 1,3. Затем перейдем к решению подзадач с параметрами j=i+3 и т.д.

31 Обозначим через t ij минимальную сложность вычисления цепочки матриц M i М i+1... М j, где 1 i j n. Ее можно получить следующим образом: Здесь t ik минимальная сложность вычисления цепочки М' = M i М i+1... М k, a t k+1,j минимальная сложность вычисления цепочки М˝= M k+1 М k+2... М j. Третье слагаемое r ikj равно сложности умножения М' на М˝. Утверждается, что t ij ( j > i) наименьшая из сумм этих трех членов по всем возможным значениям k, лежащим между i и j - 1.

32 Итак, t ij вычисляются в порядке возрастания разностей нижних индексов. Процесс начинается с вычисления t ii для всех i, затем t i,i+1 для всех i, потом t i,i+2 и т. д. При этом t ik и t k+1,j будут уже вычислены, когда мы приступим к вычислению t ij. Оценка сложности данного алгоритма есть О (п 3 ). В результате работы алгоритма для примера из четырех матриц будет построена следующая таблица T: Порядок, в котором можно произвести эти умножения, легко определить, приписав каждой клетке то значение k, на котором достигается минимум

33 Алгоритм for (i=0; i

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

35 Нахождение кратчайших путей между всеми парами вершин Строим матрицу стоимостей: w(i, j), если ребро (i, j) E M[i, j] =+, если ребро (i, j) E 0, если i = j Обозначим через d [i, j] матрицу кратчайших путей между всеми вершинами. Вершины занумеруем числами от 1 до n.

36 Алгоритм Флойда-Уоршолла Обозначим через d ij (k) стоимость кратчайшего пути из вершины с номером i в вершину с номером j с промежуточными вершинами из множества {1, 2, …, k}. M[i, j], если k = 0, d ij (k) = min(d ij (k-1), d ik (k-1) + d kj (k-1) ), если k 1 D (n) содержит искомое решение

37 Floyd-Warshall(M, n) { D (0) M; for (k = 0; k

38 Задача "Divisibility ACM NEERC (подключена в системе тестирования NSUTS в школьных тренировках) Consider an arbitrary sequence of integers. One can place + or – operators between integers in the sequence, thus deriving different arithmetical expressions that evaluate to different values. Let us, for example, take the sequence: 17, 5, –21, 15. There are eight possible expressions: – 21+15= –21–15=– – –21+15= – –21–15=28 17–5 + –21+15=6 17–5+–21–15=–24 17–5– –21+15=48 17–5– –21–15=18 We call the sequence of integers divisible by K if + or – operators can be placed between integers in the sequence in such way that resulting value is divisible by K. In the above example, the sequence is divisible by 7 (17+5+–21–15=–14) but is not divisible by 5. You are to write a program that will determine divisibility of sequence of integers. The first line of the input file contains two integers, N and K (1 N 10000, 2 K 100) separated by a space. The second line contains a sequence of N integers separated by spaces. Each integer is not greater than by its absolute value.

39 Задача "Gangsters" (подключена в системе тестирования NSUTS в школьных тренировках) N gangsters are going to a restaurant. The i-th gangster comes at the time T i and has the prosperity P i. The door of the restaurant has K+1 states of openness expressed by the integers in the range [0, K]. The state of openness can change by one in one unit of time; i.e. it either opens by one, closes by one or remains the same. At the initial moment of time the door is closed (state 0). The i-th gangster enters the restaurant only if the door is opened specially for him, i.e. when the state of openness coincides with his stoutness S i. If at the moment of time when the gangster comes to the restaurant the state of openness is not equal to his stoutness, then the gangster goes away and never returns. The restaurant works in the interval of time [0, T]. The goal is to gather the gangsters with the maximal total prosperity in the restaurant by opening and closing the door appropriately. The first line of the input file contains the values N, K, and T, separated by spaces. (1N,K100 ). he second line of the input file contains the moments of time when gangsters come to the restaurant T 1, T 2,..., T N, separated by spaces. The third line of the input file contains the values of the prosperity of gangsters P 1, P 2,..., P N, separated by spaces. The forth line of the input file contains the values of the stoutness of gangsters S 1, S 2,..., S N, separated by spaces. All values in the input file are integers.

40 Пример t = S = P = гангстеры L – состояние двери m i,j = max { [m i-1,j-1, m i-1,j, m i-1,j+1 ] + f i } где p i, если L = s i 0 f i =