Алгоритмы - построение и анализ (1021735), страница 83
Текст из файла (страница 83)
Степень подобия можно определить многими различными способами. Например, можно сказать, что два кода ДНК подобны, если один из них является подстрокой другого. (Алгоритмы, с помощью которых решается эта задача, исследуются в главе 32.) В нашем примере ни Ям ни Вз не является подстрокой другой ДНК. В этом случае можно сказать, что две цепочки молекул подобны, если для преобразования одной из них в другую потребовались бы только небольшие изменения. (Такой подход рассматривается в задаче 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}
