Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 92
Текст из файла (страница 92)
Однако благодаря наличию всего лишь Н(тп) различных подзадач можно воспользоваться динамическим программированием для вычисления решения в восходящем направлении. В процедуре Г.СБ-(.ннатн в роли входных данных выступают две последовательности Х = (хз, хз, ..,, х ) и У = (ун уз,, .., у„). Величины с[з,2] хранятся в таблице с(0 .. т, 0 .. п1, элементы которой вычисляются построчно (т.е. сначала слева направо заполняется первая строка, затем — вторая и т.д.).
В процедуре также поддерживается таблица Ь(1., т, 1 .. п], благодаря которой упрощается процесс построения оптимального решения. Наглядный смысл элементов 6(з,2] состоит в том, что каждый из них указывает на элемент таблицы, соответствующий оптимальному решению подзадачи, выбранной при вычислении элемента с[з,2].
Процедура возвращает таблицы 6 и с; в элементе с(т, п] хранится длина Г.СБ последовательностей Х и У. Глава ! й Динамическое нраграммироиание 42Р О ! 2 3 4 5 б з,т ф' ГЭ таг. А 'айч Ч)Г ([[) " '1[к'„'":]:"'"т)" [ ;. Ол 1::...2:..
2. 2. 7 Л "....О;-',, 1,;...,.~,':„...22..,.).. 4 Рис. 15.6. Таблицы с и Ь, полученные в результате работы процедуры ССБ-Скнотн с последовательностями Х = (А,В,С,В,В,А,В) и У = (В,В,С, А,В,А). Квадратик пересечении строки 1 и силбца,з содержит значение с[з, Я и стрелку в качестве значения элемента 6[г, з]. Значение 4 в квадрате с[7, 6[ — нижнем правом углу таблицы — представляет собой длину ССБ (В, С, В, А) последовательностей Х и У.
Прн з, г ) О элемент с[СЯ зависит только от того, выполняется ли равенспю к; = ум и от значений в элементах с[з — 1, Я, с[8 У вЂ” 1] н с[з — 1, 1 — 1[, которые вычисляются до вычисления с[з, Я. Чтобы восстановить элементы, входюцие в ССБ, следуем по стрелкам Ь[г,Я иэ нижнего правого угла таблицы; на рисунке эта последовательность заштрихована.
Кажлал стрелка "";" в этой последовательности соответствует элементу, для которого кч = рэ является членом ьСБ. вательностей Х = (хы хщ, х ) и У = (уг, уз,, у„). Мы просто начинаем с элемента Ь[т,п) и проходим таблицу по стрелкам. Если значением элемента Ь[з, Я является ",*', то элемент х; = у принадлежит наидлиннейшей общей подпоследовательности. Элементы 1.С8, восстановленные этим методом, следуют в обратном порядке. Приведенная ниже рекурсивная процедура выводит элементы самой длинной общей подпоследовательности последовательностей Х и У в прямом порядке. Начальный вызов этой процедуры выглядит как Рк1нт-1 С8(Ь, Х, Х. 1епд1Ь, У. 1еддгЛ). Рк1нт-) С8(Ь, Х, з', з) 1 [тт'==Оог2 ==0 2 гегнгн 3 [ГЬ[з,Я =="кч," 4 Ркпчт-ЬС8(Ь, Х, з — 1„7 — 1) 5 ргшг хг б е)ве11 Ь[з, Я == '"['" 7 Ркпчт-1,С8(Ь, Х, з — 1, 7) 8 е)ке Ркнчт-ЕС8(Ь, Х, з, 1 — 1) Для таблицы Ь, изображенной на рис.
15.8, эта процедура выводит последовательность "ВСВА". Время работы процедОры равно О(т + и), поскольку хотя бы адин из индексов з или т уменьшается при каждом рекурсивном вызове. 430 Часть 1У. Усовершенствованные методы разработки н анавиза Улучшение кода После разработки алгоритма часто оказывается, что можно улучшить время его работы или объем требуемой им памяти. Одни изменения могут упростить код и уменьшить постоянный множитель, но при этом не приводят к повышению производительности в асимптотическом пределе. Другие же могут вызвать суше- ственную асимптотическую экономию времени работы и используемой памяти.
Например, в алгоритме поиска ЬСБ можно обойтись без таблицы Ь. Каждый элемент с[4,1] зависит только от трех других элементов этой же таблицы: с[з — 1,1 — Ц, с[з — 1, з] и с[4,1 — Ц. Для данного элемента с[з,1] в течение времени 0(1) можно определить, каюе из этих трех значений было использовано для вычисления с[г,у], не прибегая к таблице Ь.
Таким образом, самую длинную общую подпоследовательность можно восстановить в течение времени 0(т+ и). Для этого понадобится процедура, подобная процедуре Ринг-ЬСЕ (такую процедуру предлагается составить в упр. 15.4.2). Несмотря на то что в этом методе экономится объем памяти, равный 9(тп), асимптотически юличество памяти, необходимой для вычисления самой длинной общей подпоследовательности, не изменяется. Зто объясняется тем, что таблица с все равно требует Н(тп) памяти.
Однако можно уменьшить асимптотический объем памяти, необходимой для работы процедуры РК1ыт-ЬСЯ, поскольку одновременно нужны лишь две строки таблицы с: вычисляемая и предыдущая. (Фактически для вычисления длины самой длинной общей подпоследовательности можно обойтись пространством, лишь немного превышающим объем, необходимый для одной строки матрицы с; см. упр. 15.4.4.) Это усовершенствование работает лишь в том случае, когда нужно знать только длину самой длинной общей подпоследовательности. Если же необходимо воссоздать элементы этой подпоследовательности, такая "урезанная*' таблица содержит недостаточно информации для того, чтобы проследить обратные шаги за время О(т + ц).
Упражнения 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 Приведите версию процедуры ЬСЯ-Ьнмстн с запоминанием, время работы которой равно 0(тп). 15.4.4 Покажите, как вычислить длину наидлиннейшей общей подпоследовательности, используя при этом только 2 ппп(зп, п) элементов таблицы с плюс 0(1) допол- 43г Глава !5. Динамическое программирование нятельной памяти. Затем покажите, как то же самое можно сделать с помощью пйп(т, и) элементов таблицы и 0(1) дополнительной памяти. 15.4. 5 Разработайте алгоритм, предназначенный для вычисления наидлиннейшей монотонно неубывающей подпоследовательности данной последовательности, состоящей из и чисел.
Время работы апгоритма должно быть равно 0(пй). 15.4.6 * Разработайте алгоритм, предназначенный для вычисления наидлиннейшей монотонно неубывающей подпоследовательности данной последовательности, состоящей из и чисел. Время работы алгоритма должно быть равно 0(п 1к и). (Указание: обратите внимание, что последний элемент кандидата в искомую подпоследовательность длиной т по величине не меньше последнего элемента кандидата длиной т — 1.) 15.5. Оптимальные бинарные деревья пояска Предположим, что разрабатывается программа, предназначенная для перевода текстов с русского языка на украинский. Для каждого русского слова необходимо найти украинский эквивалент. Один из возможных путей поиска — построение бинарного дерева поиска с и русскими словами, выступакнцими в роли ключей, и украинскими эквивалентами, игриощими роль сопутствующих данных. Поскольку поиск с помощью этого дерева будет производиться для каждого отдельного слова из текста, полное затраченное на него время должно быть как можно меньше.
С помощью красно-черного дерева или любого другого сбалансированного бинарного дерева поиска можно добиться того, что время каждого отдельного поиска будет равным О(1я и). Однако слова встречаются с разной частотой, и может получиться так, что какое-нибудь часто употребляемое слово (например, предлог или союз) находится далеко от корня, а такое редкое слово, как контрйстреча, — возле корня.
Подобный способ организации привел бы к замедлению перевода, поскольку количество узлов, просмотренных в процессе поиска ключа в бинарном дереве, равно увеличенной на единицу глубине узла, содержащего данный ключ. Нужно сделать так, чтобы слова, которые встречаются в тексте часто, были размещены поближе к корню.т Кроме того, в исходном тексте могут встречаться слова„для которых перевод отсутствует. Таких слов может вообще не оказаться в бинарном дереве поиска. Как организовать бинарное дерево поиска, чтобы свести к минимуму количество посещенных в процессе поиска узлов, если известно, с какой частотой встречаются слова? То, что мы хотим получить, называется оптимальное бинарное дерево явис«я (орбша1 Ьшагу зеагсЬ атее). Приведем формальное описание задачи.
Имеется Впрочем, олнн н те же слова в текстал разной тематики могут встречаться с ратной частотой. Часть 1К Усовершенствованные методы разрабатан ь =. -е ь: (а) Рис. 15.9. Два бинарных дерева поиска длв множества ит и = б кточей со следующими веролтноствми. (а) Бинарное дерево поиска с ожидаемой стоимостью поиска 2.80. (б) Бинарное дерево поиска с ожидаемой стоимостью поиска 2.75. Это дерево — оптимальное.
,р р' + ~ 91 = 1 8=1 1=0 (15.10) Поскольку вероятность поиска каждого обычного и фиктивного ключа известна, можно определить математическое ожидание стоимости поиска по заданному бинарному дереву поиска Т. Предположим, что фактическая стоимость поиска определяется количеспюм проверенных узлов, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
