Кратчайшая общая проблема суперпоследовательности - Shortest common supersequence problem

В Информатика, то кратчайшая общая суперпоследовательность двух последовательностей Икс и 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=m+n}$ выполняется для любых двух входных последовательностей.

Нет подобной взаимосвязи между самыми короткими общими суперпоследовательностями и самыми длинными общими подпоследовательностями трех или более входных последовательностей. (В частности, LCS и SCS не двойные проблемы.) Однако обе проблемы можно решить в ${\displaystyle O(n^{k})}$ время с использованием динамического программирования, где ${\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{aligned}\{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\}\}\}\\\end{aligned}}}$

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

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

1. Дэвид Майер (1978). «Сложность некоторых задач о подпоследовательностях и суперпоследовательностях». J. ACM. ACM Press. 25 (2): 322–336. Дои:10.1145/322063.322075.
2. Кари-Йоуко Райха, Эско Укконен (1981). «Самая короткая общая задача суперпоследовательностей над двоичным алфавитом является NP-полной». Теоретическая информатика. 16 (2): 187–198. Дои:10.1016 / 0304-3975 (81) 90075-х.
3. Тао Цзян и Мин Ли (1994). «Об аппроксимации кратчайших общих суперпоследовательностей и самых длинных общих подпоследовательностей». SIAM Журнал по вычислениям. 24 (5): 1122–1139. Дои:10.1137 / s009753979223842x.
4. Марек Карпински и Ричард Шмид (2013). "Об улучшенных результатах о несовместимости кратчайшей суперструны и связанных с ней задачах" (PDF). Материалы 19-го CATS CRPIT. 141: 27–36.
5. Вазирани, п. 20. ошибка sfn: цель отсутствует: CITEREFVazirani (помощь)

• Гарей, Майкл Р.; Джонсон, Дэвид С. (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

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

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