Самая длинная возрастающая подпоследовательность - Longest increasing subsequence

В информатике самая длинная проблема возрастающей подпоследовательности состоит в том, чтобы найти подпоследовательность данной последовательности, в которой элементы подпоследовательности расположены в отсортированном порядке, от наименьшего к наибольшему, и в которой подпоследовательность является максимально длинной. Эта подпоследовательность не обязательно является непрерывной или уникальной. Самые длинные возрастающие подпоследовательности изучаются в контексте различных дисциплин , связанных с математикой , в том числе алгоритмики , теории случайных матриц , теории представлений и физики . Задача самой длинной возрастающей подпоследовательности решается за время O ( n log n ), где n обозначает длину входной последовательности.

Пример

В первых 16 членах двоичной последовательности Ван дер Корпута

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

самая длинная возрастающая подпоследовательность

0, 2, 6, 9, 11, 15.

Эта подпоследовательность имеет длину шесть; входная последовательность не имеет семичленных возрастающих подпоследовательностей. Самая длинная возрастающая подпоследовательность в этом примере - не единственное решение: например,

0, 4, 6, 9, 11, 15

0, 2, 6, 9, 13, 15

0, 4, 6, 9, 13, 15

другие возрастающие подпоследовательности равной длины в той же входной последовательности.

Связь с другими алгоритмическими проблемами

Проблема самой длинной возрастающей подпоследовательности тесно связана с самой длинной проблемой общей подпоследовательности , которая имеет решение динамического программирования с квадратичным временем : самая длинная возрастающая подпоследовательность последовательности S является самой длинной общей подпоследовательностью S и T , где T - результат сортировки S . Однако для особого случая, когда ввод представляет собой перестановку целых чисел 1, 2, ..., n , этот подход можно сделать гораздо более эффективным, что приведет к временным границам в форме O ( n log log n ).

Наибольшая клика в графе перестановок соответствует самой длинной убывающей подпоследовательности перестановки, которая определяет граф (при условии, что исходная неперестановочная последовательность отсортирована от наименьшего значения к наибольшему). Точно так же максимальный независимый набор в графе перестановок соответствует самой длинной неубывающей подпоследовательности. Следовательно, алгоритмы самой длинной возрастающей подпоследовательности могут использоваться для эффективного решения проблемы кликов в графах перестановок.

В соответствии Робинсона-Шенстеда между перестановками и таблицами Юнга длина первой строки таблицы, соответствующей перестановке, равна длине самой длинной возрастающей подпоследовательности перестановки, а длина первого столбца равна длине самой длинной убывающая подпоследовательность.

Эффективные алгоритмы

Алгоритм, описанный ниже, эффективно решает самую длинную проблему возрастающей подпоследовательности с помощью массивов и двоичного поиска . Он обрабатывает элементы последовательности по порядку, сохраняя самую длинную возрастающую подпоследовательность, найденную до сих пор. Обозначим значения последовательности как и т. Д. Тогда после обработки алгоритм сохранит значения в двух массивах: ${\ Displaystyle Х [0], Х [1], \ ldots,}$ ${\ Displaystyle X [я],}$

${\ displaystyle M [j]}$ - сохраняет индекс наименьшего значения , так что существует возрастающая подпоследовательность длины, заканчивающаяся на диапазоне ( необходимо сделать этот оператор более понятным ). Таким образом, если обозначает набор всех индексов, таких что и существует возрастающая подпоследовательность длины, заканчивающаяся на (то есть существуют индексы, заканчивающиеся такой, что ), то это индекс, для которого выполняется следующее: и (или, что то же самое, и для каждый ). Обратите внимание, что потому что представляет длину возрастающей подпоследовательности и представляет индекс ее завершения. ${\ displaystyle k}$ ${\ displaystyle X [k]}$ ${\ displaystyle j}$ ${\ displaystyle X [k]}$ ${\ Displaystyle к \ Leq я}$ ${\ displaystyle K_ {i, j}}$ ${\ displaystyle k}$ ${\ Displaystyle к \ Leq я}$ ${\ displaystyle j}$ ${\ displaystyle X [k]}$ ${\ displaystyle j}$ ${\ Displaystyle l_ {1} <l_ {2} <\ cdots <l_ {j} = k}$ ${\ displaystyle k}$ ${\ Displaystyle X \ влево [L_ {1} \ вправо] \ Leq X \ влево [L_ {2} \ вправо] \ Leq \ cdots \ Leq X \ влево [к \ вправо]}$ ${\ displaystyle M [j]}$ ${\ displaystyle M [j] \ in K_ {i, j}}$ ${\ Displaystyle Икс [M [j]] = \ min _ {k \ in K_ {i, j}} X [k]}$ ${\ displaystyle M [j] \ in K_ {i, j}}$ ${\ displaystyle k \ in K_ {i, j},}$ ${\ Displaystyle Икс [M [J]] \ Leq X [k]}$ ${\ displaystyle j \ leq i + 1,}$ ${\ displaystyle j \ geq 1}$ ${\ Displaystyle к \ geq 0}$
${\ displaystyle P [k]}$ - сохраняет индекс предшественника в самой длинной возрастающей подпоследовательности, заканчивающейся на ${\ displaystyle X [k]}$ ${\ displaystyle X [k].}$

Кроме того, алгоритм сохраняет переменную L, представляющую длину самой длинной возрастающей подпоследовательности, найденной на данный момент. Поскольку алгоритм ниже использует нулевую основу нумерации , для ясности дополняется который идет неиспользованным таким образом , что соответствует подпоследовательности длина реальной реализации можно пропустить и корректировать индексы соответственно. ${\ displaystyle M}$ ${\ displaystyle M [0],}$ ${\ displaystyle M [j]}$ ${\ displaystyle j.}$ ${\ displaystyle M [0]}$

Обратите внимание, что в любой точке алгоритма последовательность

{\ Displaystyle Икс [M [1]], Икс [M [2]], \ ldots, X [M [L]]}

повышается. Ибо, если существует возрастающая подпоследовательность длины, заканчивающаяся на, тогда существует также подпоследовательность длины, заканчивающаяся на меньшем значении: а именно подпоследовательность, заканчивающаяся на. Таким образом, мы можем выполнять двоичный поиск в этой последовательности за логарифмическое время.

{\ displaystyle j \ geq 2}

{\ displaystyle X [M [j]],}

{\ displaystyle j-1}

{\ Displaystyle X [P [M [j]]].}

Таким образом, алгоритм работает следующим образом:

Демо кода.

P = array of length N
M = array of length N + 1

L = 0
for i in range 0 to N-1:
    // Binary search for the largest positive j ≤ L
    // such that X[M[j]] < X[i]
    lo = 1
    hi = L + 1
    while lo < hi:
        mid = lo + floor((hi-lo)/2)
        if X[M[mid]] < X[i]:
            lo = mid+1
        else:
            hi = mid

    // After searching, lo is 1 greater than the
    // length of the longest prefix of X[i]
    newL = lo

    // The predecessor of X[i] is the last index of 
    // the subsequence of length newL-1
    P[i] = M[newL-1]
    M[newL] = i
    
    if newL > L:
        // If we found a subsequence longer than any we've
        // found yet, update L
        L = newL

// Reconstruct the longest increasing subsequence
S = array of length L
k = M[L]
for i in range L-1 to 0:
    S[i] = X[k]
    k = P[k]

return S

Поскольку алгоритм выполняет одиночный двоичный поиск для каждого элемента последовательности, его общее время может быть выражено с использованием нотации Big O как O ( n log n ). Фредман (1975) обсуждает вариант этого алгоритма, который он приписывает Дональду Кнуту ; в варианте, который он изучает, алгоритм проверяет, может ли каждое значение использоваться для расширения текущей самой длинной возрастающей последовательности за постоянное время, прежде чем выполнять двоичный поиск. С этой модификацией алгоритм использует не более n log ₂n - n log ₂ log ₂n + O ( n ) сравнений в худшем случае, что является оптимальным для алгоритма на основе сравнения с точностью до постоянного множителя в O ( n ) срок. ${\ Displaystyle X [я]}$

Границы длины

Согласно теореме Эрдеша – Секереса , любая последовательность из n ² +1 различных целых чисел имеет возрастающую или убывающую подпоследовательность длины n + 1. Для входов, в которых каждая перестановка входных данных одинаково вероятна, ожидаемая длина наибольшего увеличения подпоследовательность составляет примерно 2 √ n . В пределе, когда n приближается к бесконечности, длина самой длинной возрастающей подпоследовательности случайно переставленной последовательности из n элементов имеет распределение, приближающееся к распределению Трейси – Уидома , распределению наибольшего собственного значения случайной матрицы в гауссовском унитарном ансамбле .

Онлайн-алгоритмы

Самая длинная возрастающая подпоследовательность также изучалась в настройке онлайн-алгоритмов , в которых элементы последовательности независимых случайных величин с непрерывным распределением F - или, альтернативно, элементы случайной перестановки - представляются по одному алгоритму, который должны решить, включать или исключать каждый элемент, не зная о последующих элементах. В этом варианте задачи, который позволяет использовать интересные приложения в нескольких контекстах, можно разработать оптимальную процедуру выбора, которая, учитывая случайную выборку размера n в качестве входных данных, будет генерировать возрастающую последовательность с максимальной ожидаемой длиной размером приблизительно √ 2н . Длина возрастающей подпоследовательности, выбранной этой оптимальной процедурой, имеет дисперсию, приблизительно равную √ 2n / 3 , а ее предельное распределение асимптотически нормально после обычного центрирования и масштабирования. Те же самые асимптотические результаты верны с более точными оценками для соответствующей задачи в случае пуассоновского процесса прихода. Дальнейшее уточнение процесса Пуассона дается посредством доказательства центральной предельной теоремы для процесса оптимального выбора, которая выполняется с подходящей нормализацией в более полном смысле, чем можно было бы ожидать. Доказательство дает не только «правильную» функциональную предельную теорему, но также (сингулярную) ковариационную матрицу трехмерного процесса, суммирующую все взаимодействующие процессы.

заявка

Часть системы MUMmer (поиск максимального уникального совпадения) для выравнивания полных геномов.
Используется в системах контроля версий, таких как Git и т. Д.
Используется в Patience Diff, алгоритме сравнения (вычисляет и отображает различия между содержимым файлов), который используется в «Bazaar» (Bazaar - это система контроля версий, которая помогает вам отслеживать историю проекта с течением времени и легко сотрудничать с другими ..)

Смотрите также

Сортировка терпения , эффективный метод определения длины самой длинной возрастающей подпоследовательности
Плактический моноид , алгебраическая система, определяемая преобразованиями, сохраняющими длину самой длинной возрастающей подпоследовательности
Анатолий Вершик , русский математик, изучавший приложения теории групп к самым длинным возрастающим подпоследовательностям.
Самая длинная общая подпоследовательность
Самая длинная чередующаяся подпоследовательность

Languages

In other projects