Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 94
Текст из файла (страница 94)
и + 1,0.. п]. Первый индекс должен пробегать не и, а и + 1 значений. Это обьясняется тем, что для получения поддерева, в которое входит только фиктивный ключ в!н, понадобится вычислить и сохранить значение е[и + 1, п). Второй индекс должен начинаться с нуля, поскольку для получения поддерева, содержащего лишь фиктивный ключ Ио, нужно вычислить и сохранить значение с[1, 0).
Мы будем использовать только те элементы е[г, Я, для которых 7' > 1 — 1. Кроме того, будет использована таблица тоо1[г, з], в которую будут заноситься корни поддеревьев, содержащих ключи йв,..., к . В этой таблице задействованы только те записи, для которых 1 < 1 < 7' < п. Для повышения эффективности понадобится еще одна таблица. Вместо того чтобы каждый раз при вычислении с[1,Я вычислять значения ю(1,7') "с нуля'*, для чего потребуется В(7' — 1) операций сложения, будем сохранять эти значения в таблице ю[1 .. и+1, 0 ..
п]. В базовом случае вычисляются величины ю[1, з — Ц = рл 1 для 1 < 1 < и + 1. Для 7' > 1 вычисляются величины ю[г, з'] = и[!, з — Ц+р + сь . (15.15) Таким образом, каждое из б!(пз) значений матрицы ю[1,Я можно вычислить за время В(1). Ниже приведен псевдокод, который принимает в качестве входных данных вероятности ры..., р„н до,..., 9н н размер и и возвращает таблицы е и тоо1.
ОРТ! МАЕ-ВБТ (р, 9, п) 1 с[1 .. и + 1, О., п), ю[1 ., и + 1, О .. и] н тоо1[1 .. п, 1., и) — новые таблицы 2 !ог 1 = 1 Го п + 1 3 е[г,! — Ц = дв 4 ю[1,1 — Ц=9! ! 5 !ог ! = 1 Го п 6 1ог 1 = 1 зо и — 1+ 1 7 )=!+! — 1 8 е[г,Я = со 9 ю[г,Я = ю[е,з — Ц+ру + ц !О Гоге = 1!о) 11 1 = е~г', т — Ц + е[т + 1, Я + ю [1, Я !2 !з ! < е[г,Я 13 е[1,Я = ! !4 тоос[в,Я = т 15 ге!пгп е и тоо! Гласа!5. Динамическое «рограммироаание 437 е 5 ",1 7 4 .4112.'.5.' ., 2 3. - )-:Тз- .2'®~53 2 4Ф4 '1.20:.!73!"...4 ~645,,~МФ~б!6~~~0р~ ОФ$,:.,;,0,!!)о 5.",! 1 4 '1:®2~2 3 ...
02!! ' балла О. гоог 5.~1 ~2 ~;3 Рнс. 15.10. Таблицы с[1,Я, го[в)Я и гаоф,у], вычисленные процедурой Октгми.-ВБТдлв распределенил ключей, показанного на рис. ! 5 ай Таблицы повернугы таким образом, чтобы диагонали располагались по горизонтали. Благсшаря приведенному выше описанию и схожести с процедурой Мдтн1хСнд!н-Ойпбк нз раздела 15.2, работа представленной выше процедуры должна быть понятной. Цикл 1ог в строках 2-4 инициализирует значения е]т,т — Ц н и [!,т — Ц. Затем в цикле Рог в строках 5 — 14 с помощью рекуррентных соотношений (15.14) и (15.15) вычисляются элементы матриц е[г, Я и пг[г, 7] для всех индексов 1 < т < 5 < гт.
В первой итерации, когда 1 = 1, в этом цикле вычисляются элементы е[т,т) и цг[г,т] для т' = 1,2,..., п. Во второй итерации, когда 1 = 2, вычисляются элементы е[т, т + Ц и тю[т', т + Ц для т' = 1, 2,..., п — 1 и т.д. Во внутреннем цикле Рог (строки 10-14) каждый индекс т апробируется на роль индекса корневого элемента к„оптимального бинарного дерева поиска с ключами гт,..., гсзч В этом цикле элементУ гоп![!, т] пРисваиваетсЯ то значение индекса г, которое подходит лучше всего. На рис. 15.10 показаны таблицы е[1,2], цг[т, 7] и гоо![т', т], вычисленные с помощью процедуры Орт!ыл!.-ВЯТ для распределения ключей, показанного на рис. 15.9. Как и в примере с перемножением цепочки матриц на рис.
15.5, таблицы повернуты так, чтобы диагонали располагались горизонтально. В процедуре Орт!мл~.-ВБТ строки вычисляются снизу вверх, а в каждой строке заполнение элементов выполняется слева направо. Время работы процедуры ОРТ!мм:ВБТ, как и время работы процедуры Мдтк!х-Сн7гпч-ОВОВВ, равно !Э(пэ). Легко увидеть, что время работы составляет 0(п~), поскольку циклы 1ог этой процедуры трижды вложены друг в друга„ и индекс каждого цикла принимает не более и значений. Далее, индексы циклов в процедуре Орт!ыл~.-ВВТ изменяются не в тех же пределах, что и индексы 43о Часть 1К усовершенствованные методы разрабонин н анашзо циклов в процедуре МАтюх-СнА1н-Окпнн, но во всех направлениях они принимают по крайней мере одно значение. Таким образом, процедура Орт~мА~:ВЯТ, как и процедура МАтых-СнАпч-Окпнк, выполняется в течение времени П(п ).
Упражнении 15.5.1 Напишите псевдокод процедуры Сонзткист-Орт1млс-ВЯТ(гоо1), которая по заданной таблице гооз выводит структуру оптимального бинарного дерева поиска. Для примера, приведенного на рис. 15.10, процедура должна выводить структуру, соответствующую оптимальному бинарному дереву поиска, показанному на рис. 15.9, (6). кз является корнем Й1 является левым дочерним узлом Йз до является левым дочерним узлом )сэ с11 является правым дочерним узлом й~ кз является правым дочерним узлом кз Й4 является левым дочерним узлом )сз Йз является левым дочерним узлом Й4 дз является левым дочерним узлом Йз ~1з является правым дочерним узлом йз с(4 является правым дочерним узлом й4 дз является правым дочери»м узлом Йз 15.5.2 Определите стоимость и структуру оптимального бинарного дерева поиска для множества, состоящего из и = 7 ключей, которым соответствуют следующие вероятности.
15.5.3 Предположим, что вместо того, чтобы поддерживать таблицу ш[з, з'], значение зо(з, 1) вычисляется в строке 9 процедуры Орт1мл1.-ВЯТ непосредственно из уравнения (15.12) и используется в строке 11. Как это изменение повлияет на асимптотическое поведение времени выполнения этой процедуры? 15.5.4 * Кнут [21Ц показал, что всегда существуют корни оптимальных поддеревьев, такие, что юо1[4,1' — 1] < гоо1[з,Я < гоо1[г + 1,1] для всех 1 < з < 4 < и. Используйте этот факт для модификации процедуры Орт~мАь-ВЯТ, при которой время ее работы станет равным Й(п ).
Гласа )5. Динамическое программирование 439 Задачи 15.1. Наидлиннейиеий простой пуввь в ориенгнированном агбиклическом графе Предположим, что имеется ориентированный ациклический граф г = ()г, Е) с действительными весами ребер и двумя различными вершинами в и К Опишите подход динамического программирования для поиска наидлиннейшего взвешенного простого пути от л к 1.
Как выглядит граф подзадач? Какова эффективность разработанного вами алгоритма? 15.3. Наидлиннейиеая палиндраиная подпоследовательноснеь Палиндром представляет собой непустую строку на некотором алфавите, которая одинаково читается в прямом и обратном направлениях.
Примерами палиндромов могут служить все строки длиной 1, потоп, топот, заказ и др. Разработайте эффективный алгоритм поиска наидлиннейшего палиндрома, являющегося подпоследовательностью данной входной строки. Например, для строки математика ваш алгоритм должен выводить атата. Каково время работы нашего алгоритма? 15.3. Бипгоническая евклидова задача о коммивояжере В йитонической евклидовой задаче о коммивояжере на плоскости задано множество нз п точек, и необходимо найти кратчайший замкнутый путь, соединяющий все эти точки. На рис. 15.11, (а) показано решение задачи, в которой имеется семь точек. В общем случае задача является )ч)Р-полной, поэтому считается, что для ее решения требуется время, превышающее полиномиальное (см.
главу 34). Й.Л. Бентли (П.. Веп))еу) предположил, что задача упрощается благодаря ограничению интересующих нас маршрутов биатоническими (Ь(гоше гонг), т.е, такимн, которые начинаются в крайней слева точке, проходят слева направо, а затем— справа налево, возвращаясь прямо к исходной точке. На рис.15.11,(б) показан кратчайший битонический маршрут„проходящий через те же семь точек. В этом (б) (а) Рнс. 15.11. Семь точек на плоскости, налаженные на единичную сетку.
(а) Кратчайший замкнутый путь длиной омно 24.89. Этот путь не является бнтоннческнм. (6) Кратчайший бнтоннческнй замкнутый путь для того ме мнокества точек. Его длина — оюло 25.58. 440 Часть з'К усовершенствованные методы разработки и аназюа случае возможна разработка алгоритма, время работы которого является полиномиальным. Разработайте алгоритм для определения оптимального битонического маршрута„время работы которого будет равным 0(пз). Предполагается, что не существует двух точек, координаты х которых совпадают. (Указаниез перебор вариантов следует организовать слева направо, поддерживая оптимальные возможности для двух частей, из которых состоит маршрут.) 15.4. Вывод на печать с форматированием Рассмотрим задачу о форматировании параграфа текста, предназначенного для вывода на печать.
Входной текст представляет собой последовательность, состоящую из и слов, длины которых равны (ы (з,..., 1„(длина слов измеряется в символах). При выводе на печать параграф должен быть аккуратно отформатирован и размещен в несколько строк, в каждой из которых помещается по М символов. Сформулируем критерий "аккуратного" форматирования следующим образом.
Если данная строка содержит слова от з-го до у-го, где з < з, и мы оставляем между словами ровно по одному пробелу, количество оставшихся пробелов в конце строки, равное М вЂ” 5+ з — 2 „',1ы должно быть неотрицательным, чтобы все слова поместились в строке. Мы хотим минимизировать сумму возведенных в куб остатков по всем строкам, кроме последней. Сформулируйте алгоритм, основанный на принципах динамического программирования, который аккуратно выводит на принтер параграф, состоящий из и слов. Проанализируйте время работы этого алгоритма и требуемое для его работы количество памяти. 15.5.
Расстояние редактирования Для того чтобы преобразовать исходную строку текста с[1..зп] в конечную строку у(1 .. и], можно воспользоваться различными операциями преобразования. Наша цель заключается в том, чтобы для данных строк х и у определить последовательность преобразований, превращающих х в у. Для хранения промежуточных результатов используется массив е (предполагается, что он достаточно велик для хранения необходимых промежуточных результатов). Изначально массив з пуст, а в конце работы еЦ = у]5] для всех 5 = 1, 2,..., п.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
