Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 85
Текст из файла (страница 85)
В этом случае можно сказать, что две цепочки молекул подобны, если для преобразования одной из них в другую потребовались бы только небольшие изменения. (Такой подход рассматривается в задаче 15-3.) Еще один способ определения степени подобия последовательностей Яь н Яз заключается в поиске третьей последовательности Яз, основания которой имеются как в Яы так и в Яз, при этом они следуют в одном и том же порядке, но не обязательно одно за другим.
Чем длиннее последовательность оз, тем более схожи последовательности Яь и Яз. В рассматриваемом примере самая длинная последовательность Вз имеет Вид СТСОТСССААССССССССАА. Последнее из упомянутых выше понятий подобия формализуется в виде задачи о самой длинной общей подпоследовательности. Подпоследовательность данной последовательности — это просто данная последовательность, из которой удалили ноль или больше элементов. Формально последовательность Я = = (зы хз,..., гь) является подпоследовотельностью (ьцЬзейиепсе) последовательности Х = (хы ха,..., х ), если существует строго возрастающая последовательность (гы 1з,..., (ь) индексов Х, такая что для всех у = 1,2,..., й выполняется соотношение х;,.
= г . Например, Я = (В, С, Р, В) — подпоследовательность Глава 15. Динамическое программирование 419 последовательности Х = (А, В, С, В, Р, А, В), причем соответствующая ей последовательность индексов имеет вид (2, 3, 5, 7). Говорят, что последовательность Я является общей подноследовательностьзо (сопппоп зпЬзес1пепсе) последовательностей Х и У, если Я является подпоследовательностью как Х, так и У. Например, если Х = (А,В,С,В,Р,А,В) и У = = (В, Р, С, А, В, А), то последовательность (В, С, А) — общая подпоследовательность Х и У. Однако последовательность (В, С, А) — не самая длинная общая подпоследовательность Х и У, поскольку ее длина равна 3, а длина последовательности (В, С, В, А), которая тоже является общей подпоследовательностью Х и У, равна 4.
Последовательность (В, С, В, А) — самая длинная общая подпоследовательность (1опяезс соплпоп ьпЬзес1пепсе, 1.СЯ) последовательностей Х и У, как и последовательность (В,Р, А, В), поскольку не существует общей подпоследовательности длиной 5 элементов или более. В задаче о самой длинной общей нодпоследовательности даются две последовательности Х = (хы хз,..., хт) и У = (уы уз,..., уп), и требуется найти общую подпоследовательность Х и У максимальной длины. В данном разделе показано, что эта задача эффективно решается методом динамичесюго программирования.
Этап 1: характеристика самой длинной общей подпоследовательности Решение задачи поиска самой длинной общей подпоследовательности "в лоб" заключается в том, чтобы пронумеровать все подпоследовательности последовательности Х и проверить„являются ли они также подпоследовательностями У, пытаясь отыскать при этом самую длинную из них. Каждая подпоследовательность последовательности Х соответствует подмножеству индексов (1, 2,..., т) последовательности Х. Всего имеется 2т подпоследовательностей последовательности Х, поэтому время работы алгоритма, основанного на этом подходе, будет экспоненциально зависеть от размера задачи, и для длинных последовательностей он становится непригодным.
Однаю задача поиска самой длинной общей подпоследовательности обладает оптимальной подструктурой. Этот факт доказывается в сформулированной ниже теореме. Как мы увидим, естественно возникающие классы вспомогательных задач соответствуют парам "префиксов" двух входных последовательностей. Дадим точное определение этого понятия: г-м преСРиксам последовательности Х = = (хы хз,..., х ) для г = 1,2,...,т является подпоследовательность Х; = = (хм ха,...,х ). Например,если Х = (А,В,С,В,Р,А,В),тоХ4 = (А,В,С, В), а Хо — пустая последовательность.
Часть 1Ч. Усовершенствованные методы разработки и анализа 420 Теорема 15.1 (Оптимальнаи подструктура 1.СЯ). Пусть имеются последовательности Х = (хыхз,...,х ) и У = (уырз,...,Р„), а Я = (вы аз,...,яь) — нх самая длинная общая подпоследовательность. 1. Если х„, = у„, то я = х,„= у„и Яь ~ — ЕСЯ последовательностей Х и1„ 2. Если х ф у„, то из гь ф х,„следует, что Я вЂ” самая длинная общая подпоследовательность последовательностей Х з и У.
3. Если х ф у„, то нз гь ~ у„следует, что Я вЂ” самая длинная общая подпоследовательность последовательностей Х и У„ Докжзательсзпво. (1) Если бы выполнялось соотношение хь ф х„, то к последовательности Я можно было бы добавить элемент х,„= у„, в результате чего получилась бы общая подпоследовательность последовательностей Х и У длиной )с+ 1, а это противоречит предположению о том, что Я вЂ” сания длинная общая подпоследовательность последовательностей Х и У. Таким образом, должно выполняться соотношение зь = х = р„.
Таким образом, префикс Уь ~ — общая подпоследовательность последовательностей Х ~ и У„~ длиной к — 1. Нужно показать, что это самая длинная общая подпоследовательность. Проведем доказательство методом от противного. Предположим, что имеется общая подпоследовательность И~ последовательностей Х,„ ~ и У„ ы длина которой превышает й — 1. Добавив к И' элемент х = у„, получим общую подпоследовательность последовательностей Х и У, длина которой превышает )с, что приводит к противоречию. (2) Если яь ф х,, то Я вЂ” общая подпоследовательность последовательностей Х ~ и У.
Если бы существовала общая подпоследовательность И~ последовательностей Х ~ и У, длина которой превышает й, то она была бы также общей подпоследовательностью последовательностей Х„,— : Х и У, что противоречит предположению о том, что Л вЂ” самая длинная общая подпоследовательность последовательностей Х и У. (3) Доказательство этого случая аналогично доказательству случая (2) с точностью до замены элементов последовательности Х соответствующими элементами последовательности У.
и И теоремы 15.1 видно, что самая длинная общая подпоследовательность двух последовательностей содержит в себе самую длинную общую подпоследовательность их префиксов. Таким образом, задача о самой длинной общей подпоследовательности обладает оптимальной подструктурой. В рекурсивном решении этой задачи также возникают перекрывающиеся вспомогательные задачи, но об этом речь пойдет в следующем разделе. Глава 15. Динамическое программирование 421 Этап 2: рекурсивное решение О при 1 = О или т' = О, с [г, у] = с [1 — 1, т' — 1] + 1 при1,т>оих;=у, шах (с [г, з — 1], с [1 — 1, т']) при 1, у' > О и х, ~ у . (15. 14) Обратите внимание, что в этой рекурсивной формулировке условия задачи ограничивают круг рассматриваемых вспомогательных задач.
Если х; = у, можно и нужно рассматривать вспомогательную задачу поиска самой длинной общей подпоследовательности последовательностей Х; 1 и Уу и В противном случае рассматриваются две вспомогательные задачи по поиску 1.СБ последовательностей Х; и Уу ы а также последовательностей Х; 1 и У;. В рассмотренных ранее алгоритмах, основанных на принципах динамического программирования (для задач о составлении расписания работы сборочного конвейера и о перемножении цепочки матриц), выбор вспомогательных задач не зависел от условий задачи. Задача о поиске 1СВ не единственная, в которой вид возникающих вспомогательных задач определяется условиями задачи. В качестве другого подобного примера можно привести задачу о расстоянии редактирования (см.
задачу 15-3). Из теоремы 15.! следует, что при нахождении самой длинной общей подпоследовательности последовательностей Х = (хы хз,..., х„Д и У = (уы уз,..., у„) возникает одна или две вспомогательные задачи. Если х = у„, необходимо найти самую длинную общую подпоследовательность последовательностей Х и У,„п Добавив к ней элемент х,п = у„, получим ЕСБ последовательностей Х и У.
Если х ф у„, необходимо решить две вспомогательных задачи: найти самые 18С последовательностей Х„, 1 и У, а также последовательностей Х и У„ Какая из этих двух подпоследовательностей окажется длиннее, та и будет самой длинной общей подпоследовательностью последовательностей Х и У. В задаче поиска самой длинной общей подпоследовательности легко увидеть проявление свойства перекрывающихся вспомогательных задач. Чтобы найти 1СЯ последовательностей Х и У, может понадобиться найти ЕСЯ последовательностей Х„, 1 и У, а также?,СЯ Х и У„п Однако в каждой из этих задач возникает задача о поиске ЕСЯ последовательностей Х 1 и У„п Общая вспомогательная задача возникает и во многих других подзадачах. Как и в задаче о перемножении цепочки матриц„в рекурсивном решении задачи о самой длинной общей подпоследовательности устанавливается рекуррентное соотношение для значений, характеризующих оптимальное решение.
Обозначим через с [г, Я длину самой длинной общей подпоследовательности последовательностей Х; и У'. Если г = О или у = О, длина одной из этих последовательностей равна нулю, поэтому самая длинная их общая подпоследовательность имеет нулевую длину. Оптимальная вспомогательная подструктура задачи о самой длинной общей подпоследовательности определяется формулой: Часть |Ч. Усовершенствованные методы разработки и анализа 422 Этап 3: вычисление длины самой длинной общей подпоследовательн ости На основе уравнения (15.14) легко написать рекурсивный алгоритм с экспоненциальным временем работы, предназначенный для вычисления длины ЬСБ двух последовательностей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
