Кратчайшая общая суперпоследовательность
В информатике самая короткая общая суперпоследовательность двух последовательностей X и Y — это самая короткая последовательность, которая имеет X и Y в качестве подпоследовательностей . Эта проблема тесно связана с проблемой самой длинной общей подпоследовательности . Для двух последовательностей X = < x 1 ,...,x m > и Y = < y 1 ,...,y n > последовательность U = < u 1 ,...,uk > является общей суперпоследовательностью. X , и Y если элементы можно удалить из U, произвести X и Y. чтобы
Кратчайшая общая суперпоследовательность (SCS) — это общая суперпоследовательность минимальной длины. В задаче о кратчайшей общей суперпоследовательности заданы две последовательности X и Y , и задача состоит в том, чтобы найти кратчайшую общую суперпоследовательность этих последовательностей. В общем, СКС не уникален.
Для двух входных последовательностей SCS можно легко сформировать из самой длинной общей подпоследовательности (LCS). Например, самая длинная общая подпоследовательность X и Ю это Z . Вставляя символы, не относящиеся к LCS, в Z , сохраняя их исходный порядок, мы получаем кратчайшую общую суперпоследовательность U . В частности, уравнение справедливо для любых двух входных последовательностей.
Не существует аналогичной взаимосвязи между кратчайшими общими суперпоследовательностями и самыми длинными общими подпоследовательностями из трех или более входных последовательностей. (В частности, LCS и SCS не являются двойными задачами .) Однако обе задачи можно решить в время с использованием динамического программирования, где количество последовательностей, а это их максимальная длина. Для общего случая произвольного числа входных последовательностей проблема является NP-трудной . [1]
Кратчайшая общая суперстрока
[ редактировать ]Тесно связанная проблема поиска строки минимальной длины, которая является суперстрокой конечного набора строк S = { s 1 , s 2 ,..., s n }, также является NP-трудной. [2] На протяжении многих лет было предложено несколько аппроксимаций с постоянным коэффициентом, и самый известный на данный момент алгоритм имеет коэффициент аппроксимации 2,475. [3] Однако, возможно, самое простое решение — переформулировать задачу как пример покрытия взвешенного множества чтобы вес оптимального решения экземпляра покрытия множества был меньше, чем в два раза, длины кратчайшей суперстроки S. таким образом , Затем можно использовать O(log( n ))-аппроксимацию для взвешенного покрытия множества, чтобы получить O(log( n ))-аппроксимацию для кратчайшей суперстроки (обратите внимание, что это не аппроксимация с постоянным фактором).
Для любой строки x в этом алфавите определите P ( x ) как набор всех строк, которые являются подстроками x . Экземпляр I покрытия множества формулируется следующим образом:
- Пусть М пусто.
- Для каждой пары строк s i и s j , если последние k символов s i совпадают с первыми k символами s j , затем добавьте строку в M , которая состоит из конкатенации с максимальным перекрытием s i с s. Дж .
- Определите вселенную установленного экземпляра обложки как S
- Определите набор подмножеств вселенной как { P ( x ) | x ∈ S ∪ M }
- Определите стоимость каждого подмножества P (x) как | x |, длина x .
Затем случай I можно решить с использованием алгоритма покрытия взвешенного набора, и алгоритм может вывести произвольную конкатенацию строк x , для которых алгоритм покрытия взвешенного набора выводит P ( x ). [4]
Пример
[ редактировать ]Рассмотрим набор S = { abc, cde, fab }, который становится вселенной экземпляра покрытия взвешенного набора. В этом случае M = {abcde, fabc}. Тогда набор подмножеств Вселенной равен
которые имеют стоимость 3, 3, 3, 5 и 4 соответственно.
Ссылки
[ редактировать ]- ^ Дэвид Майер (1978). «Сложность некоторых задач о подпоследовательностях и суперпоследовательностях» . Дж. АКМ . 25 (2). ACM Press: 322–336. дои : 10.1145/322063.322075 . S2CID 16120634 .
- ^ Кари-Йуко Райха, Эско Укконен (1981). «Самая короткая общая задача суперпоследовательности в двоичном алфавите является NP-полной». Теоретическая информатика . 16 (2): 187–198. дои : 10.1016/0304-3975(81)90075-х .
- ^ Маттиас Энглерт, Николаос Мацакис и Павел Весел (2022 г.). «Улучшенная гарантия аппроксимации кратчайших суперстрок с использованием классификации циклов по соотношению перекрытия и длины» . Материалы 54-го ежегодного симпозиума ACM SIGACT по теории вычислений (PDF) . стр. 317–330. дои : 10.1145/3519935.3520001 . ISBN 9781450392648 . S2CID 243847650 .
- ^ Вазирани , с. 20.
- Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . У. Х. Фриман. п. 228 А4.2: СР8 . ISBN 0-7167-1045-5 . Збл 0411.68039 .
- Шпанковский, Войцех (2001). Анализ среднего случая алгоритмов на последовательностях . Серия Wiley-Interscience по дискретной математике и оптимизации. С предисловием Филиппа Флажоле. Чичестер: Уайли. ISBN 0-471-24063-Х . Збл 0968.68205 .
- Vazirani, Vijay V. (2001), Approximation Algorithms , Springer-Verlag, ISBN 3-540-65367-8