анти. Guide to Competitive
 Скачать 2.39 Mb.
|
|
15.5. Методы перебора с возвратом В этом разделе мы покажем, как ускорить работу алгоритмов перебора с возвратом. Сначала рассмотрим задачу о подсчете количества путей на 304 Глава 15. Дополнительные темы сетке и попробуем улучшить алгоритм с помощью отсечения ветвей де- рева поиска. Затем решим задачу об игре в 15, применив алгоритм IDA * и эвристические функции. 15.5.1. Отсечение ветвей дерева поиска Многие алгоритмы перебора с возвратом можно улучшить путем отсе- чения ветвей дерева поиска: заметив, что частичное решение нельзя про- должить до полного, не имеет смысла продолжать поиск. Рассмотрим задачу о вычислении количества путей на доске 7×7 таких, что каждый путь начи- нается в левом верхнем углу, заканчивается в пра- вом нижнем углу и заходит в каждую клетку ровно один раз. Один такой путь показан на рис. 15.27, а всего их, как можно показать, 111 712. Мы начнем с простого алгоритма перебора с воз- вратом, а затем постепенно оптимизируем его, за- метив, как можно сократить поиск. После каждой оптимизации будем измерять время работы алго- ритма и количество рекурсивных вызовов, чтобы оценить влияние оптимизации на эффективность поиска. Базовый алгоритм. В первой версии алгоритма нет никаких оптими- заций. Мы просто пользуемся перебором с возвратом, чтобы породить все возможные пути из левого верхнего угла в правый нижний, и подсчиты- ваем число таких путей. • Время работы: 483 с. • Количество рекурсивных вызовов: 76 · 10 9 Оптимизация 1. В любом решении мы сначала делаем один шаг вниз или вправо, и существует два пути, симметричных относительно диагона- ли доски. Например, пути на рис. 15.28 симметричны. Поэтому мы можем всегда делать первый шаг вниз (или, наоборот, вправо), а в конце умно- жить количество решений на два. • Время работы: 244 с. • Количество рекурсивных вызовов: 38 · 10 9 Оптимизация 2. Если путь заходит в правый нижний угол, не посетив все остальные клетки, то очевидно, что получить корректное решение уже не удастся. Пример показан на рис. 15.29. Следовательно, поиск можно за- вершать немедленно, если мы попали в правую нижнюю клетку слишком рано. Рис. 15.27. Путь из левого верхнего угла в правый нижний 15.5. Методы перебора с возвратом 305 • Время работы: 119 с. • Количество рекурсивных вызовов: 20 · 10 9 Рис. 15.28. Два пути, симметричных относительно диагонали Рис. 15.29. Мы дошли до правого нижнего угла, не посетив все остальные клетки Оптимизация 3. Если путь упирается в край и может повернуть как налево, так и направо, то дос ка оказалась разбита на две части, в каждой из которых есть непосещенные клетки. Например, путь на рис. 15.30 может повернуть налево или на- право. В таком случае нам точно не удастся посе- тить все клетки, поэтому можно завершать поиск. Эта оптимизация оказалась очень полезной. • Время работы: 1,8 с. • Количество рекурсивных вызовов: 221 · 10 6 Оптимизация 4. Идею предыдущей оптимиза- ции можно обобщить: если путь нельзя продол- жить вперед, но можно повернуть налево или направо, то доска разбива- ется на две части, каждая из которых содержит непосещенные клетки. На рис. 15.31 приведен пример такого случая. Очевидно, что нам не удастся посетить все клетки, поэтому можно завершать поиск. После этой оптими- зации поиск становится очень эффективным. Рис. 15.30. Путь разбивает доску на две части, содержащие непосещенные клетки 306 Глава 15. Дополнительные темы • Время работы: 0,6 с. • Количество рекурсивных вызовов: 69 · 10 6 Вывод. Теперь самое время прекратить попыт- ки оптимизации алгоритма и посмотреть, чего мы достигли. Время работы первой версии алгоритма составляло 483 с, а после всех оптимизаций умень- шилось до 0,6 с. То есть благодаря оптимизациям алгоритм стал работать почти в 1000 раз быстрее. Это типично для перебора с возвратом, потому что дерево поиска обычно велико, и даже простые наблюдения могут заметно уменьшить количество ветвей в нем. Особенно полезны оптимизации на первых шагах алгоритма, т. е. в самом начале дерева поиска. 15.5.2. Эвристические функции В некоторых задачах перебора с возвратом мы ищем оптимальное ре- шение, например самую короткую последовательность ходов. В таких слу- чаях поиск можно улучшить, воспользовавшись эвристической функцией, которая оценивает расстояние от текущего состояния поиска до конечного состояния. В игре в 15 имеется доска 4×4, а на ней 15 костяшек (с числами от 1 до 15), так что одна клетка пустая. На каждом ходе мы можем выбрать любую костяшку, со- седнюю с пустой клеткой, и переместить ее в пустую клетку. Мы хотим найти минимальное количество хо- дов, требуемое для получения конечной позиции, по- казанной на рис. 15.32. Для решения задачи мы воспользуемся алгоритмом IDA * , который состоит из нескольких поисков методом перебора с возвратом. В каждом поиске мы пытаемся найти решение с количеством ходов не более k. Вначале k равно 0, и после каждого неудачного поиска увеличи- вается на 1. В алгоритме используется эвристическая функция, которая оценивает количество ходов, оставшееся до конца игры. Эвристическая функция должна быть допус- тимой, т. е. она никогда не должна давать завышенной оценки числа ходов. Таким образом, с ее помощью мы получаем нижнюю границу числа ходов. Для примера рассмотрим позицию на рис. 15.33. Как выясняется, минимальное число ходов в ней равно 61. Рис. 15.31. Более общая ситуация, когда путь разбивает доску на две части 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Рис. 15.32. Конечная позиция в игре в 15 11 3 12 9 8 15 6 5 14 10 2 7 13 1 4 Рис. 15.33. Минимальное количество ходов в этой позиции равно 61 15.5. Методы перебора с возвратом 307 Поскольку в каждом состоянии имеется от 2 до 4 возможных ходов в зави- симости от положения пустой клетки, бесхитростный алгоритм перебора с возвратом занял бы слишком много времени. По счастью, алгоритм IDA * включает эвристическую функцию, которая значительно ускоряет поиск. Далее мы рассмотрим несколько эвристических функций и измерим время работы алгоритма и количество рекурсивных вызовов. Во всех эв- ристиках мы реализуем перебор с возвратом таким образом, что преды- дущий ход никогда не отменяется, потому что это не привело бы к опти- мальному решению. Эвристика 1. Простая эвристика заключается в том, чтобы для каждого квадратика вычислить манхэттенское расстояние от его текущего поло- жения до конечного. Манхэттенское расстояние вычисляется по формуле |x c − x f | + |y c − y f |, где (x c , y c )– текущее положение квадратика, а (x f , y f ) – его конечное положение. Нижнюю границу числа ходов мы получим, просум- мировав все такие расстояния, поскольку каждый ход изменяет положе- ние костяшки по вертикали или по горизонтали на 1. • Время работы: 126 с. • Число рекурсивных вызовов: 1,5 · 10 9 Эвристика 2. Эвристику получше мы создадим, сконцентрировав вни- мание на костяшках, которые уже находятся в правильной строке или пра- вильном столбце. Рассмотрим костяшки 6 и 8 в нашем примере. Они уже стоят в правильной строке, правда, не в том порядке. Чтобы поменять по- рядок, нужно будет сдвинуть одну из них по вертикали, что добавляет два хода. Таким образом, мы можем улучшить эвристику следующим образом: сначала вычислить сумму манхэттенских расстояний, а затем добавить два дополнительных хода для каждой строки или столбца, где две костяш- ки, находящиеся в своей строке (своем столбце), но неправильно располо- женные друг относительно друга. • Время работы: 22 с. • Число рекурсивных вызовов: 1,43 · 10 8 Эвристика 3. Мы можем еще улучшить предыдущую эвристику: если имеется больше двух костяшек, находящихся в правильной строке или в правильном столбце, то, возможно, мы сможем добавить еще два допол- нительных хода. Например, рассмотрим костяшки 5, 6 и 8. Поскольку они стоят в порядке, обратном нужному, нам придется сдвинуть по крайней мере две из них по вертикали, что даст четыре дополнительных хода. Вообще, если имеется c 1 костяшек, занимающих правильную строку или столбец, и не более c 2 из них стоят в нужном порядке, то можно добавить 2(c 1 − c 2 ) дополнительных ходов. 308 Глава 15. Дополнительные темы • Время работы: 39 с. • Число рекурсивных вызовов: 1,36 · 10 8 Вывод. А что случилось? Мы улучшили эвристику, но время работы ал- горитма увеличилось с 22 с до 39 с. Хорошая эвристика обладает двумя свойствами: она дает нижнюю гра- ницу, близкую к истинному расстоянию, и может быть эффективно вычис- лена. Последняя эвристика точнее предпоследней, но ее труднее вычис- лить, поэтому в данном случае более простая эвристика предпочтительнее. 15.6. Разное В этом разделе представлена подборка методов проектирования алго- ритмов. Мы обсудим технику встречи в середине, алгоритм динамиче- ского программирования для подсчета подмножеств, метод параллель- ного двоичного поиска и пакетное решение задачи о динамической связности. 15.6.1. Встреча в середине Идея техники встречи в середине состоит в том, чтобы разбить простран- ство поиска на две части приблизительно равного размера, выполнить поиск в каждой части, а затем объединить результаты двух поисков. Эта техника позволяет ускорить некоторые алгоритмы с временной сложно- стью O(2 n ), уменьшив время работы до O(2 n /2 ). Отметим, что O(2 n /2 ) гораздо быстрее, чем O(2 n ), поскольку 2 n /2 = √2 n . С помощью алгоритма с времен- ной сложностью O(2 n )мы можем обработать входные данные, для которых n ≈ 20, а если временная сложность уменьшается до O(2 n /2 ), то оценка n возрастает до n ≈ 40. Пусть дано множество n целых чисел и требуется определить, существу- ет ли в нем подмножество с суммой x. Например, если дано множество {2, 4, 5, 9} и x = 15, то мы можем выбрать подмножество {2, 4, 9}, поскольку 2 + 4 + 9 = 15. Эту задачу легко решить за время O(2 n ), перебрав все возмож- ные подмножества, но мы решим ее более эффективно за время O(2 n /2 ), воспользовавшись техникой встречи в середине. Идея в том, чтобы разделить наше множество на два подмножества A и B, так чтобы в каждом была примерно половина чисел. Мы выполняем два поиска: первый порождает все подмножества A и сохраняет их суммы в списке S A , второй создает аналогичный список S B для B. После этого доста- точно проверить, можно ли выбрать один элемент из S A и другой элемент из S B , так чтобы их сумма была равна x; это возможно тогда и только тогда, когда в исходном множестве имеется подмножество с суммой x. Посмотрим, к примеру, как обрабатывается множество {2, 4, 5, 9}. Сна- чала мы разбиваем множество на два подмножества A = {2, 4} и B = {5,9}. 15.6. Разное 309 После этого создаем списки S A = [0, 2, 4, 6] и S B = [0, 5, 9, 14]. Поскольку S A содержит сумму 6, а S B содержит сумму 9, мы заключаем, что в исходном множестве имеется подмножество с суммой 6 + 9 = 15. При хорошей реализации списки S A и S B можно создать за время O(2 n /2 ) таким образом, что оба списка будут отсортированы. После этого можно воспользоваться алгоритмом двух указателей и за время O(2 n /2 ) проверить, можно ли составить сумму x из двух слагаемых, взятых по одному из S A и S B Таким образом, полная временная сложность алгоритма равна O(2 n /2 ). 15.6.2. Подсчет подмножеств Пусть X = {0 … n − 1}, и каждому подмножеству S ⊂ X сопоставлена цен- ность – целое число value [ S]. Требуется для каждого S вычислить sum [ S] = A S ⊂ ∑ value [ A], т. е. сумму ценностей подмножеств S. Пусть, например, n = 3 и ценности таковы: • value [ ∅] = 3; • value [{2}] = 5; • value [{0}] = 1; • value [{0, 2}] = 1; • value [{1}] = 4; • value [{1, 2}] = 3; • value [{0,1}] = 5; • value [{0, 1, 2}] = 3. Тогда sum ( {0, 2}) = value [ ∅] + value [{0}] + value [{2}] + value [{0, 2}] = 3 + 1 + 5 + 1 = 10. Ниже мы покажем, как решить эту задачу за время O(2 n n ), применив ди- намическое программирование и поразрядные операции. Идея в том, что- бы рассмотреть подзадачи, в которых имеются ограничения на то, какие элементы можно удалять из S. Обозначим partial (S, k)сумму ценностей подмножеств S с тем ограни- чением, что удалять из S можно только элементы 0 … k. Например, partial ({0, 2}, 1) = value [{2}] + value [{0, 2}], поскольку разрешено удалять лишь элементы 0 …1. Отметим, что, зная partial , мы можем вычислить любое значение sum (S), потому что sum (S)= partial (S, n − 1). Чтобы воспользоваться динамическим программированием, мы долж- ны найти рекуррентное соотношение для partial . Базой рекурсии являет- ся случай partial (S, −1)= value [ S], 310 Глава 15. Дополнительные темы поскольку из S нельзя удалить ни одного элемента. А в общем случае имеет место соотношение: partial (S, k − 1) k ∉ S partial (S, k) = � partial (S, k − 1) + partial (S \ { k}, k − 1) k ∈ S Здесь наше внимание направлено на элемент k. Если k ∈ S, то есть два варианта: либо мы оставляем k в подмножестве, либо удаляем из подмно- жества. Реализация. Существует очень красивый способ реализовать решение методом динамического программирования с помощью поразрядных операций. А именно объявим массив: int sum[1< for (int s = 0; s < (1< } После этого массив заполняется так: for (int k = 0; k < n; k++) { for (int s = 0; s < (1< } Здесь мы записываем вычисленные значения partial (S, k)для k = 0 … n − 1 в массив sum . Поскольку partial (S, k)зависит только от partial (S, k − 1), то мы можем использовать массив sum повторно, что дает очень эффектив- ную реализацию. 15.6.3. Параллельный двоичный поиск Техника параллельного двоичного поиска позволяет повысить эффектив- ность некоторых алгоритмов, основанных на двоичном поиске. Общая идея заключается в том, чтобы выполнять несколько двоичных поисков одновременно, а не по отдельности. Рассмотрим следующую задачу. Имеется n городов, пронумерованных 1, 2, …, n. Первоначально между городами нет дорог. Затем каждый день в течение m дней между какими-то двумя городами строится новая дорога. И наконец, дано k запросов вида (a, b), а наша задача – для каждого запроса определить самый ранний момент, когда можно будет проехать между го- 15.6. Разное 311 родами a и b. Мы можем предполагать, что все встречающиеся в запросах пары городов будут соединены через m дней. На рис. 15.34 приведен пример для четырех городов. Предположим, что предъявлены запросы q 1 = (1, 4) и q 2 = (2, 3). Ответ на запрос q 1 равен 2, по- скольку города 1 и 4 оказываются соединены на второй день, а на запрос q 2 – 4, поскольку города 2 и 3 будут соединены на четвертый день. Сначала рассмотрим более простую задачу, когда имеется всего один запрос (a, b). В этом случае можно воспользоваться системой непересека- ющихся множеств для моделирования процесса добавления дорог. После строительства каждой новой дороги мы проверяем, соединены ли города a и b, и если да, то останавливаемся. Как добавление новой дороги, так и проверка наличия соединения занимают время O(log n), поэтому алго- ритм имеет временную сложность O(m log n). 1 2 3 4 День 1 1 2 3 4 День 2 1 2 3 4 День 3 1 2 3 4 День 4 Рис. 15.34. Пример задачи о строительстве дороги Как обобщить это решение на k запросов? Конечно, можно было бы об- рабатывать каждый запрос по отдельности, но такой алгоритм потребовал бы времени O(km log n) – слишком много, если k и m велики. Ниже мы покажем, как решить задачу более эффективно, воспользовавшись парал- лельным двоичным поиском. Идея в том, чтобы сопоставить каждому запросу диапазон [x, y], озна- чающий, что первое соединение между городами появляется не раньше, чем на x-й день, и не позже, чем на y-й день. Вначале все диапазоны равны [1, m]. Теперь log m раз смоделируем процесс добавления всех дорог в сеть, применяя систему непересекающихся множеств. Для каждого запроса проверяем, соединены ли города в момент u = ⌊(x + y)/2⌋. Если да, то новым диапазоном становится [x, u], иначе [u + 1, y]. После log m раундов каждый |