Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 86
Текст из файла (страница 86)
Однако благодаря наличию всего лишь О (тп) различных вспомогательных задач можно воспользоваться динамическим программированием для вычисления решения в восходящем направлении. В процедуре ЬСЯ ЬечОтн в роли входных данных выступают две последовательности Х = (хмара,...,х,„) и У = (уыуз,...,у„). Величины с[1>Я хранятся в таблице с [О..т, О..п), элементы которой вычисляются по строкам (т.е.
сначала слева направо заполняется первая строка, затем — вторая и т.д.). В процедуре также поддерживается таблица Ь [1..т, 1..п], благодаря которой упрощается процесс построения оптимального решения. Наглядный смысл элементов Ь [г, Я состоит в том, что каждый из них указывает на элемент таблицы, соответствующий оптимальному решению вспомогательной задачи, выбранной при вычислении элемента с [1,2). Процедура возвращает таблицы Ь и с; в элементе с [т, и] хранится длина 1 СБ последовательностей Х и У.
ЬСБ Ьнчатн(Х, У) 1 пз ~ — 1еадй(Х) 2 п ~ — 1епдй[У] 3 1ог г' — 1 1о пх 4 по с[1,0] — О 5 1ог2' - О 1о и 6 йо с[0,2] О 1 1ог1 — 1 1о т 8 по 1ог д — 1 1о и 9 аоп~;= 1О хпеп 11 12 е1ае 13 14 15 16 17 ге1пгп с и Ь Уу с[1, з] ~ — с(1 — 1, 2 — 1] + 1 Ь(в', Я П с[1 — 1,2] > с[х,д — 1] 1веп с(г, Я вЂ” с[1 — 1, 2] Ь[г, Я епе с(1, у] Ь[г, Я "- "Т" — с[1, 2 — Ц + — + — ™ На рис.
15.6 показаны таблицы, полученные в результате выполнения процедуры ЬСЗ Ьнхотн с входными последовательностями Х = (А, В, С, В, х), А, В) и У = = (В, Х), С, А, В, А). Время выполнения процедуры равно О (тп), поскольку на вычисление каждого элемента таблицы требуется время, равное О (1). Квадрат, Глава 15. Динамическое программирование 423 с; 2 1 з з ь л .''ю" л и' я ъ': .4,~ Г '-:с1 а~ 0',,; ~~-, ~ !.~ Рнс.
15.6. Таблицы с н 6, которые возвращаются процедурой 1.СЗ Ееиотн для входных последовательностей Х = = (А,В,С,В,В,А,В) н У = (В,Ю,С, А,В,А) который находится на пересечении строки 1 и столбца з, содержит значение с [г, з] и соответствующую стрелку, выступающую в роли значения 6 [г, з]. Элемент 4, который является значением содержащегося в правом нижнем углу элемента с[7,6], — длина самой длинной обшей подпоследовательности последовательностей Х и У (в данном случае это (В, С, В, А)). При г, у > О элемент с[1, з] зависит только от того, выполняется ли соотношение х; = у, и от значений элементов с [1 — 1, з], с [г, з — 1] и с [1 — 1, з — 1], которые вычисляются перед значением с [г, з].
Чтобы восстановить элементы, из которых состоит самая длинная общая подпоследовательность, проследуем по стрелочкам 6 [г, з], ведущим из правого нижнего угла. Полученный путь обозначен затенением серого цвета. Каждый элемент ""~" на этом пути соответствует (выделенному цветом) элементу, для которого х; = уу является элементом самой длинной общей подпоследовательности. Этап 4: построение самой длинной общей подпоследователь ности С помощью таблицы 6, которая возвращается процедурой 1 СЯ Енчстн, можно быстро сконструировать самую длинную общую подпоследовательность последовательностей Х = (хм ха,..., х,в) и У = (ум уз,..., у„). Мы просто начинаем с элемента 6 [гп,7з] и проходим таблицу по стрелкам.
Если значением элемента 6 [1,2] является ""~", то элемент х; = у принадлежит самой длинной Часть !У. Усовершенствованные методы разработки н анализа 424 общей подпоследовательности. Элементы 1.СБ, восстановленные этим методом, следуют в обратном порядке. Приведенная ниже рекурсивная процедура выводит элементы самой длинной общей подпоследовательности последовательностей Х и У в прямом порядке. Начальный вызов этой процедуры выглядит как Ршнт 1.СЯ(6, Х, !епрГЬ [Х], !епу!и [г ]): Рк!нт 1.СБ(Ь, Х, г, !') ! !11=0илиу =О 2 Г!зеп ге!пгп 3 Ы 6[!,з] =""," 4 !пеп Рк!нт 1.СБ(Ь, Х, ! — 1, з — 1) 5 рг!и! х; б е!вен 6[!, з] = "!" 7 !!зеп Рюнт 1СЯ(Ь,Х,! — 1,з) 8 еие Рк!нт 1.СБ(Ь,Х,г, з — 1) Для таблицы Ь, изображенной на рис.
15.б, эта процедура выводит последовательность "ВСВА". Время работы процедуры равно О (т+ и), поскольку хотя бы один из индексов г или з уменьшается на каждой стадии рекурсии. Улучшение кода После разработки алгоритма часто оказывается, что можно улучшить время его работы или объем требуемой им памяти. Особенно это справедливо в отношении незамысловатых алгоритмов, основанных на принципах динамического программирования.
Некоторые изменения могут упростить код и уменьшить постоянный множитель, но не приводят к повышению производительности в асимптотическом пределе. Другие же могут вызвать существенное асимптотическую экономию времени и пространства. Например, можно обойтись без таблицы Ь. Каждый элемент с [!, т] зависит только от трех других элементов этой же таблицы: с[! — 1, з — 1], с[! — 1,Я и с [1, з — 1]. Для данного элемента с [г, т] в течение времени О (1) можно определить, какое из этих трех значений было использовано для вычисления с [г, т], не прибегая к таблице Ь. Таким образом, самую длинную общую подпоследовательность можно восстановить в течение времени О (т + и).
Для этого понадобится процедура, подобная процедуре Рк!нт 1 СЯ (такую процедуру предлагается составить в упражнении !5.4-2). Несмотря на то, что в этом методе экономится объем памяти, равный О (тп), асимптотически количество памяти, необходимой для вычисления самой длинной обшей подпоследовательности, не изменяется. Это объясняется тем, что таблица с все равно требует О (тп) памяти. Однако можно уменьшить объем памяти, необходимой для работы процедуры Рк!нт 1.СЗ, поскольку одновременно нужны лишь две строки этой таблицы: Глава 15.
Динамическое программирование 425 вычисляемая и предыдущая. (Фактически для вычисления длины самой длинной общей подпоследовательности можно обойтись пространством, лишь немного превышающим объем, необходимый для одной строки матрицы с — см. упражнение 15.4-4.) Это усовершенствование работает лишь в том случае, когда нужно знать только длину самой длинной общей подпоследовательности. Если же необходимо воссоздать элементы этой подпоследовательности, такая "урезанная" таблица содержит недостаточно информации для того, чтобы проследить обратные шаги в течение времени 0 (т + п).
Упражнения 15.4-1. Определите самую длинную общую подпоследовательность последовательностей (1,0,0,1,0,1,0,1) и (0,1,0,1,1,0,1,1,0). 15.4-2. Покажите, как в течение времени 0(гп+ и) воссоздать самую длинную общую подпоследовательность, не используя при этом таблицу б, если имеется таблица с и исходные последовательности Х = (кы хз,..., х ) и У = (Уы Уз,, Ув) 15.4-3.
Приведите версию процедуры ЕСБ 1ехстн с запоминанием, время работы которой равно 0 (тп). 15.4-4. Покажите, как вычислить длину самой длинной общей подпоследовательности, используя при этом всего 2 . гшп (т, и) элементов таблицы с плюс О (1) дополнительной памяти. Затем покажите, как это же можно сделать с помощью 1пш (ти, п) элементов таблицы и 0 (1) дополнительной памяти. 15.4-5. Приведите алгоритм, предназначенный для вычисления самой длинной монотонно неубывающей подпоследовательности данной последовательности, состоящей из п чисел.
Время работы алгоритма должно быть равно 0 (пз). * 15.4-6. Приведите алгоритм, предназначенный для вычисления самой длинной монотонно неубывающей подпоследовательности данной последовательности, состоящей из п чисел. Время работы алгоритма должно быть равно 0 (и !кп). (Указание: обратите внимание, что последний элемент кандидата в искомую подпоследовательность по величине не меньше последнего элемента кандидата длиной г — 1.) 15.5 Оптимальные бинарные деревья поиска Предположим, что разрабатывается программа, предназначенная для перевода текстов с русского языка на украинский. Для каждого русского слова необходимо найти украинский эквивалент.
Один из возможных путей поиска — построение Часть 1Ч. Усовершенствованные методы разработки и анализа 426 бинарного дерева поиска с п русскими словами, выступающими в роли ключей, и украинскими эквивалентами, играющими роль сопутствующих данных. Поскольку поиск с помощью этого дерева будет производиться для каждого отдельного слова из текста, полное затраченное на него время должно быть как можно меньше.
С помощью красно-черного дерева или любого другого сбалансированного бинарного дерева поиска можно добиться того, что время каждого отдельного поиска будет равным 0(1яп). Однако слова встречаются с разной частотой, и может получиться так, что какое-нибудь часто употребляемое слово (например, предлог или союз) находится далеко от корня, а такое редкое слово, как "контрвстреча", — возле корня. Такой способ организации привел бы к замедлению перевода, поскольку количество узлов, просмотренных в процессе поиска ключа в бинарном дереве, равно увеличенной на единицу глубине узла, содержащего данный ключ. Нужно сделать так, чтобы слова, которые встречаются в тексте часто, были размещены поближе к корню.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
