В информатике самая длинная проблема возрастающей подпоследовательности состоит в том, чтобы найти подпоследовательность заданной последовательности, в которой элементы подпоследовательности расположены в отсортированном порядке, от самого низкого до самого высокого, и в котором подпоследовательность является максимально длинной. Эта подпоследовательность не обязательно является непрерывной или уникальной. Самые длинные возрастающие подпоследовательности изучаются в контексте различных дисциплин , связанных с математикой , в том числе алгоритмики , теории случайных матриц , теории представлений и физики . [1] Задача самой длинной возрастающей подпоследовательности разрешима за время O ( n log n), где n обозначает длину входной последовательности. [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 и T , где T - результат сортировки S . Однако для особого случая, когда ввод представляет собой перестановку целых чисел 1, 2, ..., n , этот подход можно сделать гораздо более эффективным, что приведет к временным ограничениям в форме O ( n log log n ). [3]
Наибольшая клика в графе перестановок соответствует самой длинной убывающей подпоследовательности перестановки, которая определяет граф (при условии, что исходная неперестановочная последовательность отсортирована от наименьшего значения к наибольшему). Точно так же максимальный независимый набор в графе перестановок соответствует самой длинной неубывающей подпоследовательности. Следовательно, алгоритмы самой длинной возрастающей подпоследовательности могут использоваться для эффективного решения проблемы кликов в графах перестановок. [4]
В соответствии Робинсона-Шенстеда между перестановками и таблицами Юнга длина первой строки таблицы, соответствующей перестановке, равна длине самой длинной возрастающей подпоследовательности перестановки, а длина первого столбца равна длине самой длинной убывающая подпоследовательность. [2]
Эффективные алгоритмы [ править ]
Алгоритм, описанный ниже, эффективно решает самую длинную проблему возрастающей подпоследовательности с помощью массивов и двоичного поиска . Он обрабатывает элементы последовательности по порядку, сохраняя самую длинную на данный момент возрастающую подпоследовательность. Обозначим значения последовательности как X [0], X [1] и т. Д. Затем, после обработки X [ i ], алгоритм сохранит значения в двух массивах:
- M [ j ] - хранит индекс k наименьшего значения X [ k ], так что существует возрастающая подпоследовательность длины j, заканчивающаяся в X [ k ] в диапазоне k ≤ i ( необходимо сделать это утверждение более понятным ). Обратите внимание, что j ≤ (i + 1) , поскольку j ≥ 1 представляет длину возрастающей подпоследовательности, а k ≥ 0 представляет индекс ее завершения.
- P [ 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для i в диапазоне от 0 до N-1: // Бинарный поиск наибольшего положительного j ≤ L // такое, что X [M [j]] <= X [i] lo = 1 привет = L пока lo ≤ hi: mid = ceil ((lo + hi) / 2) если X [M [mid]] <X [i]: lo = mid + 1 еще : привет = середина 1 // После поиска lo на 1 больше, чем // длина самого длинного префикса X [i] newL = lo // Предшественником X [i] является последний индекс // подпоследовательность длины newL-1 P [i] = M [newL-1] M [newL] = я если newL> L: // Если мы нашли подпоследовательность длиннее любой, мы // пока не нашел, обновить L L = новыйL// Восстановить самую длинную возрастающую подпоследовательностьS = массив длины Lk = M [L]для i в диапазоне от L-1 до 0: S [i] = X [k] k = P [k]вернуть S
Поскольку алгоритм выполняет одиночный двоичный поиск для каждого элемента последовательности, его общее время может быть выражено с использованием нотации Big O как O ( n log n ). Фредман (1975) обсуждает вариант этого алгоритма, который он приписывает Дональду Кнуту ; в варианте, который он изучает, алгоритм проверяет, может ли каждое значение X [ i ] использоваться для расширения текущей самой длинной возрастающей последовательности за постоянное время, прежде чем выполнять двоичный поиск. С этой модификацией алгоритм использует не более n log 2 n - n log 2 log 2 n + O ( n )сравнения в худшем случае, который является оптимальным для алгоритма на основе сравнения с точностью до постоянного множителя в члене O ( n ). [5]
Ограничения длины [ править ]
Согласно теореме Эрдеша – Секереса , любая последовательность из n 2 +1 различных целых чисел имеет возрастающую или убывающую подпоследовательность длины n + 1. [6] [7] Для входов, в которых каждая перестановка входных данных одинаково вероятна, ожидаемая длина самой длинной возрастающей подпоследовательности составляет примерно 2 √ n . [8] В пределе, когда n приближается к бесконечности, длина самой длинной возрастающей подпоследовательности случайной перестановки последовательности из n элементов имеет распределение, приближающееся к распределению Трейси – Уидома , распределению наибольшего собственного значения случайной матрицы вГауссовский унитарный ансамбль . [9]
Онлайн-алгоритмы [ править ]
Самая длинная возрастающая подпоследовательность также изучалась в настройке онлайн-алгоритмов , в которых элементы последовательности независимых случайных величин с непрерывным распределением F - или, альтернативно, элементы случайной перестановки - представляются по одному алгоритму, который должны решить, включать или исключать каждый элемент, не зная о последующих элементах. В этом варианте задачи, который позволяет использовать интересные приложения в нескольких контекстах, можно разработать оптимальную процедуру выбора, которая, учитывая случайную выборку размера n в качестве входных данных, будет генерировать возрастающую последовательность с максимальной ожидаемой длиной размером приблизительно √ 2н .[10] Длина возрастающей подпоследовательности, выбранной этой оптимальной процедурой, имеет дисперсию, приблизительно равную √ 2n / 3 , и ее предельное распределение асимптотически нормально после обычного центрирования и масштабирования. [11] Те же самые асимптотические результаты верны с более точными оценками для соответствующей задачи в случае пуассоновского процесса прихода. [12] Дальнейшее уточнение процесса Пуассона дается посредством доказательства центральной предельной теоремыдля оптимального процесса выбора, который выполняется с подходящей нормализацией в более полном смысле, чем можно было бы ожидать. Доказательство дает не только «правильную» функциональную предельную теорему, но также (сингулярную) ковариационную матрицу трехмерного процесса, суммирующую все взаимодействующие процессы.[13]
Заявление [ править ]
Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( Май 2019 г. ) |
См. Также [ править ]
- Сортировка терпения , эффективный метод определения длины самой длинной возрастающей подпоследовательности
- Плактический моноид , алгебраическая система, определяемая преобразованиями, сохраняющими длину самой длинной возрастающей подпоследовательности
- Анатолий Вершик , русский математик, изучавший приложения теории групп к самым длинным возрастающим подпоследовательностям.
- Самая длинная общая подпоследовательность
- Самая длинная чередующаяся подпоследовательность
Ссылки [ править ]
- ↑ Олдос, Дэвид ; Diaconis, Persi (1999), "Наибольшая увеличение подпоследовательности: от терпения сортировочный к теореме Baik-Deift-Johansson", Бюллетень Американского математического общества , 36 (04): 413-432, DOI : 10,1090 / S0273-0979-99 -00796-X.
- ^ Б Шенстеда, С. (1961), "Серия увеличения и уменьшения подпоследовательности", Canadian Journal математики , 13 : 179-191, DOI : 10,4153 / CJM-1961-015-3 , МР 0121305 .
- ^ Хант, J .; Шиманьский, Т. (1977), "Быстрый алгоритм для вычисления наибольшей общей подпоследовательности", коммуникации ACM , 20 (5): 350-353, DOI : 10,1145 / 359581,359603 .
- ^ Голумбик, MC (1980), Алгоритмическая теория графов и совершенные графы , информатика и прикладная математика, Academic Press, стр. 159.
- ^ Фредман, Майкл Л. (1975), «О вычислении длины самых длинных возрастающих подпоследовательностей», Дискретная математика , 11 (1): 29–35, DOI : 10.1016 / 0012-365X (75) 90103-X.
- ^ Erdős, Пол ; Секерес, Джордж (1935), "Комбинаторная задача в геометрии" , Compositio Mathematica , 2 : 463–470.
- ↑ Стил, Дж. Майкл (1995), «Вариации на монотонную тему подпоследовательности Эрдёша и Секереса», в Олдосе, Дэвид ; Диаконис, Перси ; Спенсер, Джоэл ; и другие. (ред.), Дискретная вероятность и алгоритмы (PDF) , Объемы IMA по математике и ее приложениям, 72 , Springer-Verlag, стр. 111–131 .
- ^ Вершик, AM ; Керов, Ц.В. (1977), "Асимптотика планшеровской меры симметрической группы и предельная форма для таблиц Юнга", Докл. Акад. АН СССР , 233 : 1024–1027..
- ^ Байк, Джинхо; Deift, Перси; Йоханссон, Курт (1999), «О распределении длины самой длинной возрастающей подпоследовательности случайных перестановок», Журнал Американского математического общества , 12 (4): 1119–1178, arXiv : math / 9810105 , doi : 10.1090 / S0894-0347-99-00307-0.
- ^ Сэмюэлс, Стивен. М .; Стил, Майкл Дж (1981), "Оптимальный Последовательный Выбор монотонной последовательности из случайной выборки" (PDF) , Анналы вероятности , 9 (6): 937-947, DOI : 10,1214 / АОП / 1176994265
- ^ Арлотто, Алессандро; Nguyen, Vinh V .; Стил, Дж. Майкл (2015), «Оптимальный онлайн-выбор монотонной подпоследовательности: центральная предельная теорема», Стохастические процессы и их приложения , 125 (9): 3596–3622, arXiv : 1408.6750 , doi : 10.1016 / j.spa .2015.03.009
- ^ Брюсс, Ф. Томас ; Дельбаен, Фредди (2001), «Оптимальные правила для последовательного выбора монотонных подпоследовательностей максимальной ожидаемой длины», Стохастические процессы и их приложения , 96 (2): 313–342.
- ^ Брюсс, Ф. Томас ; Дельбаен, Фредди (2004), «Центральная предельная теорема для оптимального процесса выбора для монотонных подпоследовательностей максимальной ожидаемой длины», Стохастические процессы и их приложения , 114 (2): 287–311, doi : 10.1016 / j.spa.2004.09 0,002.
Внешние ссылки [ править ]
- Самая длинная возрастающая подпоследовательность алгоритмиста
- Упрощенная самая длинная возрастающая подпоследовательность
- Нахождение числа самых длинных увеличенных подпоследовательностей
- Диета Полдо