- Задача поиска наибольшей увеличивающейся подпоследовательности
-
Задача поиска наибольшей увеличивающейся подпоследовательности состоит в отыскании наиболее длинной возрастающей подпоследовательности в данной последовательности элементов.
Содержание
Постановка задачи
Отметим, подпоследовательность может и не являться подстрокой (то есть, её элементы не обязательно идут подряд в исходной последовательности). Формально, для строки x длины n необходимо найти максимальное число l и соответствующую ему возрастающую последовательность индексов i1..il, таких что . Наибольшая увеличивающая подпоследовательность имеет применения в физике, математике, теории представления групп, теории случайных матриц. В общем случае известно решение этой задачи за время n log n[1] в худшем случае.
Родственные алгоритмы
- Задача наибольшей увеличивающейся подпоследовательности схожа с задачей поиска наибольшей общей подпоследовательности, имеющей квадратичное динамическое решение.
- В частном случае, если строка является перестановкой 1..n, задача имеет решение за n log log n[2] с использованием деревьев ван Эмде Боаса.
- При использовании дерева, построенного для элементов алфавита, возможно решение задачи за O( n log A ), где A - мощность алфавита, определяемая заранее. При реализации сбалансированными деревьями, необязательно задавать A наперёд. По очевидным причинам A ограничивается длиной строки.
- Возможно также свести задачу к поиску длиннейшего пути в ориентированном ациклическом графе, задавая рёбра между возрастающими элементами. Хотя подсчёт длиннейшего пути будет занимать линейное время от числа рёбер, в худшем случае оно может быть квадратично от длины строки.
Пример эффективного алгоритма
Для строки x будем хранить массивы M и P длины n. M[i] содержит наименьший по величине из последних элементов возрастающих подпоследовательностей xnj длины i, , найденных на данном шаге. P[i] хранит индекс предшествующего символа для наидлиннейшей возрастающей подпоследовательности, оканчивающейся в i-й позиции. На каждом шаге будем хранить текущий максимум длины подпоследовательности и соответствующий индекс конечного символа, не забывая поддерживать свойства массивов. Шаг представляет собой переход к следующему элементу строки, для каждого перехода потребуется не более логарифма времени (бинарный поиск по массиву M).
L = index = M[0] = 0 for i = 1 to n бинарный поиск наибольшего индекса j ≤ L, удовлетворяющего X[M[j]] < X[i] P[i] = M[j] if j == L or X[i] < X[M[j+1]] // нашли более оптимальную подпоследовательность M[j+1] = i L = max{L, j+1}
Очевидно, после выполнения алгоритма, L — длина искомой подпоследовательности, сами же элементы можно получить, разворачивая P рекурсивно из элемента index.
См. также
- ↑ Schensted, C. (1961). «Longest increasing and decreasing subsequences». Canadian Journal of Mathematics 13: 179—191.
- ↑ [1]Hunt, J.; Szymanski, T. (1977). «A fast algorithm for computing longest common subsequences». Communications of the ACM: 350—353.
Ссылки
Категория:- Строковые алгоритмы
Wikimedia Foundation. 2010.