Введение

В информатике кратчайшая общая суперпоследовательность двух последовательностей X и Y — это кратчайшая последовательность, содержащая X и Y в качестве подпоследовательностей. Эта задача тесно связана с задачей о наибольшей общей подпоследовательности. Для двух последовательностей X = <x1, ..., xm> и Y = <y1, ..., yn> последовательность U = <u1, ..., uk> является общей суперпоследовательностью X и Y, если из U можно удалить элементы, чтобы получить X и Y. Кратчайшая общая суперпоследовательность (SCS) — это общая суперпоследовательность минимальной длины. В задаче о кратчайшей общей суперпоследовательности заданы две последовательности X и Y, и требуется найти кратчайшую возможную общую суперпоследовательность этих последовательностей. В общем случае SCS не является единственной. Для двух входных последовательностей SCS можно легко сформировать из наибольшей общей подпоследовательности (LCS). Например, пусть наибольшая общая подпоследовательность X и Y — это Z. Вставляя в Z символы, не входящие в LCS, сохраняя при этом их исходный порядок, мы получаем кратчайшую общую суперпоследовательность U. В частности, для любых двух входных последовательностей выполняется следующее соотношение: . Аналогичной связи между кратчайшими общими суперпоследовательностями и наибольшими общими подпоследовательностями для трех и более входных последовательностей не существует. (В частности, LCS и SCS не являются двойственными задачами.) Однако обе задачи могут быть решены за время с помощью динамического программирования, где — количество последовательностей, а — их максимальная длина. Для общего случая произвольного числа входных последовательностей задача является NP-трудной.

Пример

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