анти. Guide to Competitive
 Скачать 2.39 Mb.
|
|
Рис. 15.19. Разбиение массива на два Слияние. Операция слияния двух дуч создает новую дучу, соответствую- щую конкатенации двух массивов. Обе дучи обрабатываются одновремен- но, и на каждом шаге выбирается дуча с наименьшим весом корня. Если вес корня левой дучи меньше, то сам корень и его левое поддерево пере- мещаются в новую дучу, а его правое поддерево становится новым корнем 296 Глава 15. Дополнительные темы левой дучи. Аналогично, если корень правой дучи меньше, то сам корень и его правое поддерево перемещаются в новую дучу, а его левое поддере- во становится новым корнем правой дучи. Поскольку высота дучи равна O(log n), эта операция занимает время O(log n). Например, мы можем поменять местами два массива, а затем снова конкатенировать их. На рис. 15.20 показаны массивы до слияния, а на рис. 15.21 – конечный результат. Сначала вершина D и ее правое поддере- во добавляются в новую дучу. Затем вершина A и ее правое поддерево ста- новятся левым поддеревом вершины D. После этого вершина C и ее левое поддерево становятся левым поддеревом вершины A. Наконец, в новую дучу добавляются вершины H и S. I C H S A N D W 0 1 2 0 1 2 3 4 9 S 3 A 6 N 1 D 8 W 9 I 4 C 5 H I C H S A N D W 0 1 2 3 4 5 6 7 9 S 3 A 6 N 1 D 8 W 9 I 4 C 5 H Рис. 15.20. Слияние двух массивов в один: до начала слияния Рис. 15.21. Слияние двух массивов в один: после слияния 15.3.2. Реализация Далее мы рассмотрим удобный способ реализации дучи. Ниже показана структура для хранения вершины дучи: struct node { node *left, *right; int weight, size, value; node(int v) { left = right = NULL; weight = rand(); size = 1; value = v; } }; 15.3. Дучи 297 В поле size хранится размер поддерева вершины. Поскольку вершина может быть равна NULL , полезна следующая функция: int size(node *treap) { if (treap == NULL) return 0; return treap->size; } Показанная ниже функция split реализует операцию разбиения. Она рекурсивно разбивает дучу treap на дучи left и right , так что левая дуча содержит первые k вершин и правая – все остальные. void split(node *treap, node *&left, node *&right, int k) { if (treap == NULL) { left = right = NULL; } else { if (size(treap->left) < k) { split(treap->right, treap->right, right, k-size(treap->left)-1); left = treap; } else { split(treap->left, left, treap->left, k); right = treap; } treap->size = size(treap->left)+size(treap->right)+1; } } Функция merge реализует операцию слияния. Она создает дучу treap , ко- торая содержит сначала вершины дучи left , а затем – вершины дучи right void merge(node *&treap, node *left, node *right) { if (left == NULL) treap = right; else if(right == NULL) treap = left; else { if (left->weight < right->weight) { merge(left->right, left->right, right); treap = left; } else { merge(right->left, left, right->left); treap = right; } treap->size = size(treap->left)+size(treap->right)+1; } } 298 Глава 15. Дополнительные темы Например, в следующем фрагменте создается дуча, соответствующая массиву [1, 2, 3, 4]. Затем она разбивается на две дучи размера 2, которые переставляются местами, в результате чего создается дуча, соответствую- щая массиву [3, 4, 1, 2]. node *treap = NULL; merge(treap, treap, new node(1)); merge(treap, treap, new node(2)); merge(treap, treap, new node(3)); merge(treap, treap, new node(4)); node *left, *right; split(treap, left, right, 2); merge(treap, right, left); 15.3.3. Дополнительные методы Операции разбиения и слияния дуч весьма эффективны, поскольку по- зволяют произвольным образом «вырезать и копировать» массивы за ло- гарифмическое время. Но дучи можно еще обобщить, так что они будут работать, почти как деревья отрезков. Например, помимо хранения размера каждого поддерева, мы можем также хранить сумму значений в нем, мини- мальное значение и т. д. В частности, с помощью дуч можно выполнить интересный трюк: обратить массив. Для этого нужно переставить местами левого и правого потомков каж дой вершины в дуче. На рис. 15.22 показано, что получается после обраще- ния массива на рис. 15.18. Чтобы сделать это эффективно, мы можем ввести поле, которое показывает, следует ли обра- щать поддерево вершины, и выполнять операции перестановки лениво. 15.4. Оптимизация динамического программирования В этом разделе обсуждаются методы оптимизации динамического про- граммирования. Сначала мы рассмотрим трюк с выпуклой оболочкой, ко- торым можно воспользоваться для эффективного нахождения минималь- H C I W D N A S 0 1 2 3 4 5 6 7 9 S 3 A 6 N 1 D 8 W 9 I 4 C 5 H Рис. 15.22. Обращение массива с помощью дучи 15.4. Оптимизация динамического программирования 299 ного значения семейства линейных функций. Затем мы обсудим еще два приема, основанных на свойствах функций стоимости. 15.4.1. Трюк с выпуклой оболочкой Трюк с выпуклой оболочкой (convex hull trick)позволяет эффективно найти минимальное значение в заданной точке x семейства n линейных функций вида f(x)= ax + b. На рис. 15.23 показаны функции f 1 (x)= x + 2, f 2 (x)= x/3 + 4, f 3 (x)= x/6 + 5 и f 4 (x)= −x/4 + 7. Минимальное значение в точке x = 4 принимает функция f 2 (4) = 16/3. f 1 f 2 f 3 f 4 x = 4 Рис. 15.23. Минимальное значение семейства функций в точке x = 4 равно f 2 (4) = 16/3 Идея заключается в том, чтобы разбить ось x на диапазоны, в которых некоторая функция меньше всех остальных. Оказывается, что для каждой функции есть не более одного такого диапазона, и мы можем сохранить их в отсортированном списке, содержащем не более n диапазонов. На рис. 15.24 показаны диапазоны для нашего примера. Сначала наимень- шей является функция f 1 , затем f 2 и, наконец, f 4 . Отметим, что f 3 ни в одной точке не принимает значение, которое было бы меньше значений всех остальных функций. Имея список диапазонов, мы можем найти минимальное значение се- мейства функций в точке x за время O(log n), применив двоичный поиск. Например, поскольку на рис. 15.24 точка x = 4 принадлежит диапазону функции f 2 , мы сразу заключаем, что минимальное значение в этой точке принимает функция f 2 , и оно равно f 2 (4)= 16/3. Таким образом, множество k запросов можно обработать за время O(k log n). Кроме того, если запро- сы следуют в порядке возрастания, то их можно обработать за время O(k), просто обходя диапазоны слева направо. 300 Глава 15. Дополнительные темы f 1 f 2 f 3 f 4 f 1 f 2 f 4 Рис. 15.24. Диапазоны, в которых минимальны функции f 1 , f 2 и f 4 Но как определить эти диапазоны? Если функции заданы в порядке убы- вания коэффициентов наклона, то диапазоны найти легко, поскольку мы можем вести стек диапазонов. Тогда амортизированная стоимость обра- ботки каждой функции равна O(1). Если функции можно задавать в про- извольном порядке, то потребуется более сложная структура множества, и обработка каждой функции займет время O(log n). Пример. Пусть имеется n последовательных концертов. Билет на i-й концерт стоит p i рублей, а если мы посещаем этот концерт, то получаем скидочный купон величиной d i (0 < d i < 1). Впоследствии этот купон можно использовать для покупки билета за d i p рублей вместо p. Известно так- же, что d i ≥ d i +1 для всех последовательных концертов i и i + 1. Мы хотим обязательно посетить последний концерт, но не против посетить также и другие. В какую минимальную цену мы можем уложиться? Эту задачу легко решить методом динамического программирования, если вычислять для каждого концерта i значение u i – минимальную цену посещения концерта i и, возможно, некоторых других. Чтобы найти оп- тимальный выбор для некоторого концерта, мы можем просто перебрать все предыдущие концерты за время O(n), так что в итоге получается алго- ритм с временной сложностью O(n 2 ). Однако, воспользовавшись трюком с выпуклой оболочкой, мы сможем найти оптимальное решение за время O(log n)и получить алгоритм с временной сложностью O(n log n). Идея заключается в том, чтобы построить семейство линейных функ- ций, первоначально содержащее только функцию f(x)= x, означающую, что скидочного купона нет. Чтобы вычислить значение u i для некоторого кон- церта, мы найдем в нашем семействе функцию f, для которой достигается минимум f(p i ); это можно сделать за время O(log n), применив трюк с вы- пуклой оболочкой. Затем мы добавляем в семейство функцию f(x)= d i x + u i и можем использовать ее для посещения какого-то из последующих кон- цертов. Этот алгоритм работает за время O(n log n). 15.4. Оптимизация динамического программирования 301 Отметим, что если дополнительно известно, что p i ≤ p i +1 для всех сосед- них концертов i и i + 1, то задачу можно решить еще эффективнее за время O(n), поскольку мы можем не использовать двоичный поиск, а обработать диапазоны слева направо и найти оптимальное решение за амортизиро- ванное постоянное время. 15.4.2. Оптимизация методом «разделяй и властвуй» Оптимизация методом «разделяй и властвуй» применима к некоторым задачам динамического программирования, когда последовательность n элементов s 1 , s 2 , …, s n нужно разбить на k подпоследовательностей, состоя- щих из соседних элементов. Задана функция cost (a, b), которая определяет стоимость создания подпоследовательности s a , s a +1 , …, s b . Общая стоимость разбиения равна сумме стоимостей отдельных подпоследовательностей, а наша задача состоит в том, чтобы найти разбиение, минимизирующее общую стоимость. Предположим, к примеру, что имеется последовательность положитель- ных целых чисел и cost (a, b)= (s a + s a +1 + … + s b ) 2 . На рис. 15.25 показан оп- тимальный способ разбить последовательность на три подпоследователь- ности при такой функции стои мости. Общая стоимость этого разбиения равна (2 + 3 + 1) 2 + (2 + 2 + 3) 2 + (4 + 1) 2 = 110. Для решения задачи определим функцию solve (i, j), которая дает мини- мальную общую стоимость разбиения первых i элементов s 1 , s 2 , ..., s i на j подпоследовательностей. Очевидно, что значение solve (n, k) и есть ответ на вопрос. Чтобы вычислить solve (i, j), мы должны найти индекс 1 ≤ p ≤ i, при котором достигается минимум выражения solve (p − 1, j − 1)+ cost (p, i). На рис. 15.25 оптимальным решением для solve (8, 3)является p = 7. Чтобы найти его, можно просто проверить все индексы 1, 2, …, i, что зай мет время O(n). Если таким образом вычислять все значения solve (i, j), то мы получим алгоритм динамического программирования с временной сложно- стью O(n 2 k). Однако, применив оптими- зацию методом «разделяй и власт вуй», мы можем улучшить временную сложность до O(nk log n). Такую оптимизацию можно использовать, если функция стоимости удовлетворяет неравенству четырехугольника cost (a, c) + cost (b, d) ≤ cost (a, d) + cost (b, c) для любых a ≤ b ≤ c ≤ d. Обозначим pos (i, j)наименьший индекс p, при ко- тором достигается минимум стоимости разбиения для solve (i, j). Если 2 3 1 2 2 3 4 1 1 2 3 4 5 6 7 8 Рис. 15.25. Оптимальный способ разбить последовательность на три блока 302 Глава 15. Дополнительные темы приведенное выше неравенство удовлетворяется, то гарантируется, что pos (i, j)≤ pos (i + 1, j)для всех i и j, что позволяет вычислять значения solve (i, j)более эффективно. Идея заключается в том, чтобы определить функцию calc (j, a, b, x, y), которая вычисляет все значения solve (i, j)для a ≤ i ≤ b и фиксированно- го j, пользуясь тем фактом, что x ≤ pos (i, j)≤ y. Функция сначала вычисляет solve (z, j),где z = ⌊(a + b)/2⌋, а затем рекурсивно вызывает calc (j, a, z − 1, x, p) и calc (j, z + 1, b, p, y), где p = pos (z, j). Тот факт, что pos (i, j)≤ pos (i + 1, j),ис- пользуется для ограничения области поиска. Для вычисления всех значе- ний solve (i, j) мы выполняем вызов calc (j,1, n,1, n)для каждого j = 1, 2, …, k. Поскольку каждый такой вызов занимает время O(n log n), построен ный алгоритм имеет временную сложность O(nk log n). Наконец, докажем, что используемая в нашем примере функция стои- мости – сумма квадратов – удовлетворяет неравенству четырехугольника. Обозначим sum (a, b)сумму значений в диапазоне [a, b], и пусть x = sum (b, c), y = sum (a, c)− sum (b, c), z = sum (b, d)− sum (b, c). В этих обозначениях неравен- ство четырехугольника принимает вид (x + y) 2 + (x + z) 2 ≤ (x + y + z) 2 + x 2 , что эквивалентно неравенству 0 ≤ 2yz. Поскольку y и z неотрицательны, утверждение доказано. 15.4.3. Оптимизация Кнута Оптимизацию Кнута 3 можно использовать для решения некоторых задач динамического программирования, в которых требуется разбить последовательность n элементов s 1 , s 2 , …, s n на отдельные элементы, при- меняя операции разделения. Функция стоимости cost (a, b)определяет стоимость обработки последовательности s a , s a +1 , …, s b , а наша задача – най- ти решение, минимизирующее суммарную стоимость разделения. Пусть, например, cost (a, b)= s a + s a +1 + … + s b . На рис. 15.26 показан оп- тимальный способ обработки последовательности в этом случае. Полная стоимость этого решения равна 19 + 9 + 10 + 5 = 43. Эту задачу можно решить, определив функцию solve (i, j), которая дает минимальную стоимость разбиения последовательности s i , s i +1 , …, s j на от- дельные элементы. Тогда значение solve (1, n)дает искомый ответ. Чтобы вычислить значение solve (i, j), мы должны найти индекс i ≤ p < j, при кото- ром достигает минимума величина cost (i, j) + solve (i, p) + solve (p + 1, j). 3 Кнут [23] применил эту оптимизацию для построения оптимального двоичного дерева поиска. Впоследствии Яо [36] обобщил предложенный подход на другие похожие задачи. 15.5. Методы перебора с возвратом 303 2 7 3 2 5 cost: 19 2 7 3 2 5 cost: 9 2 7 3 2 5 cost: 10 2 7 3 2 5 cost: 5 2 7 3 2 5 Стоимость: 19 Стоимость: 9 Стоимость: 10 Стоимость: 5 Рис. 15.26. Оптимальный способ разбиения массива на отдельные элементы Если мы будем проверять все индексы между i и j, то получим задачу динамического программирования с временной сложностью O(n 3 ). А с по- мощью оптимизации Кнута мы сможем вычислить значения solve (i, j)бо- лее эффективно за время O(n 2 ). Оптимизация Кнута применима, если cost (b, c) ≤ cost (a, d) и cost (a, c) + cost (b, d) ≤ cost (a, d) + cost (b, c) для любых a ≤ b ≤ c ≤ d. Отметим, что второе неравенство – не что иное, как неравенство четырехугольника, которое встречалось и в оптимизации методом «разделяй и властвуй». Обозначим pos (i, j) наименьший индекс p, при котором достигается минимум стоимости вычисления solve (i, j). Если приведенные выше неравенства удовлетворяются, то pos (i, j − 1) ≤ pos (i, j) ≤ pos (i + 1, j). Теперь можно выполнить n раундов – 1, 2, …, n – вычисляя на k-м раунде значения solve (i, j), где j − i + 1 = k, т. е. обрабатывать подпоследовательно- сти в порядке возрастания длины. Поскольку известно, что pos (i, j)должно быть заключено между pos (i, j − 1) и pos (i + 1, j), то каждый раунд можно выполнить за время O(n), и полная временная сложность алгоритма ока- зывается равна O(n 2 ). |