Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 88
Текст из файла (страница 88)
Мы будем использовать только те элементы е [г, Я, для которых з > 1 — 1. Кроме того, будет использована таблица гоо1 [г, з], в которую будут заноситься корни поддеревьев, содержащих ключи Ц,..., /с . В этой таблице задействованы только те записи, для которых 1<г<з<и. Для повышения эффективности понадобится еще одна таблица. Вместо того чтобы каждый раз при вычислении е [г, з] вычислять значения со (г, з) "с нуля", для чего потребуется 6 (з — 1) операций сложения, будем сохранять эти значения в таблице и [1 ..п + 1, О..п).
В базовом случае вычисляются величины ю [с', 1 — 1) = = д; 1 для 1 ( 1 ( и + 1. Для з' > 1 вычисляются величины ю [г, з] = и [с', з' — 1] + р + д . (15.20) Таким образом, каждое из 9 [пз) значений матрицы со [г, з] можно вычислить за время 9 (1). Ниже приведен псевдокод, который принимает в качестве входных данных вероятности рм..., р„и до,..., д„и размер п и возвращает таблицы е и гоо1. Часть |Ч. Усовершенствованные методы разработки и анализа 432 ОРТ!мА!.
ВБТ[р, 9, и) 1 Гогг' — 1 1о и+1 2 до е[г,1 — 1] — рн 3 ю[ю',г — Ц вЂ” о; 1 4 1ог! — 1 то и 5 Йо 1ог 1 — 1 Го и — 1+ 1 б йо 7' -1+1 — 1 7 е[г, Я оо 8 ю[г',Я вЂ” ю[т,7' — 1] + ру + 93 9 Гог т — г' 1о 7' 1О йо 1 — е(г, т — 1] + е[т+ 1, 7] + ю[1, 7] !1 !Г! < е[1,2] !2 Феп е[Г,Я вЂ” Х 13 тоо8[з, Я вЂ” т !4 гегпгп е и тоо1 Благодаря приведенному выше описанию и аналогии с процедурой МАтк!х СнА!н Оюеа, описанной в разделе 15.2, работа представленной выше процедуры должна быть понятной.
Цикл 1ог в строках 1-3 инициализирует значения е [1,1 — 1] и ю (1,1 — Ц. Затем в цикле 1ог в строках 4-13 с помощью рекуррентных соотношений Г!5.19) и 115.20) вычисляются элементы матриц е [г, Я и !о [г, Я для всех индексов 1 < ! < 7' < и. В первой итерации, когда ! = 1, в этом цикле вычисляются элементы е [г, 1) и ю [г, 1] для 1 = 1, 2,..., и.
Во второй итерации, когда 1 = 2, вычисляются элементы е [1,1+ 1) и ю [г, Г + 1] для Г = 1, 2,..., и — 1 и т.д. Во внутреннем цикле Гог Гстроки 9 — 13) каждый индекс т апробируется на роль индекса корневого элемента )с„оптимального бинарного дерева поиска с ключами )с,,..., й~. В этом цикле элементу тоо1 [1, з] присваивается то значение индекса т, которое подходит лучше всего. На рис.
15.8 показаны таблицы е [г, Я, ю (з, Я и тоо! [г, 7], вычисленные с помощью процедуры ОРт!мль ВБТ для распределения ключей из табл. 15.!. Как и в примере с перемножением цепочки матриц, таблицы повернуты так, чтобы диагонали располагались горизонтально. В процедуре ОРт!мл!. ВБТ строки вычисляются снизу вверх, а в каждой строке заполнение элементов производится слева направо. Время выполнения процедуры ОРт!мл!.
ВБТ, как и время выполнения процедуры МАтих СнА!н Оюна, равно 91и~). Легко увидеть, что время работы составляет О [из), поскольку циклы 1ог этой процедуры трижды вложены друг в друга, и индекс каждого цикла принимает не более и значений. Далее, индексы циклов в процедуре ОРт!мА!. ВБТ изменяются не в тех же пределах, что и индексы циклов в процедуре МАта!х Снл!н Оюек, но во всех направлениях они принимают по крайней мере одно значение. Таким образом, процедура ОРт!мА!. ВБТ, как и процедура МАта!х Снлпч Оюпк, выполняется в течение времени Г) [из).
Глава 15. Динамическое программирование 433 Рис. 15.8. Таблицы с~!,1), и ~1,Я н гоо! ~г,Я, вычнслснныс процедурой Огть мль ВЯТ для распрсдслсния ключсй из табл. !5.1 Упражнения 15.5-1. Напишите псевдокод для процедуры Соызтиг!ст Опт!ми. ВБТ(гоо!), которая по заданной таблице гоп! выдает структуру оптимального бинарного дерева поиска. Для примера, приведенного на рис.
15.8, процедура должна выводить структуру, соответствующую оптимальному бинарному дереву поиска, показанному на рис. 15.76: Йз — корень Й! — левый дочерний элемент Йз дс — левый дочерний элемент й! с!1 — правый дочерний элемент !с1 1св — правый дочерний элемент Йз Й~ — левый дочерний элемент Йз йз — левый дочерний элемент к4 г!з — левый дочерний элемент йз с!з — правый дочерний элемент Йз о4 — правый дочерний элемент Й4 Ыз — правый дочерний элемент 1сз Часть 1Ч.
Усовершенствованные методы разработки и анализа 434 15.5-2. Определите стоимость и структуру оптимальною бинарного дерева поиска для множества, состоящего из и = 7 ключей, которым соответствуют след уюшие вероятности: 15.5-3. Предположим, что вместо того, чтобы поддерживать таблицу и [г, Я„значение ш (г, з) вычисляется в строке 8 процедуры Огт!мА!. ВБТ непосредственно из уравнения (15.17) и используется в строке 1О. Как это изменение повлияет на асимптотическое поведение времени выполнения этой процедуры? * 15.5-4. Кнут (184! показал, что всегда существуют корни оптимальных поддеревьев, такие что гоо1[г, З вЂ” 1] < гоо1[1, Я < гоо1[1 + 1,Я для всех 1 < 1 < з < и. Используйте этот факт для модификации процедуры Огт!млг. ВБТ, при которой время ее выполнения станет равным 9 (п~).
Задачи 15-1. Битоиическая евклидова задача о коммивояжере Евклидова задача о коммивояжере (епс!Ыеап 1гаче11!пй-за1еашап ргоЬ1еш) — это задача, в которой определяется кратчайший замкнутый путь, соединяющий заданное множество, которое состоит из и точек на плоскости. На рис. 15.9а приведено решение задачи, в которой имеется семь точек.
В общем случае задача является Ыр-полной, поэтому считается, что для ее решения требуется время, превышающее полиномиальное (см. главу 34). Бентли (1.1.. Вепг!еу) предположил, что задача упрощается благодаря ограничению интересуюших нас маршрутов ботаническими (Ь!гоп!с 1опг), т.е. такими, которые начинаются в крайней левой точке, проходят слева направо, а затем — справа налево, возвращаясь прямо к исходной точке. На рис. 15.9б показан кратчайший битонический маршрут, проходящий через те же семь точек. В этом случае возможна разработка алгоритма, время работы которого является полиномиальным.
Напишите алгоритм, предназначенный для определения оптимального битонического маршрута, время работы которого будет равным О (пз]. Предполагается, что не существует двух точек, координаты х которых совпадают. (Указание: перебор вариантов следует организовать слева направо, поддерживая оптимальные возможности для двух частей, из кото- рых состоит маршрут.) Глава 15. Динамическое программирование 435 а) Рис. 15.9. а) кратчайший (ие битоиический) замкнутый маршрут длиной 24.89; б) кратчайший битоиический маршрут длиной 25.58 15-2. Вывод на печать с форматированием Рассмотрим задачу о форматировании параграфа текста, предназначенного для вывода на печать. Входной текст представляет собой последовательность, состоящую из п слов, длины которых равны 1м1з,..., 1„ (длина слов измеряется в символах).
При выводе на печать параграф должен быть аккуратно отформатирован и размещен в несколько строк, в каждой из которых помещается по М символов. Сформулируем критерий "аккуратного" форматирования. Если данная строка содержит слова от г-го до з-го и мы оставляем между словами ровно по одному пробелу, количество оставшихся пробелов„равное М вЂ” ) + г — ~;э~,. 1ш должно быть неотрицательно, чтобы все слова поместились в строке. Мы хотим минимизировать сумму возведенных в куб остатков по всем строкам, кроме последней.
Сформулируйте алгоритм, основанный на принципах динамического программирования, который аккуратно выводит на принтер параграф, состоящий из и слов. Проанализируйте время работы этого алгоритма и требуемое для его работы количество памяти. 15-3. Расстояние редактирования Для того чтобы преобразовать исходную строку текста х[1..т[ в конечную строку у [1..п]„можно воспользоваться различными операциями преобразования. Наша цель заключается в том, чтобы для данных строк х и у определить последовательность преобразований, превращающих х в у. Для хранения промежуточных результатов используется массив г (предполагается, что он достаточно велик для хранения необходимых промежуточных результатов). Изначально массив г пуст, а в конце работы з [2[ = у [Я для всех ) = 1, 2,..., и.
Поддерживается текущий индекс г массива к и индекс з массива г, и в ходе выполнения операций преобразования разрешено изменять элементы массива з и эти индексы. В начале работы алгоритма г = з = 1. В процессе преобразования необходимо Часть И. Усовершенствованные методы разработки и анализа 436 проверить каждый символ массива х.
Это означает, что в конце выполне- ния последовательности операций значение г должно быть равно т + 1. Всего имеется шесть перечисленных ниже операций преобразования. Копирование символа из массива х в массив г путем присвоения х [Я вЂ” х [г] с последующим увеличением индексов г и у. В этой операции проверяется элемент х [1].
Замена символа из массива х другим символом с путем присвоения я [Я с с последующим увеличением индексов г и тд В этой операции проверяется элемент х [4]. Удаление символа из массива х путем увеличения на единицу индекса г и сохранения индекса 1 прежним. В этой операции проверяется элемент х [1]. Вставка символа с в массив г путем присвоения г [у] — с и увеличения на единицу индекса з при сохранении индекса г прежним. В этой операции не проверяется ни один элемент массива х.
Перестановка двух следующих символов путем копирования их из массива х в массив з в обратном порядке. Это делается путем присваиваний з [Я вЂ” х [г + Ц и г [у + 1] — х [г] с последующим изменением значений индексов г — 1+ 2 и з — т'+ 2. В этой операции проверяются элементы х [г] и х [1+ 1]. Удаление остатка массива х путем присвоения з — т + 1. В этой операции проверяются все элементы массива х, которые не были проверены до сих пор. Если эта операция выполняется, то она должна быть последней.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
