Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 91
Текст из файла (страница 91)
В рассматриваемом примере наидлиннейшая последовательность Яз имеет вид 6ТС6ТС66АА6СС66СС6АА. Последнее из упомянутых выше понятий подобия формализуется в виде задачи о наидлиннейшей общей подпоследовательности. Подпоследовательность двиной последовательности — это просто данная последовательность, из которой удалили нуль или более элементов.
Формально последовательность с (гп гз,..., зь) является подпоследоаательносеьт (впЪвейоепсе) последовательности Х = (хм хз,..., х ), если существует строго возрастающая последовательность (ем (з,..., (ь) индексов Х, такая, что для всех 5 = 1, 2,..., )с выполняется соотношение хч = г;ч Например, В = (В, С, Р, В) представляет собой подпоследовательность последовательности Х = (А, В, С, В, Р, А, В), причем аютвегствуюшая ей последовательность индексов имеет вид (2, 3, б, 7).
Говорят, что последовательность Я является общей подпоследоааеельностью (сопппоп впЬведцепсе) последовательностей Х и У, если Я является подпоследовательностью как Х, так и У. Например, если Х = (А, В, С, В, Р, А, В) и У = (В, Р, С, А, В, А), то последовательность (В, С, А) является общей подпоследовательностью Х и У. Однако последовательность (В, С, А) — не наидлиннейшая общая подлоследовательность Х и У, поскольку ее длина равна 3, а длина последовательности (В, С, В, А), которая также является общей подпоследовательностью Х и У, равна 4.
Последовательность (В, С, В, А) — наидлиннейшая общая подпоследовательность (1опкев1 сопппоп впЬвейоепсе — ЕСВ) последовательностей Х и У, как и последовательность (В, Р, А, В), поскольку не существует общей подпоследовательности длиной 5 элементов или более. В задаче о наидлпннейшей общей подпоследоаательностн задаются две последовательности, Х = (хз, хз,..., х ) и У = (ум уз,..., у„), и требуется найти общую подлоследовательность Х и У максимальной длины. В данном разделе показано, что эта задача эффективно решается методом динамического программирования.
Этап 1. Характеристика иаидлиииейшей общей подпоследовательности Решение задачи поиска наидлиннейшей общей подпоследовательности "в лоб" заключается в том, чтобы перечислить все подпоследовательности последовательности Х и проверить, являются ли они также подпоследовательностями У, пытаясь отыскать при этом наидлиннейшую из них. Каждая подпоследовательность последовательности Х соответствует подмножеству индексов (1,2,...,еп) последовательности Х. Всего имеется 2™ подпоследовательностей последовательности Х, поэтому время работы алгоритма, основанного на этом подходе, будет экспоненциально зависеть от размера задачи, и для длинных последовательностей он становится непригодным.
Однако задача поиска наидлиннейшей общей подпоследовательности обладает оптимальной подструктурой. Этот факт доказывается в сформулированной ниже 42б Часть Лс Усовершенствованные методы равоаботнн н анавооа теореме. Как мы увидим, естественно возникающие классы подзадач соответствуют парам "префиксов" двух входных последовательностей.
Дадим точное определение этого понятия: 1-м префиксам последовательности Х = (х1, хг,..., х ) для 1 = 1,2,...,т является подпоследовательность Х, = (х1,хг,...,х,). Например, если Х = (А,В, С, В,Р, А, В), то Х4 = (А, В, С, В), а Хо представляет собой пустую последовательность. Теорема 15.1 (Оптимальная подструктура 1.СБ) Пусть имеются последовательности Х = (х1, хг,, х ) и У = (У1, Уг .
Уо) и пУсть Я = (г1, гг,..., гь) — наиДлиннейшаа обЩаЯ поДпослеДовательность Х и У. !. Если х = у„, то гь = х = у„и Яь 1 — ЕСБ последовательностей Х н Уп — 1 ° 2. Если х ф у„, то из ха нь х вытекает, что Я представляет собой (.СВ последовательностей Х 1 и У. 3. Если хт ф усо то нз гь ф у„вытекаег, что Я представляет собой (.СБ последовательностей Х и У Доказательставх (1) Если бы выполнялось соотношение гь ~ х, то к последовательности Я можно было бы добавить элемент х = усо в результате чего получилась бы общая подпоследовательность последовательностей Х и У длиной 14 + 1, а это противоречит предположению о том, что о — наидлиннейиеая общая подпоследовательность последовательностей Х и У. Таким образом, должно выполняться соотношение гь = х = у„.
Итак, префикс Яь 1 — общая подпоследовательность последовательностей Х 1 и У„1 длиной й — 1. Нужно показать, что это наидлиннейшая общая подпоследовательность. Проведем доказательство методом от противного. Предположим, что имеется общая подпоследовательность Ис последовательностей Х 1 и У„н длина которой превышает /с — 1. Добавив к И' элемент х = у„, получим общую подпоследовательность последовательностей Х и У, длина которой превышает /4, что приводит к противоречию. (2) Если гь ~ х, то Я вЂ” общая подпоследовательность последовательностей Х 1 и У.
Если бы существовала общая подпоследовательность И' последовательностей Х 1 и У, длина которой превышала бы /4, то она была бы также общей подпоследовательностью последовательностей Х„, и У, что противоречит предположению о том, что о — наидлиннейшая общая подпоследовательность последовательностей Х и У. (3) Доказательство симметрично (2).
Из теоремы 15.1 видно, что наидлиннейшая общая подпоследовательность двух последовательностей содержит в себе наидлиннейшую общую подпоследовательность их префиксов. Таким образом, задача о наидлиннейшей общей подпоследовательности обладает оптимальной подструктурой. В рекурсивном решении этой задачи также возникают перекрывающиеся подзадачи, но об этом речь пойдет чуть позже.
Глава ! а динамическое программирование Этап 2. Рекурсивное решение Из теоремы 15.1 следует, что при нахождении наидлиннейшей общей подлоследоаательности последовательностей Х = (хы хз,..., х,„) и У = (ум уз, ..., у„) возникает одна или две подзадачи. Если х,„= уео необходимо найти иаидлиннейшую общую подпоследовательность последовательностей Хео 1 я У„п Добавив к ней элемент х = у„, получим ЬСБ последовательностей Х я У.
Если х ф уво необходимо решить две подзадачи: найти ЬСБ последовательностей Х 1 и У, а также последовательностей Х и У„ь Какая из этих двух подпоследовательностей окажется длиннее, та и будет наидлиннейшей обшей подпоследовательностью последовательностей Х и У. Поскольку эти случаи исчерпывают все возможности, мы знаем, что одно из оптимальных решений подзадач должно находиться в ЬСБ Х и У. В задаче поиска наидлиннейшей обшей подпоследовательности легко увидеть проявление свойства перекрывающихся подзадач.
Чтобы найти ЬСБ последовательностей Х и У, может понадобиться найти ЬСВ последовательностей Х и У„п а также последовательностей Х з и У. Однако в каждой из этих подзадач возникает подзадача поиска ЬСБ последовательностей Х,„з и У„п Общие подзадачи возникают и во многих других случаях. Как и в задаче о перемножении цепочки матриц, в рекурсивном решении задачи о наидлиннейшей общей подпоследовательности устанавливается рекуррентяое соотношение для значений, характеризующих оптимальное решение. Обозначим через с]ЬЯ длину наидлиннейшей общей подпоследовательности последовательностей Х, и Уг. Если 1 = О или з = О, длина одной из этих последовательностей равна нулю, поэтому наидлиннейшая их общая подпоследовательность имеет нулевую длину.
Оптимальная вспомогательная подструктура задачи о иаидлиннейшей обшей подпоследовательности определяется рекурсивной формулой О, если 1 = О или 1 = О, с]Ь1] = с[1 — 1,1 — 1]+1, если Ьз ) О и х, = у, (159) шах(с]Ь з — 1], с(е — 1, 1]), если Ь 1 ) О и х, ф у Обратите внимание, что в этой рекурсивной формулировке условия задачи ограничивают круг рассматриваемых подзадач. Если х, = у, можно и нужно рассматривать подзадачу поиска наидлиннейшей общей подпоследовательности последовательностей Х; 1 и Уз ь В противном случае рассматриваются две подзадачи поиска ЬСБ последовательностей Х, и 15 и а также Х, 1 и Уг.
В рассмотренных ранее алгоритмах, основанных на принципах динамического программирования (для задач о разрезании стержня и о перемножении цепочки матриц), выбор подзадач не зависел от условий задачи. Задача поиска ЬСБ не единственная, в которой вид возникающих подзадач определяется условиями задачи. В качестве другого подобного примера можно привести задачу о расстоянии редактирования (см. задачу 15.5). Часть Рк Усовершенствованные методы разработки и анализа 428 Этап 3.
Вычисление длины нандлиннейшей общей подпоследовательности Г.С8-1.а1нсзтН(Х, У) 1 тп = Х.1епдсл 2 п = К1епдгЬ 3 Ь(1..т,1..п] и с[О..т,О..п] — новыетаблицы 4 Гогг' = 1гот 5 с(г,О] = 0 6 Гогд' = Отоп 7 с(0,2] = 0 8 ГогГ =11от 9 Гог 2' = 1 Го п 1О 1Гх; ==у 11 с [в, 2'] = с[в — 1, 2 — Ц + 1 12 6[з,2] = ""," 13 е!ае1Гсз — 1 ' ) се ' — Ц [,2] [ 2 с[з,2'] = с[з — 1,2] Ь(з,2] = "Т" е)зе с[з,2] = с[з,2 — Ц 6[з, 2] = "4 —" вгп с и Ь 14 15 16 17 18 геГ На рис. 15.8 показаны таблицы, полученные в результате работы процедуры Г,СБ- Еннатн с последовательностями Х = (А,В,С,В,Р,А,В) и У = (В,Р,С,А,В, А). Время работы процедуры равно Н(тп), поскольку каждый элемент таблицы вычисляется за время Н(1).
Этап 4. Построение наидлиннейшей общей подпоследовательностн С помощью таблицы Ь, которая возвращается процедурой Г.СБ-1.внсзтн, можно быстро построить самую длинную общую подпоследовательность последо- На основе уравнения (15.9) легко написать рекурсивный алгоритм с экспоненциальным временем работы, предназначенный для вычисления длины Г.СБ двух последовательностей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
