Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 81
Текст из файла (страница 81)
Если выполняется строка 5, то в силу ветвления в строке 3 мы имеем х. (е1г = Т,пй или х. 1е1(.тпх < з,1ого. Если х.1еу( = Т.пй, поддерево с корнем х.(еуг, очевидно, не содержит отрезка, перекрывающегося с з, и присвоение х значения х, тдЬ( сохраняет инвариант. Предположим, следовательно, что х. 1е1г ~ Т. пз( и х. 1е1(. тах < з. (ога. Как показано на рис. 14.5, (а), для каждого отрезка з' в левом поддереве х имеем з'. ЬгдЬ < х. (е!(. тах < з.(ощ .
Согласно трихотомии отрезков з' и з не перекрываются. Таким образом, левое поддерево х не содержит отрезков, перекрывающихся с з, так что присвоение х значения х, тдЬ( сохраняет инвариант. (6) (з] рис. 14.8. Отрезки в доказательстве теоремы 14.2. Значение х. !е1г. глаз показано в обоих случаях пунктирной линией. (а) Поиск выполняется вправо. В левом поддереве х нег отрезка г', перекрывающегося с г. (б) Поиск выполняется влево. Левое поддерево х содержит отрезок, перекрывающийся с г (ситуапия не показана), либо отрезок з', такой, что !'.
)г(уа = х. !е1Г, тах. Поскольку г не перекрывается с г', он не перекрывается и ни с одним из отрезюв гн в правом поддереве х, посмиьку г'. !ам < г". 1ам. ~з век згге Часть Ш. Структуры данных Эаб Если же выполняется строка 4, то, как мы покажем, если в левом поддереве х нет отрезка, перекрывающегося с г, то его вообще нет в дереве. Поскольку выполняется строка 4, в силу условия в строке 3 имеем х. 1е11, тах > 1. 1ош. Кроме того, по определению атрибута тпах в левом поддереве х должен быть некоторый интервал г', такой, что 1.Ь)дЬ = х.1е11.тах ) 1. 10Ю .
(Эта ситуация проиллюстрирована на рис. 14.5,(б).) Поскольку 1 и з' не перекрываются и посюльку неверно, что г'. Ь)дЬ < 1. 1ов, отсюда в соответствии со свойством трихотомии отрезюв следует, что). /идЬ < г'. 1ои. Поскольку дерево отрезков упорядочено в соответствии с левыми концами отрезков, из свойства дерева поиска вытекает, что для любого отрезка гн из правого поддерева х г.
Ь1дЬ < 1 . 1ош < 1'. 1ош Из трихотомии отрезков следует, что 1 и гн не перекрываются. Мы можем, таким образом, заключить, что независимо от того, имеется ли в левом поддереве х отрезок, перекрывающийся с 1, присвоение х значения х. 1еуг сохраняет инвариант цикла. Завершение. Если цикл завершается по условию х = Т. п11, то в дереве, корнем которого является х, нет отрезков, перекрывающихся с 1. Обращение инварнанта цикла приводит к заключению, что дерево Т не содержит отрезков, перекрывающихся с Ь Следовательно, возвращаемое процедурой значение Т. пй совершенно юрректно. Таким образом, процедура 1мтекчАЕ-ЯеАксн работает корректно.
Упражнения 14.3.1 Напишите псевдокод процедуры 1.ЕЕт-йотАте, которая работает с узлами дерева отрезюв и обновляет атрибуты глах за время 0(1). 14.3.2 Перепишите код процедуры 1хте1и/Аь-БеАксн для корректной работы с интервалами (отрезками без юнечных точек). 14.3.3 Разработайте эффективно работающий алгоритм, который для данного отрезка 1 возвращает отрезок, перекрывающийся с 1 и имеющий минимальное значение левого конца (либо Т. п11, если такого отрезка не существует). лву Глава 1К Расширение структур данник 14.3.4 Пусть имеется дерево отрезков Т и отрезок 1.
Опишите, каким образом найти в дереве Т все отрезки, перекрывающиеся с отрезком г, за время 0(ш1п(п, )с 18п)), где к — количество отрезков в выводимом списке. (Указание: один простой метод выполняет запросы, меняя между ними само дерево. Попробуйте найти немного более сложное решение, не изменяющее дерево.) 14.3.5 Какие изменения следует внести в процедуры дерева отрезков для поддержки новой операции 1мтекуле-Яелксн-Ехлстел'(Т,1), которая получает в качестве параметров дерево отрезков Т и отрезок 1 и возвращает указатель на узел х, такой, что х.
1пй 1ове = г. (ов и х. 1пй Ьдй = г'. Ьздй (либо Т. пл1, если такого узла в дереве Т нет). Все операции, включая 1мтекчле-8елпсн-Ехлстеу, должны выполняться в дереве с и узлами за время 0(18 и). 14.3. 6 Пусть есть динамическое множество чисел с4, поддерживающее операцию М1НОлр, возвращающую минимальное расстояние между соседними числами в Я. Например, если Я = (1,5,9,15,18,22), то Мцч-Олр(Я) возвратит значение 18— 15 = 3, так как 15 и 18 — ближайшие соседние числа в 9. Разработайте максимально зффективные процедуры 1мзект, Пееете, Белксн и Мпч-Олр и проанализируйте их время работы. 14.3.7 * Базы данных при разработке СВИС зачастую представляют интегральную схему как список прямоугольников.
Предположим, что все прямоугольники ориентиронаны вдоль осей х и у, так что представление прямоугольника состоит из минимальных и максимальных координат х и у. Разработайте алгоритм для выяснения, имеются ли в данном множестве из и прямоугольников два перекрывающихся (искать все перекрывающиеся пары не нужно). Перекрытием считается также ситуация, когда один прямоугольник лежит полностью внутри другого, пусть при этом их границы и не пересекаются. Время работы алгоритма должно составлять 0(п 18 п). (Указание: перемешайте "строку развертки" по множеству прямоугольников.) Задачи 14.1.
Точка максимального лерекрмалия Предположим, что необходимо найти влочлу максимального иерекрыилия множества отрезков, т.е. точку, в которой перекрывается наибольшее количество отрезков множества. а Покажите, что такая точка всегда имеется и представляет собой конечную точку одного из отрезков. 3ВВ Часть Пл Структуры данных б. Разработайте структуру данных, которая поддерживает зффекгивную работу операций 1тттекчАС-174зект, 1тттекчАС-Реьете и Р33чт7-РОМ (которая возвращает точку максимального перекрытия). (Указание: воспользуйтесь красно-черным деревом всех конечных точек отрезков. С каждым левым концом отрезка связано значение +1, с правым — значение — 1.
Добавьте к узлам дерева некоторую дополнительную информацию для поддержки точки максимального перекрытия.) 14.2. Перестановка Иосифа Задача Иосифа' формулируется следующим образом. Предположим, что п человек расставлены по кругу и задано некоторое натуральное число тп < п. Начиная с определенного человека, мы идем по кругу, удаляя каждого пт-го человека. После удаления человека счет продолжается дальше. Процесс продолжается, пока все п человек не будут удалены. Порядок, в котором люди удаляются из круга, определяет (и, тп)-нерестановку Иосифа целых чисел 1, 2,, п.
Например, (7,3)-перестановка Иосифа имеет вид (3,6,2,7,5,1,4). вь Пусть тп — некоторая фиксированная константа. Разработайте алгоритм, который для данного п за время 0(п) выводит (п, т)-перестановку Иосифа. б. Пусть т не является константой. Разработайте алгоритм, который для данных п и пз за время 0(п 18 п) выводит (п, гп)-перестановку Иосифа.
Заключительные замечания В книге [280] Препарата (Ргерагата) и Шамос (8Ьаэпоз) описывают ряд деревьев отрезков, встречавшихся литературе, и приводят результаты из работ Эдельсбруннера (Н. Еде!БЬптппег, 1980) и Мак-Крейта (МсСте18Ьт, 1981). В книге детально описано дерево отрезков, в котором для данной статической базы данных из п отрезков все /с отрезков, перекрывающихся с заданным, могут быть найдены за время 0(1с + 18 п) . 'Достаточно подробно об этой задаче, ее происхождении и аариаинях, можно прочесть, например, а «инте К Болл, Г Коксетер. Математические эссе н развлечения.
— Мс Мир, Грйб. — С. 43-4Х вЂ” Примеч. ред И' Усовершенствованные методы разработки и анализа Введение В этой части описаны три важных метода разработки и анализа эффективных алгоритмов: динамическое программирование (глава 15), жадные алгоритмы (глава 16) и амортизационный анализ (глава 17). В предыдущих частях были представлены другие широко распространенные методы, такие как метод "разделяй и властвуй", рандомизация и решение рекуррентных соотношений. Новые подходы, с которыми вам предстоит ознакомиться в этой части, более сложные, однако они полезны лля решения многих вычислительных задач.
К темам, рассмотренным в данной части, мы еще обратимся позже в данной книге. Динамическое программирование обычно находит применение в задачах оптимизации, в которых для получения оптимального решения необходимо сделать определенное множество выборов. После того как каждый из выборов сделан, часто возникают вспомогательные подзадачи того же вида. Динамическое программирование эффективно тогда, когда определенная вспомогательная подзадача может возникнуть в результате нескольких вариантов выбора. Основной метод решения таких задач заключается в сохранении решения каждой подзадачи, которая может возникнуть повторно. В главе 15 показано, как благодаря этой простой идее алгоритм, время решения которого экспоненциально зависит от обьема входных данных, иногда можно преобразовать в алгоритм с полиномиальным временем работы.
Жадные алгоритмы, подобно алгоритмам, применяемым в динамическом программировании, используются в задачах оптимизации, для рационального решения которых требуется сделать ряд выборов. Идея, лежащая в основе жадного алгоритма, заключается в том„чтобы каждый выбор был локально оптимальным. В качестве простого примера приведем задачу о выдаче сдачи; чтобы свести к минимуму количество монет, необходимых для выдачи определенной суммы, достаточно каждый раз выбирать монету наибольшего достоинства, не превышающую Часто з'У. 'зсовершенствошзнные методы разработки и анакша той суммы, которую осталось выдать.' Можно сформулировать много таких задач, оптимальное решение которых с помощью жадных алгоритмов получается намного быстрее, чем с помощью методов динамического программирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
