Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску

В информатике самая длинная проблема возрастающей подпоследовательности состоит в том, чтобы найти подпоследовательность заданной последовательности, в которой элементы подпоследовательности расположены в отсортированном порядке, от самого низкого до самого высокого, и в котором подпоследовательность является максимально длинной. Эта подпоследовательность не обязательно является непрерывной или уникальной. Самые длинные возрастающие подпоследовательности изучаются в контексте различных дисциплин , связанных с математикой , в том числе алгоритмики , теории случайных матриц , теории представлений и физики . [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]

Заявление [ править ]


См. Также [ править ]

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

Ссылки [ править ]

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

Внешние ссылки [ править ]

  • Самая длинная возрастающая подпоследовательность алгоритмиста
  • Упрощенная самая длинная возрастающая подпоследовательность
  • Нахождение числа самых длинных увеличенных подпоследовательностей
  • Диета Полдо