Jump to content

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

В информатике самая короткая общая суперпоследовательность двух последовательностей 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 соответственно.

  1. ^ Дэвид Майер (1978). «Сложность некоторых задач о подпоследовательностях и суперпоследовательностях» . Дж. АКМ . 25 (2). ACM Press: 322–336. дои : 10.1145/322063.322075 . S2CID   16120634 .
  2. ^ Кари-Йуко Райха, Эско Укконен (1981). «Самая короткая общая задача суперпоследовательности в двоичном алфавите является NP-полной». Теоретическая информатика . 16 (2): 187–198. дои : 10.1016/0304-3975(81)90075-х .
  3. ^ Маттиас Энглерт, Николаос Мацакис и Павел Весел (2022 г.). «Улучшенная гарантия аппроксимации кратчайших суперстрок с использованием классификации циклов по соотношению перекрытия и длины» . Материалы 54-го ежегодного симпозиума ACM SIGACT по теории вычислений (PDF) . стр. 317–330. дои : 10.1145/3519935.3520001 . ISBN  9781450392648 . S2CID   243847650 .
  4. ^ Вазирани , с. 20.
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: abde853f12fb59b45ab98bf40e79a8f7__1701575040
URL1:https://arc.ask3.ru/arc/aa/ab/f7/abde853f12fb59b45ab98bf40e79a8f7.html
Заголовок, (Title) документа по адресу, URL1:
Shortest common supersequence - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)