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

В Информатика, то самая длинная возрастающая подпоследовательность проблема состоит в том, чтобы найти подпоследовательность заданного последовательность в котором элементы подпоследовательности отсортированы от наименьшего к наибольшему и в котором подпоследовательность является максимально длинной. Эта подпоследовательность не обязательно является непрерывной или уникальной. Наиболее длинные возрастающие подпоследовательности изучаются в контексте различных дисциплин, связанных с математика, в том числе алгоритмика, теория случайных матриц, теория представлений, и физика.[1] Задача самой длинной возрастающей подпоследовательности разрешима за время O (п бревно п), куда п обозначает длину входной последовательности.[2]

пример

В первых 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 и Т, куда Т это результат сортировка S. Однако для особого случая, когда ввод представляет собой перестановку целых чисел 1, 2, ..., п, этот подход можно сделать гораздо более эффективным, что приведет к временным ограничениям в виде O (п журнал журнал п).[3]

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

в Переписка Робинсона – Шенстеда между перестановки и Молодые картины длина первой строки таблицы, соответствующей перестановке, равна длине самой длинной возрастающей подпоследовательности перестановки, а длина первого столбца равна длине самой длинной убывающей подпоследовательности.[2]

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

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

M [j] - хранит индекс k наименьшего значения X [k] такая, что существует возрастающая подпоследовательность длины j оканчивается на X [k] в диапазоне k ≤ я (Необходимо сделать это утверждение более ясным). Обратите внимание, что j ≤ (я + 1), потому что j ≥ 1 представляет длину возрастающей подпоследовательности, а k ≥ 0 представляет индекс его завершения.
П[k] - хранит индекс предшественника X [k] в самой длинной возрастающей подпоследовательности, заканчивающейся на X [k].

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

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

X [M [1]], X [M [2]], ..., X [M [L]]

повышается. Ибо, если существует возрастающая подпоследовательность длины j ≥ 2 заканчиваются на X [M [j]], то существует также подпоследовательность длины j-1 с меньшим значением, а именно с тем, которое заканчивается на X [P [M [j]]]. Таким образом, мы можем выполнять двоичный поиск в этой последовательности за логарифмическое время.

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

Демо кода.
P = массив длины NM = массив длины N + 1L = 0за я в диапазоне 0 к N-1: // Бинарный поиск наибольшего положительного j ≤ L // такого, что X [M [j]] <= X [i] lo = 1 hi = L пока lo ≤ hi: mid = ceil ((lo + hi) / 2) если X [M [mid]] еще: hi = mid-1 // После поиска lo на 1 больше, чем // длина самого длинного префикса X [i] newL = lo // Предшественник X [i] - это последний индекс // подпоследовательности длины newL-1 P [i] = M [newL-1] M [newL] = i если newL> L: // Если мы нашли подпоследовательность длиннее любой // найденной нами, обновляем L L = newL // Реконструируем самую длинную возрастающую подпоследовательность S = массив длины Lk = M [L]за я в диапазоне L-1 к 0: S [i] = X [k] k = P [k]вернуть S

Поскольку алгоритм выполняет одиночный двоичный поиск для каждого элемента последовательности, его общее время может быть выражено с помощью Обозначение Big O как O (п бревноп). Фредман (1975) обсуждает вариант этого алгоритма, который он приписывает Дональд Кнут; в изучаемом варианте алгоритм проверяет, каждое ли значение X [я] можно использовать для расширения текущей самой длинной возрастающей последовательности за постоянное время до выполнения двоичного поиска. С этой модификацией алгоритм использует не более п бревно2 п − п бревно2бревно2 п + O (п) сравнения в худшем случае, который является оптимальным для алгоритма на основе сравнения с точностью до постоянного множителя в O (п) срок.[5]

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

Согласно Теорема Эрдеша – Секереса, любая последовательность п2+1 различных целых чисел имеет возрастающую или убывающую подпоследовательность длины п + 1.[6][7] Для входов, в которых каждая перестановка входа равновероятна, ожидаемая длина самой длинной возрастающей подпоследовательности составляет примерно 2√п.[8] В пределе как п приближается к бесконечности, длина самой длинной возрастающей подпоследовательности случайно переставленной последовательности п предметы имеют распределение, приближающееся к Распределение Трейси – Уидома, распределение наибольшего собственного значения случайной матрицы в Гауссовский унитарный ансамбль.[9]

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

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

Заявление


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

Рекомендации

  1. ^ Олдос, Дэвид; Диаконис, Перси (1999), «Самые длинные возрастающие подпоследовательности: от сортировки по терпению до теоремы Байка – Дейфта – Йоханссона», Бюллетень Американского математического общества, 36 (04): 413–432, Дои:10.1090 / S0273-0979-99-00796-X.
  2. ^ а б Шенстед, К. (1961), «Самые длинные возрастающие и убывающие подпоследовательности», Канадский математический журнал, 13: 179–191, Дои:10.4153 / CJM-1961-015-3, Г-Н  0121305.
  3. ^ Hunt, J .; Шиманский, Т. (1977), "Быстрый алгоритм вычисления самых длинных общих подпоследовательностей", Коммуникации ACM, 20 (5): 350–353, Дои:10.1145/359581.359603.
  4. ^ Голумбик, М.С. (1980), Алгоритмическая теория графов и совершенные графы, Компьютерные науки и прикладная математика, Academic Press, стр. 159.
  5. ^ Фредман, Майкл Л. (1975), «О вычислении длины самой длинной возрастающей подпоследовательности», Дискретная математика, 11 (1): 29–35, Дои:10.1016 / 0012-365X (75) 90103-X.
  6. ^ Эрдеш, Пол; Секерес, Джордж (1935), «Комбинаторная задача геометрии», Compositio Mathematica, 2: 463–470.
  7. ^ Стил, Дж. Майкл (1995), "Вариации на монотонную тему подпоследовательности Эрдеша и Секереша", в Олдос, Дэвид; Диаконис, Перси; Спенсер, Джоэл; и другие. (ред.), Дискретная вероятность и алгоритмы (PDF), Объемы IMA по математике и ее приложениям, 72, Springer-Verlag, стр. 111–131..
  8. ^ Вершик, А.М.; Керов, К. В. (1977), "Асимптотика планшеровской меры симметрической группы и предельная форма для таблиц Юнга", Докл. Акад. АН СССР, 233: 1024–1027.
  9. ^ Байк, Джинхо; Deift, Перси; Йоханссон, Курт (1999), "О распределении длины самой длинной возрастающей подпоследовательности случайных перестановок", Журнал Американского математического общества, 12 (4): 1119–1178, arXiv:математика / 9810105, Дои:10.1090 / S0894-0347-99-00307-0.
  10. ^ Сэмюэлс, Стивен. М .; Стил, Дж. Майкл (1981), «Оптимальный последовательный выбор монотонной последовательности из случайной выборки» (PDF), Анналы вероятности, 9 (6): 937–947, Дои:10.1214 / aop / 1176994265
  11. ^ Арлотто, Алессандро; Nguyen, Vinh V .; Стил, Дж. Майкл (2015), «Оптимальный онлайн-выбор монотонной подпоследовательности: центральная предельная теорема», Случайные процессы и их приложения, 125 (9): 3596–3622, arXiv:1408.6750, Дои:10.1016 / j.spa.2015.03.009
  12. ^ Брюсс, Ф. Томас; Дельбаен, Фредди (2001), «Оптимальные правила для последовательного выбора монотонных подпоследовательностей максимальной ожидаемой длины», Случайные процессы и их приложения, 96 (2): 313–342.
  13. ^ Брюсс, Ф. Томас; Delbaen, Freddy (2004), "Центральная предельная теорема для оптимального процесса выбора для монотонных подпоследовательностей максимальной ожидаемой длины", Случайные процессы и их приложения, 114 (2): 287–311, Дои:10.1016 / j.spa.2004.09.002.

внешняя ссылка