WikiDer > Кратчайшая общая проблема суперпоследовательности

В Информатика, то кратчайшая общая суперпоследовательность двух последовательностей Икс и Y - кратчайшая последовательность, имеющая Икс и Y в качестве подпоследовательности. Это проблема, тесно связанная с проблема самой длинной общей подпоследовательности. Учитывая две последовательности Икс = <х₁,...,Икс_м > и Y = <у₁, ..., y_п >, последовательность U = 1, ..., ты_k > - обычная суперпоследовательность Икс и Y если элементы могут быть удалены из U производить Икс и Y.

Кратчайшая общая суперпоследовательность (SCS) - это обычная суперпоследовательность минимальной длины. В самой короткой общей задаче суперпоследовательности две последовательности Икс и Y даны, и задача состоит в том, чтобы найти кратчайшую общую суперпоследовательность этих последовательностей. В общем, СКС не уникальна.

Для двух входных последовательностей SCS может быть сформирован из самая длинная общая подпоследовательность (LCS) легко. Например, самая длинная общая подпоследовательность Икс${ displaystyle [1..m] = abcbdab}$ и Y${ displaystyle [1..n] = bdcaba}$ является Z${ displaystyle [1..L] = bcba}$. Вставив символы, отличные от LCS, в Z при сохранении их первоначального порядка получаем кратчайшую общую суперпоследовательность U${ displaystyle [1..S] = abdcabdab}$. В частности, уравнение ${ Displaystyle L + S = т + п}$ выполняется для любых двух входных последовательностей.

Нет подобной взаимосвязи между самыми короткими общими суперпоследовательностями и самыми длинными общими подпоследовательностями трех или более входных последовательностей. (В частности, LCS и SCS не двойные проблемы.) Однако обе проблемы можно решить в ${ Displaystyle О (п ^ {к})}$ время с использованием динамического программирования, где ${ displaystyle k}$ - количество последовательностей, а ${ displaystyle n}$ это их максимальная длина. Для общего случая произвольного числа входных последовательностей проблема заключается в NP-жесткий.^[1]

Кратчайшая общая суперструна

Тесно связанная проблема поиска строки минимальной длины, которая является суперстрокой конечного набора строк. S = { s₁,s₂,...,s_п } также NP-сложен.^[2] Кроме того, хорошие (постоянный коэффициент) приближения были найдены для среднего случая, но не для худшего случая.^[3][4] Однако его можно сформулировать как пример крышка утяжеленного набора таким образом, чтобы вес оптимального решения для установленного экземпляра обложки был менее чем в два раза больше длины самой короткой суперструны S. Затем можно использовать O (журнал (п)) - приближение для взвешенного покрытия множества, чтобы получить O (log (п)) - приближение для кратчайшей суперструны (заметим, что это нет приближение постоянного множителя).

Для любой строки Икс в этом алфавите определите п(Икс) как набор всех строк, которые являются подстроками Икс. Экземпляр я Комплект обложки формулируется следующим образом:

• Позволять M быть пустым.
• Для каждой пары струн s_я и s_j, если последний k символы s_я такие же, как и первые k символы s_j, затем добавьте строку в M который состоит из конкатенации с максимальным перекрытием s_я с s_j.
• Определить вселенную ${ displaystyle { mathcal {U}}}$ установленного экземпляра обложки, чтобы быть S
• Определите набор подмножеств вселенной как { п(Икс) | Икс ∈ S ∪ M }
• Определите стоимость каждого подмножества п(x) быть |Икс|, длина Икс.

Экземпляр я затем можно решить с помощью алгоритма взвешенного покрытия множества, и алгоритм может вывести произвольную конкатенацию строк Икс для которого алгоритм взвешенного покрытия выводит п(Икс).^[5]

Пример

Рассмотрим множество S = {abc, cde, fab}, который становится универсумом экземпляра обложки взвешенного набора. В этом случае, M = {abcde, fabc}. Тогда множество подмножеств вселенной

${ Displaystyle { begin {align} {P (x) | x in S cup M } & = {P (x) | x in {abc, cde, fab, abcde, fabc } } & = {P (abc), P (cde), P (fab), P (abcde), P (fabc) } } & = { {a, b, c, ab, bc, abc }, {c, d, e, cd, de, cde }, ldots, {f, a, b, c, fa, ab, bc, fab, abc, fabc } } } конец {выровнено}}}$

которые имеют стоимость 3, 3, 3, 5 и 4 соответственно.

Рекомендации

• Гарей, Майкл Р.; Джонсон, Дэвид С. (1979). Компьютеры и непреодолимость: руководство по теории NP-полноты. W.H. Фримен. п. 228 A4.2: SR8. ISBN 0-7167-1045-5. Zbl 0411.68039.
• Шпанковски, Войцех (2001). Анализ среднего случая алгоритмов на последовательностях. Серия Wiley-Interscience по дискретной математике и оптимизации. С предисловием Филиппа Флажоле. Чичестер: Вайли. ISBN 0-471-24063-X. Zbl 0968.68205.
• Вазирани, Виджай В. (2001), Алгоритмы аппроксимации, Springer-Verlag, ISBN 3-540-65367-8

внешняя ссылка

• Словарь алгоритмов и структур данных: кратчайшая общая суперпоследовательность