Алгоритмы - построение и анализ (1021735), страница 74
Текст из файла (страница 74)
Доказательство. Цикл твййе в строках 2-5 завершается, если х = ит2 [Т] либо если 1 перекрывается с гит (х]. В последнем случае процедура тривиально возвращает значение х. Поэтому нас интересует первый случай, когда цикл завершается из-за того, что х = ит2 [Т]. Воспользуемся следующим инвариантом цикла и'Ы1е в строках 2-5. Если дерево Т содержит отрезок, который перекрывается с г, то этот отрезок находится в поддереве, корнем которого является узел х. Глава 14. Расширение структур данных 379 ) г 1 — — 4 а) б) Рис. 14.5. Отрезки в доказательстве теоремы 14.2. Пунктирной линией показана величина тах [1еф [х]] Инициализация.
Перед выполнением первой итерации в строке 1 переменной х присваивается указатель на корень дерева, так что инвариант выполняется. Сохранение. Прн каждой итерации цикла згЫ)е выполняется либо строка 4, либо строка 5. Покажем, что инвариант цикла сохраняется в любом случае. При выполнении строки 5 (в силу невыполнения условия в строке 3) мы имеем 1е)г [х] = п11 [Т] или тах [1ефх]] < 1ою [1]. Если 1е]1 [х] = п11 ]Т], то поддерево, корнем которого является 1е~1 [х]„очевидно, не может содержать отрезок, перекрывающийся с г, так что присвоение х — пдЬ1 [х] сохраняет инвариант цикла. Предположим, следовательно, что 1еГ1 [х] ~~ п11 [Т] и тах [1ег1[х]] < 1ою [1]. Как показано на рис. 14.5а, для каждого интервала з' из левого поддерева х выполняется следующее соотношение: БлдЬ [1] (~ тах[1еф [х]] < 1ою [1].
В соответствии со свойством трихотомии отрезков, 1' и 1 не перекрываются. Таким образом, левое поддерево х не содержит отрезков, перекрывающихся с г, и присвоение х — г1дЬ1 [х] сохраняет инвариант. Пусть выполняется строка 4. В этом случае мы покажем, что если в левом поддереве х нет отрезка, перекрывающегося с г, то его вообще нет в дереве. Строка 4 выполняется в случае, когда тах [1е)т [хЦ > 1ою [1].
Кроме того, по определению поля тах в левом поддереве х должен быть некоторый интервал 1', такой что Ь1дЬ [1'] = тах [1ег1 [х]] > 1ою [1]. (Данная ситуация проиллюстрирована на рис. 14.5б.) Поскольку 1 и 1' не перекрываются и поскольку неверно, что Ь1дЬ [1'] < < 1ою [1], отсюда в соответствии со свойством трихотомии отрезков следует, что Ь19Ь [1] < 1ою [г'].
Поскольку дерево отрезков упорядочено в соответствии с левыми концами отрезков, из свойства дерева поиска вытекает, что для любого отрезка га нз правого поддерева х Ь1дЬ [1] < 1ою [1'] < 1ою [1"] . 380 Часть 111. Структуры данных Из трихотомии отрезков следует, что 1 и гв не перекрываются. Мы можем, таким образом, заключить, что независимо от того, имеется ли в левом поддереве х отрезок, перекрывающийся с г, присвоение х — 1еу2 [х] сохраняет инвариант цикла.
Завершение. Если цикл завершается по условию х = пп [Т], то в дереве, корнем которого является х, нет отрезков, перекрывающихся с г. Обращение инварианта цикла приводит к заключению, что дерево Т не содержит отрезков, перекрывающихся с г. Следовательно, возвращаемое процедурой значение пя [Т] совершенно корректно. Итак, процедура 1нтекчле 8елксн работает корректно.
Упражнения 14.3-1. Напишите псевдокод процедуры 1.еет Нотлте, которая работает с узлами дерева отрезков и обновляет поля тах за время О (1). 14.3-2. Перепишите код процедуры 1нтекчлг. Белксн для корректной работы с интервалами (отрезками без конечных точек). 14.3-3. Разработайте эффективно работающий алгоритм, который для данного отрезка г возвращает отрезок, перекрывающийся с г и имеющий минимальное значение левого конца (либо п11 [Т], если такого отрезка не существует). 14.3-4. Пусть у нас имеется дерево отрезков Т и отрезок 1. Опишите, каким образом найти все отрезки в дереве Т, перекрывающиеся с отрезком 1, за время О (ппп(п, 1с 18п)), где 1с — количество найденных отрезков. 1Дополлшпвльное условие: попробуйте найти решение, не изменяющее дерево.) 14.3-5.
Какие изменения надо внести в процедуры дерева отрезков для поддержки новой операции 1нтекчм. 8елксн Ехлсти'(Т, г), которая возвращает указатель на узел х дерева отрезков Т, такой что 1ож [1п1 [х]] = 1ою [г] и )пдп [гп1 [х]] = )пдву [1] (либо пг1 [Т], если такого узла в дереве Т нет). Все операции, включая 1нтекчлг, Белксн Ехлстьч, должны выполняться в дереве с и узлами за время О (18 и). 14.3-6. Пусть у нас есть динамическое множество натуральных чисел Щ на котором определена операция Мич блк, возвращающая минимальное расстояние между соседними числами в Я. Например, если Я = (1, 5, 9, 15, 18, 22), то М1н блг(Я) возвратит значение 18 — 15 = 3, так как 15 и 18— ближайшие соседние числа в Я. Разработайте максимально эффективные процедуры 1хзект, 13ееете, Белксн и М~н блг и проанализируйте нх время работы.
Глава 14. Расширение структур данных 381 * 14.3-7. Базы данных при разработке СБИС зачастую представляют интегральную схему как список прямоугольников. Предположим, что все прямоугольники ориентированы вдоль осей х и у, так что представление прямоугольника состоит из минимальных и максимальных координат х и у. Разработайте алгоритм для выяснения, имеются ли в данном множестве из и прямоугольников два перекрывающихся (искать все перекрывающиеся пары не надо). Перекрытием считается также ситуация, когда один прямоугольник лежит полностью внутри другого, пусть при этом их границы и не пересекаются. Время работы алгоритма должно составлять О (и 18 и).
(Указание: перемещайте "строку развертки*' по множеству прямоугольников.) Задачи 14-1. Точка максимального перекрытия Предположим, что мы хотим найти точку максимального перекрытия множества отрезков, т.е. точку, в которой перекрывается наибольшее количество отрезков множества. а) Покажите, что такая точка всегда имеется и представляет собой конечную точку одного из отрезков.
б) Разработайте структуру данных, которая поддерживает эффективную работу операций 1)чтвкчл!. 1)чзвкт, 1)чтвкуд). Рн етн и Рпв РОМ (которая возвращает точку максимального перекрытия). (Указание: воспользуйтесь красно-черным деревом всех конечных точек отрезков. С каждым левым концом отрезка связано значение +1, с правым — значение -1. Добавьте к узлам дерева некоторую дополнительную информацию для поддержки точки максимального перекрытия.) 14-2. Перестановка Иосифа Задача Иосифа ! формулируется следующим образом. Предположим, что и человек расставлены в круг и задано некоторое натуральное число т ( и.
Начиная с определенного человека, мы идем по кругу, удаляя каждого т-го человека. После удаления человека счет продолжается дальше. Процесс продолжается, пока все и человек не будут удалены. Порядок, в котором люди удаляются из круга, определяет (и, т)-нерестановку 'Достаточно подробно об этой задаче, се происхождении и вариациях можно прочесть, например, в книге У. Болл, Г.
Коксетср. Математические эссе и развлечения. — Млмир, ! 986 (стр. 43-47).— Прим, ред. Часть!П. Структуры данных 382 Иосифа целых чисел 1, 2,..., и. Например, (7, 3)-перестановка Иосифа имеет вид (3,6,2,7,5,1,4). а) Пусть тп — некоторая фиксированная константа. Разработайте алгоритм, который для данного и за время О (тт) выводит (и, т)-перестановку Иосифа. б) Пусть т не является константой.
Разработайте алгоритм, который для данных п и т за время О (и 18 и) выводит (и, тп)-перестановку Иосифа. Заключительные замечания В книге [247) Препарата (Ргерагага) и Шамос (балашов) описывают ряд деревьев отрезков, встречавшихся литературе, и приводят результаты из работ Эдельсбруннера (Н. Ебе1зЬп~ппег, 1980) и Мак-Крейта (МсСге18пй 1981). В книге приведено дерево отрезков, в котором для данной статической базы данных из и отрезков все к отрезков, перекрывающихся с заданным, могут быль найдены за время О(1с+ 18п). ЧАС ТЫУ Усовершенствованные методы разработки и анализа Введение В этой части описаны три важных метода разработки и анализа эффективных алгоритмов: динамическое программирование (глава 15), жадные алгоритмы (глава ! 6) и амортизационный анализ (глава 17). В предыдущих частях были представлены другие широко распространенные методы, такие как метод разбиения, рандомизация и решение рекуррентных соотношений.
Новые подходы, с которыми нам предстоит ознакомиться в этой части, более сложные, однако они полезны для решения многих вычислительных задач. К темам, рассмотренным в данной части, мы еще обратимся в последующих частях. Динамическое программирование обычно находит применение в задачах оптимизации, в которых для получения оптимального решения необходимо сделать определенное множество выборов. После того как выбор сделан, часто возникают вспомогательные подзадачи, по виду напоминающие основную. Динамическое программирование эффективно тогда, когда определенная вспомогательная подзадача может возникнуть в результате нескольких вариантов выборов. Основной метод решения таких задач заключается в сохранении решения каждой подзадачи, которая может возникнуть повторно. В главе 15 показано, как благодаря этой простой идее алгоритм, время решения которого экспоненциально зависит от объема входных данных, иногда можно преобразовать в алгоритм с полиномиальным временем работы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
