Задача о наименьшей суперпоследовательности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |definition= Последовательность <tex> Z = \left \langle z_1, z_2, \dots, z_k \right \rangle </tex> является '''...»)
(нет различий)

Версия 14:46, 23 декабря 2017

Определение:
Последовательность [math] Z = \left \langle z_1, z_2, \dots, z_k \right \rangle [/math] является подпоследовательностью (англ. subsequence) последовательности [math] X = \left \langle x_1, x_2, \dots, x_m \right \rangle [/math], если существует строго возрастающая последовательность [math] \left \langle i_1, i_2, \dots, i_k \right \rangle [/math] индексов [math] X [/math] таких, что для всех [math] j = 1, 2, \dots, k [/math] выполняется соотношение [math] x_{i_j} = z_j [/math].


Определение:
Последовательность [math] Z [/math] является общей суперпоследовательностью (англ. common supersequence) последовательностей [math] X [/math] и [math] Y [/math], если [math] X [/math] и [math] Y [/math] являются подпоследовательностями [math] Z [/math].


Задача:
Пусть имеются последовательности [math] X = \left \langle x_1, x_2, \dots, x_m \right \rangle [/math] и [math] Y = \left \langle y_1, y_2, \dots, y_n \right \rangle [/math]. Необходимо найти [math]SCS(X,Y)[/math]


Наивное решение

Заметим, что если приписать к одной из данной последовательность другую, то полученная последовательность будет их суперпоследовательностью с длиной [math] n + m [/math]. Запомним все элементы обеих последовательностей и из них построим все возможные последовательности. Тогда искомая [math]SCS[/math] гарантированно найдётся, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.