анти. Guide to Competitive
 Скачать 2.39 Mb.
|
|
Глава 6 Динамическое программирование Динамическое программирование – это техника проектирования алгорит- мов, которую можно использовать для нахождения оптимальных реше- ний задач и подсчета числа таких решений. Эта глава является введением в динамическое программирование, а его применения не раз встретятся далее на страницах этой книги. В разделе 6.1 обсуждаются основные элементы динамического про- граммирования в контексте задачи о размене монет. Дан набор монет разных номиналов, и требуется составить заданную денежную сумму, ис- пользуя минимальное число монет. Существует простой жадный алгоритм решения этой задачи, но, как мы увидим, он не всегда дает оптимальное решение. А с помощью динамического программирования мы сможем по- строить эффективный алгоритм, который гарантированно находит опти- мальное решение. В разделе 6.2 рассмотрены избранные задачи, демонстрирующие неко- торые возможности динамического программирования: нахождение наи- большей возрастающей подпоследовательности в массиве, нахождение оптимального пути на двумерной сетке и порождение всех возможных сумм весов в задаче о рюкзаке. 6.1. Основные понятия В этом разделе мы рассмотрим основные понятия динамического про- граммирования в контексте задачи о размене монет. Сначала мы предста- вим жадный алгоритм, который не всегда находит оптимальное решение, а затем покажем, как можно эффективно решить задачу, применив дина- мическое программирование. 6.1.1. Когда жадный алгоритм не работает Пусть имеется множество номиналов монет coins = {c 1 , c 2 , …, c k } и де- нежная сумма n. Задача заключается в том, чтобы разменять сумму n, ис- 6.1. Основные понятия 87 пользуя как можно меньше монет. Количество монет одного номинала не ограничено. Например, если coins = {1, 2, 5} и n = 12, то оптимальное решение 5 + 5 + 2 = 12, так что достаточно трех монет. Существует естественный жадный алгоритм решения задачи: всегда выбирать монету максимально возможного номинала, так чтобы общая сумма не превысила n. Например, если n = 12, то сначала выбираем две монеты номинала 5, а затем одну монету номинала 2. Стратегия кажет- ся разумной, но всегда ли она оптимальна? Оказывается, что не всегда. Например, если coins = {1, 3, 4} и n = 6, то оптимальное решение состоит из двух монет (3 + 3 = 6), тогда как жадный алгоритм дает решение с тремя монетами (4 + 1 + 1 = 6). Этот простой контрпример показывает, что жадный алгоритм не корректен 1 Тогда как же решить задачу? Можно было бы, конечно, попытать- ся отыскать другой жадный алгоритм, только вот никаких очевидных стратегий не просматривается. Альтернатива – применить алгоритм полного перебора всех возможных способов размена. Такой алгоритм точно даст правильные результаты, но при больших входных данных будет работать очень медленно. Однако, воспользовавшись динамическим программированием, мы можем создать алгоритм, который близок к полному перебору, но при этом эффективен. Следовательно, можно применять его к обработке больших входных данных, сохраняя уверенность в правильности ре- зультата. Ко всему прочему, ту же технику можно применять к решению многих других задач. 6.1.2. Нахождение оптимального решения Чтобы воспользоваться динамическим программированием, мы должны сформулировать задачу рекурсивно, так чтобы ее решение мож- но было получить, зная решения меньших подзадач. В задаче о размене монет естественная рекурсивная постановка заключается в вычислении значений следующей функции solve (x): каково минимальное число мо- нет, сумма номиналов которых равна x? Очевидно, значение функции зависит от номиналов монет. Например, ниже приведены значения функции для небольших x в случае, когда coins = {1, 3, 4}: solve (0) = 0 solve (1) = 1 solve (2) = 2 solve (3) = 1 solve (4) = 1 solve (5) = 2 1 Интересно знать, когда жадный алгоритм все-таки работает. В работе Pearson [28] описан эф- фективный алгоритм ответа на этот вопрос. 88 Глава 6. Динамическое программирование solve (6) = 2 solve (7) = 2 solve (8) = 2 solve (9) = 3 solve (10) = 3 Например, solve (10) = 3, потому что для размена суммы 10 нужно, по крайней мере, 3 монеты. Оптимальное решение 3 + 3 + 4 = 10. Важное свойство функции solve заключается в том, что ее можно вы- числить, зная значения для меньших аргументов. Идея в том, чтобы рас- смотреть первую монету, выбранную для размена. Так, в примере выше первой монетой может быть 1, 3 или 4. Если первой выбрать монету 1, то останется решить задачу о размене суммы 9 с помощью минимального количества монет: это задача того же вида, что и исходная, только меньше по размеру. Разумеется, то же рассуждение применимо к монетам 3 и 4. Поэтому можно выписать следующую рекурсивную формулу вычисления минимального количества монет: solve (x) = min( solve (x − 1) + 1, solve (x − 3) + 1, solve (x − 4) + 1). Базой рекурсии является равенство solve (0) = 0, поскольку для раз- мена нулевой суммы монеты не нужны. А дальше можно написать, на- пример: solve (10) = solve (7) + 1 = solve (4) + 2 = solve (0) + 3 = 3. Теперь мы готовы представить общую рекурсивную функцию, которая вычисляет минимальное количество монет, необходимых для размена суммы x: ⎧ ∞ x < 0 solve (x) = ⎨ 0 x = 0 ⎩min c ∈ coins solve (x − c) + 1 x > 0 Прежде всего если x < 0, то значение бесконечно, потому что разменять отрицательную сумму невозможно. Далее, если x = 0, то значение равно 0, потому для размена нулевой суммы монеты не нужны. Наконец, если x > 0, то переменная c пробегает все возможные варианты выбора первой монеты. Отыскав рекурсивную функцию, решающую задачу, мы уже можем на- писать реализацию решения на C++ (константа INF обозначает бесконеч- ность): 6.1. Основные понятия 89 int solve(int x) { if (x < 0) return INF; if (x == 0) return 0; int best = INF; for (auto c : coins) { best = min(best, solve(x-c)+1); } return best; } Однако эта функция неэффективна, потому что сумму можно разменять многими способами, и функция проверяет все. По счастью, это несложно исправить и сделать функцию эффективной. Запоминание. Ключевая идея динамического программирования – запо минание, т. е. мы сохраняем каждое значение функции в массиве сра- зу после его вычисления. И если впоследствии это значение понадобится снова, то мы можем достать его из массива, не делая рекурсивных вызо- вов. Для этого создадим два массива: bool ready[N]; int value[N]; где ready [x ] – признак, показывающий, было ли вычислено значение solve (x), а value [x ] – само значение, если оно было вычислено. Константа N выбирается так, чтобы все необходимые значения уместились в массив. Теперь функцию можно реализовать эффективно: int solve(int x) { if (x < 0) return INF; if (x == 0) return 0; if (ready[x]) return value[x]; int best = INF; for (auto c : coins) { best = min(best, solve(x-c)+1); } ready[x] = true; value[x] = best; return best; } Функция сначала обрабатывает рассмотренные выше случаи x < 0 и x = 0. Затем она проверяет (глядя на ready [x ]), сохранено ли значение solve (x)в элементе value [x ], и если да, то сразу возвращает его. В противном случае значение solve (x) вычисляется рекурсивно и сохраняется в value [x ]. 90 Глава 6. Динамическое программирование Эффективность этой функции объясняется тем, что значение для каж- дого параметра x рекурсивно вычисляется только один раз. А после того как значение solve (x)сохранено в value [x ], его можно легко получить, ког- да функция снова будет вызвана с параметром x. Временная сложность ал- горитма равна O(nk), где n – подлежащая размену сумма, а k – количество номиналов монет. Итеративная реализация. Отметим, что массив value можно также за- полнить итеративно, воспользовавшись следующим циклом: value[0] = 0; for (int x = 1; x <= n; x++) { value[x] = INF; for (auto c : coins) { if (x-c >= 0) { value[x] = min(value[x], value[x-c]+1); } } } На самом деле участники олимпиад предпочитают именно такую реа- лизацию, поскольку она короче и постоянные множители в ней меньше. Далее мы тоже будем использовать итеративные реализации в примерах. Тем не менее рассуждать о динамическом программировании часто про- ще в терминах рекурсивных функций. Построение решения. Иногда нас просят не только найти значение в оптимальном решении, но и привести пример построения самого реше- ния. Чтобы сделать это для задачи о размене монет, объявим новый мас- сив, в котором для каждой размениваемой суммы будем хранить первую монету в оптимальном решении: int first[N]; Теперь модифицируем исходный алгоритм следующим образом: value[0] = 0; for (int x = 1; x <= n; x++) { value[x] = INF; for (auto c : coins) { if (x-c >= 0 && value[x-c]+1 < value[x]) { value[x] = value[x-c]+1; first[x] = c; } } } 6.1. Основные понятия 91 Показанный ниже код печатает монеты, составляющие оптимальное решение для размена суммы n: while (n > 0) { cout << first[n] << "\n"; n -= first[n]; } 6.1.3. Подсчет решений Рассмотрим теперь другой вариант задачи о размене монет: требуется найти, сколькими способами можно разменять сумму x монетами задан- ных номиналов. Например, если coins = {1, 3,4} и x = 5, то всего есть 6 спо- собов: • 1 + 1 + 1 + 1 + 1; • 3 + 1 + 1; • 1 + 1 + 3; • 1 + 4; • 1 + 3 + 1; • 4 + 1. И эту задачу можно решить рекурсивно. Обозначим solve (x)число спо- собов разменять сумму x. Например, если coins = {1, 3,4}, то solve(5) = 6, и рекурсивная формула имеет вид: solve (x) = solve (x − 1)+ solve (x − 3)+ solve (x − 4). А в общем виде рекурсивная функция выглядит так: ⎧0 x < 0 solve (x) = ⎨ 1 x = 0 ⎩∑ c ∈ coins solve (x − c) x > 0 Если x < 0, то значение равно нулю, поскольку решений нет. Если x = 0, то значение равно 1, поскольку нулевую сумму можно разменять только од- ним способом. В остальных случаях вычисляем сумму всех значений вида solve (x − c), где c – элемент coins Следующий код заполняет массив count , в котором count [x ] равно значе- нию solve (x)для 0 ≤ x ≤ n: count[0] = 1; for (int x = 1; x <= n; x++) { for (auto c : coins) { if (x-c >= 0) { count[x] += count[x-c]; } 92 Глава 6. Динамическое программирование } } Часто число решений настолько велико, что вычислять его точно необя- зательно, а достаточно дать ответ по модулю m,например m = 10 9 + 7. Это можно сделать, изменив код, так чтобы все вычисления производились по модулю m. В предыдущем фрагменте достаточно добавить строку count[x] %= m; после строки count[x] += count[x-c]; 6.2. Другие примеры Обсудив основные идеи динамического программирования, мы можем рассмотреть ряд задач, которые эффективно решаются этим методом. Как мы увидим, динамическое программирование – универсальная техника, имеющая много применений в проектировании алгоритмов. 6.2.1. Наибольшая возрастающая подпоследовательность Наибольшей возрастающей подпоследовательностью в массиве из n эле- ментов называется самая длинная последовательность элементов мас- сива, простирающаяся слева направо и такая, что каждый следующий элемент больше предыдущего. На рис. 6.1 показана наибольшая возраста- ющая подпоследовательность в массиве из восьми элементов. Рис. 6.1. Наибольшая возрастающая подпоследовательность в этом массиве [2, 5, 7, 8] Для эффективного поиска наибольшей возрастающей подпоследова- тельности мы воспользуемся динамическим программированием. Обо- значим length (k)длину наибольшей возрастающей подпоследовательно- сти, оканчивающейся в позиции k. Если мы сумеем вычислить все значения length (k) для 0 ≤ k ≤ n − 1, то найдем и длину наибольшей возрастающей подпоследовательности. Значения этой функции для нашего массива при- ведены ниже: length (0) = 1 length (1) = 1 6.2. Другие примеры 93 length (2) = 2 length (3) = 1 length (4) = 3 length (5) = 2 length (6) = 4 length (7) = 2 Например, length (6) = 4, поскольку наибольшая возрастающая под- последовательность, оканчивающаяся в позиции 6, состоит из 4 элемен- тов. Чтобы вычислить значение length (k), мы должны найти позицию i < k, для которой array [i ] < array [ k] и length (i)максимально. Тогда length (k)= length (i) + 1, поскольку это оптимальный способ добавить array [ k] в под- последовательность. Но если такой позиции i не существует, то length (k)= 1, т. е. подпоследовательность состоит только из элемента array [ k]. Поскольку значение функции всегда можно вычислить, зная ее значе- ния при меньших аргументах, мы можем воспользоваться динамическим программированием. В следующем коде значения функции запоминают- ся в массиве length for (int k = 0; k < n; k++) { length[k] = 1; for (int i = 0; i < k; i++) { if (array[i] < array[k]) { length[k] = max(length[k],length[i]+1); } } } Понятно, что получившийся алгоритм работает за время O(n 2 ) 2 6.2.2. Пути на сетке Следующая наша задача – поиск пути из левого верхнего в правый нижний угол сетки n×n при условии, что разрешено двигаться только вниз и вправо. В каждой клетке находится целое число, и путь должен быть та- ким, чтобы сумма значений в лежащих на нем клетках была максималь- ной. На рис. 6.2 показан оптимальный путь на сетке 5×5. Сумма значений вдоль пути равна 67, и это наибольшая сумма на путях из левого верхнего в правый нижний угол. 2 С помощью динамического программирования эту задачу можно решить эффективнее – за время O(n log n). Сможете ли вы найти такое решение? 94 Глава 6. Динамическое программирование Рис. 6.2. Оптимальный путь из левого верхнего в правый нижний угол Пронумеруем строки и столбцы сетки числами от 1 до n, и пусть value [y ][x] равно значению в клетке (y, x). Обозначим sum (y, x)максимальную сумму на пути из левого верхнего угла в клетку square (y, x). Тогда sum (n, n)– мак- симальная сумма на путях из левого верхнего в правый нижний угол. Так, в нашем примере сетки sum (5, 5)= 67. Справедлива формула sum (y, x)= max( sum (y, x − 1), sum (y − 1, x))+ value [y ][x], основанная на наблюдении, что путь, заканчивающийся в клетке (y, x), может приходить в нее либо из клетки (y, x − 1), либо из клетки (y − 1, x) (рис. 6.3). Поэтому мы выбираем направление, доставляющее максимум сумме. Положим sum (y, x)= 0, если y = 0 или x = 0, чтобы рекуррентная фор- мула была справедлива также для клеток, примыкающих к левому и верх- нему краю. Рис. 6.3. Два возможных способа дойти до клетки Поскольку у функции два параметра, массив в методе динамического программирования тоже должен быть двумерным, например: int sum[N][N]; а суммы вычисляются следующим образом: for (int y = 1; y <= n; y++) { for (int x = 1; x <= n; x++) { sum[y][x] = max(sum[y][x-1],sum[y-1][x])+value[y][x]; 6.2. Другие примеры 95 } } Временная сложность этого алгоритм равна O(n 2 ). 6.2.3. Задачи о рюкзаке Под задачами о рюкзаке (или о ранце) понимаются задачи, в которых дано множество предметов и требуется найти подмножества, обладающие некоторыми свойствами. Часто такие задачи можно решить методом ди- намического программирования. В этом разделе нас будет интересовать такая задача: пусть дан список весов [w 1 , w 2 , …, w n ], требуется найти все суммы, которые можно получить сложением весов. На рис. 6.4 показаны возможные суммы для весов [1, 3, 3, 5]. В этом случае возможны все суммы от 0 до 12, за исключением 2 и 10. Например, сумма 7 возможна, потому что образована весами [1, 3, 3]. Рис. 6.4. Образование сумм с использованием весов [1, 3, 3, 5] Для решения задачи рассмотрим подзадачи, в которых для построения сумм используются только первые k весов. Положим possible (x, k)= true , если сумму x можно образовать из первых k весов, и possible (x, k)= false в противном случае. Значения функции можно вычислить рекурсивно по формуле possible (x, k)= possible (x − w k , k − 1)или possible (x, k − 1), основанной на том факте, что вес w k либо входит в сумму, либо нет. Если вес w k включается, то остается образовать сумму x − w k , используя только первые k − 1 весов, а если не включается, то требуется образовать сумму x, используя первые k − 1 весов. Базой рекурсии являются случаи true x = 0 possible (x, k) = � false x ≠ 0 , поскольку если веса вообще не используются, то можно образовать только сумму 0. Наконец, значение possible (x, n) сообщает, можно ли образовать сумму x, используя все веса. На рис. 6.5 показаны все значения функции для весов [1, 3, 3, 5] (сим- волом ✓обозначены значения true ). Например, глядя на строку k = 2, мы понимаем, что суммы [0, 1, 3, 4] можно образовать из весов [1, 3]. 96 Глава 6. Динамическое программирование Рис. 6.5. Решение задачи о рюкзаке для весов [1, 3, 3, 5] методом динамического программирования Обозначим m полную сумму весов. Показанной выше рекурсивной функции соответствует следующее решение методом динамического про- граммирования: possible[0][0] = true; for (int k = 1; k <= n; k++) { for (int x = 0; x <= m; x++) { if (x-w[k] >= 0) { possible[x][k] |= possible[x-w[k]][k-1]; } possible[x][k] |= possible[x][k-1]; } } Но есть и более компактный способ реализовать вычисление, применяя всего лишь одномерный массив possible [x ], показывающий, можно ли вы- брать подмножество весов, дающих в сумме x. Хитрость в том, чтобы для каждого нового веса обновлять массив справа налево: possible[0] = true; for (int k = 1; k <= n; k++) { for (int x = m-w[k]; x >= 0; x--) { possible[x+w[k]] |= possible[x]; } } Отметим, что общую идею динамического программирования, пред- ставленную в этом разделе, можно применить и к другим задачам о рюк- заке, например в случае, когда даны веса и ценности предметов и требу- ется найти подмножество с максимальной ценностью, соблюдая при этом ограничение на суммарный вес. 6.2. Другие примеры 97 6.2.4. От перестановок к подмножествам С помощью динамического программирования часто можно заменить итерирование по перестановкам итерированием по подмножествам. Вы- года здесь в том, что количество подмножеств 2 n значительно меньше ко- личества перестановок n!. Например, при n = 20 n! ≈ 2.4 · 10 18 , а 2 n ≈ 10 6 . Сле- довательно, для некоторых значений n все подмножества можно обойти эффективно, а все перестановки – нельзя. В качестве примера рассмотрим следующую задачу: имеется лифт с максимальной грузоподъемностью x и n человек, желающих подняться с первого на последний этаж. Пассажиры пронумерованы от 0 до n – 1, вес i -го пассажира равен weight [i ]. За какое минимальное количество поездок удастся перевезти всех на верхний этаж? Пусть, например, x = 12, n = 5 и веса таковы: • weight [0] = 2 • weight [1] = 3 • weight [2] = 4 • weight [3] = 5 • weight [4] = 9 В этом случае минимальное число поездок равно 2. Одно из оптималь- ных решений выглядит так: сначала перевезти пассажиров 0, 2 и 3 (сум- марный вес 11), а затем пассажиров 1 и 4 (суммарный вес 12). Задачу легко решить за время O(n!n), проверив все возможные переста- новки n человек. Но, применив динамическое программирование, мы смо- жем найти более эффективный алгоритм с временной сложностью O(2 n n ). Идея в том, чтобы для каждого подмножества пассажиров вычислить два значения: минимальное число необходимых поездок и минимальный вес пассажиров в последней группе. Обозначим rides (S)минимальное число поездок для подмножества S, а last (S) – минимальный вес последней группы в решении с минимальным числом поездок. Так, в примере выше rides ({3, 4})= 2 и last ({3, 4}) = 5, поскольку оптимальный способ поднять пассажиров 3 и 4 на последний этаж – везти их по отдельности, включив пассажира 4 в первую группу, тог- да будет минимизирован вес второй группы. Понятно, что наша конечная цель – вычислить значение rides ({0 … n − 1}). Мы можем вычислять значения функций рекурсивно, а затем приме- нить динамическое программирование. Чтобы вычислить значения для подмножества S, мы перебираем всех пассажиров, принадлежащих S, и производим оптимальный выбор последнего пассажира p, который вхо- дит в лифт. Каждый такой выбор порождает подзадачу с меньшим под- 98 Глава 6. Динамическое программирование множеством пассажиров. Если last (S \ p) + weight [ p] ≤ x, то мы можем вклю- чить p в последнюю группу. В противном случае придется выполнить еще одну поездку специально для p. Вычисление по методу динамического программирования удобно реали- зовать с помощью поразрядных операций. Сначала объявим массив pair<int,int> best[1< rides (S), last (S)). Для пустого подмножества поездки не нужны: best[0] = {0,0}; Заполнить массив можно следующим образом: for (int s = 1; s < (1< for (int p = 0; p < n; p++) { if (s&(1< auto option = best[s^(1< if (option.second+weight[p] <= x) { // добавить p в существующую группу пассажиров option.second += weight[p]; } else { // предусмотреть для p отдельную поездку option.first++; option.second = weight[p]; } best[s] = min(best[s], option); } } } Отметим, что этот цикл обладает следующим свойством: для любых двух подмножеств S 1 и S 2 – таких, что S 1 ⊂ S 2 , S 1 , – обрабатывается рань- ше S 2 . Следовательно, используемые в динамическом программировании значения вычисляются в правильном порядке. 6.2.5. Подсчет количества замощений Иногда состояния в решении методом динамического программиро- вания оказываются сложнее, чем фиксированные комбинации значений. В качестве примера рассмотрим задачу о нахождении количества различ- ных способов замостить сетку размера n×m плитками размера 1×2 и 2×1. 6.2. Другие примеры 99 Например, существует 781 способ замостить сетку 4×7, один из них пока- зан на рис. 6.6. Рис. 6.6. Один из способов заполнить сетку 4×7 плитками 1×2 и 2×1 Задачу можно решить методом динамического программирования, рас- сматривая сетку ряд за рядом. Каждый ряд в решении можно представить строкой, содержащей m символов из множества {⊓,⊔,⊏,⊐}. Так, решение, показанное на рис. 6.6, состоит из четырех рядов, которым соответствуют такие строки: • ⊓⊏⊐⊓⊏⊐⊓ • ⊔⊏⊐⊔⊓⊓⊔ • ⊏⊐⊏⊐⊔⊔⊓ • ⊏⊐⊏⊐⊏⊐⊔ Пронумеруем ряды сетки числами от 1 до n. Обозначим count (k, x) число таких решений для рядов 1…k, что ряду k соответствует строка x. Здесь можно воспользоваться динамическим программированием, потому что состояние ряда ограничено только состоянием предыдущего ряда. Решение допустимо, если ряд 1 не содержит символа ⊔, ряд n не содержит символа ⊓ и все соседние ряды совместимы. Например, ряды ⊔⊏⊐⊔⊓⊓⊔ и ⊏⊐⊏⊐⊔⊔⊓ совместимы, а ряды ⊓⊏⊐⊓⊏⊐⊓ и ⊏⊐⊏⊐⊏⊐⊔ – нет. Поскольку ряд состоит из m символов и каждый символ можно выбрать четырьмя способами, общее число различных рядов не превышает 4 m . Мы можем перебрать O(4 m )возможных состояний каждого ряда, и для каждого ряда существует O(4 m )возможных состояний предыдущего ряда, поэтому временная сложность решения равна O(n4 2 m ). На практике разумно повер- нуть сетку, так чтобы более короткая сторона имела длину m, поскольку множитель 4 2 m доминирует в оценке сложности. Эффективность решения можно повысить, представив ряды в более компактной форме. Оказывается, что достаточно знать, какие колонки предыдущей строки содержат верхний квадратик вертикальной плитки. Поэтому для представления ряда достаточно символов ⊓ и ⎕, где ⎕ – ком- бинация символов ⊔, ⊏ и ⊐. При таком представлении существует всего 2 m различных строк, так что временная сложность равна O(n2 2 m ). 100 Глава 6. Динамическое программирование Напоследок отметим, что существует явная формула для количества за- мощений: / 2 / 2 2 2 1 1 4 cos cos 1 1 n m a b a b n m π π = = ⋅ + + + ∏ ∏ Эта формула очень эффективна, поскольку вычисляет количество замо- щений за время O(nm), но, так как ответ выражается как произведение ве- щественных чисел, возникает проблема: как точно представлять промежу- точные результаты. |