Задача про найдовшу зростаючу підпослідовність

В інформатиці задача про найдовшу зростаючу підпослідовність полягає у пошуку підпослідовності даної послідовності, в якій елементи підпослідовності розташовані в порядку зростання, тобто, кожен наступний елемент підпослідовності більше попереднього, також, підпослідовність є якомога довшою. Шукана послідовність не обов'язково є неперервною або єдиною. Найбільш довгі зростаючи підпослідовності вивчаються у різних дисциплінах, пов'язаних з математикою, включаючи алгоритміку, теорію випадкових матриць, теорію представлень та фізику[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, рівність можлива тільки коли входовий масив до індексу i є зростаючим). Зверніть увагу, що j ≤ (i + 1), оскільки j ≥ 1 є довжиною зростаючої підпослідовності, а k ≥ 0 — це індекс в масиві X її останнього елементу.
P[k] — зберігає індекс в масиві X, який йде перед останнім елементом 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 = масив довжини N
M = масив довжини N + 1

L = 0
L = 0
for i in range 0 to N-1:
    // Двійковий пошук найбільшого додатного j ≤ L
    // такого, що X[M[j]] < X[i]
    lo = 1
    hi = L
    while lo ≤ hi:
        mid = ceil((lo+hi)/2)
        if X[M[mid]] < X[i]:
            lo = mid+1
        else:
            hi = mid-1

    // Після пошуку, lo на 1 більше, ніж
    // довжина найдовшого префіксу X[i]
    newL = lo

    // Попередник X[i] є останнім індексом 
    // підпослідовності довжини newL-1
    // 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:
        // Якщо ми знайшли підпослідовність довшу
        // за будь-яку зі знайдених, то оновимо L
        L = newL
// Реконструюємо найдовшу зростаючу підпослідовність
S = масив довжини 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). Fredman, (1975) обговорює варіант цього алгоритму, який він приписує Дональду Кнуту. У варіанті, який він досліджував, алгоритм перевіряє, чи кожне значення X[i] може бути використано для продовження поточної найдовшої послідовності, що збільшується, за сталий час, перед виконанням двійкового пошуку. За допомогою цієї модифікації алгоритм використовує щонайбільше n log2 n − n log2log2 n + O(n) порівнянь в найгіршому випадку, що є оптимальним для алгоритму, заснованого на порівнянні, з точністю до сталого коефіцієнта в O(n)[5].

Межі довжини

Відповідно до теореми Ердеша — Секереша, будь-яка послідовність n2+1 різних цілих чисел має зростаючу або спадну підпослідовність довжини n + 1[6][7]. Для входів, в яких кожна перестановка очікується з однаковою ймовірністю, очікувана довжина найдовшої зростаючої підпослідовності становить приблизно 2√n[8]. Коли n наближається до нескінченності, тоді граничне значення довжини найбільшої зростаючої підпослідовності випадково переставленої послідовності з n елементів має розподіл, що наближається до розподілу Трейсі – Відома, розподілу найбільшого власного значення випадкової матриці в універсальному гауссовому ансамблі[9].

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

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

Застосування
  • Частина системи MUMmer (Maximum Unique Match finder) для вирівнювання цілих геномів.
  • Використовується в системах контролю версій, таких як Git тощо.
  • Використовується в Patience Diff, алгоритмі різниці (обчислює та відображає різницю між вмістом файлів), який використовується у «Bazaar» (Bazaar — це система контролю версій, яка допомагає вам відстежувати історію проекту з часом та легко співпрацювати з іншими)

Див. також
  • Терпеливе сортування, ефективний метод визначення довжини найбільшої зростаючої підпослідовності
  • Плактичний моноїд, алгебраїчна система, що визначається перетвореннями, які зберігають довжину найдовшої зростаючої підпослідовності
  • Анатолій Вершик, російський математик, який вивчав застосування теорії груп до найдовших зростаючих підпослідовностей
  • Найдовша спільна підпослідовність
  • Найдовша підпослідовність з чергуванням

Примітки
  1. Aldous, David; Diaconis, Persi (1999). Longest increasing subsequences: from patience sorting to the Baik–Deift–Johansson theorem. Bulletin of the American Mathematical Society 36 (04): 413–432. doi:10.1090/S0273-0979-99-00796-X.
  2. Schensted, C. (1961). Longest increasing and decreasing subsequences. Canadian Journal of Mathematics 13: 179–191. MR 0121305. doi:10.4153/CJM-1961-015-3.
  3. Hunt, J.; Szymanski, T. (1977). A fast algorithm for computing longest common subsequences. Communications of the ACM 20 (5): 350–353. doi:10.1145/359581.359603.
  4. Golumbic, M. C. (1980). Algorithmic Graph Theory and Perfect Graphs. Computer Science and Applied Mathematics. Academic Press. с. 159.
  5. Fredman, Michael L. (1975). On computing the length of longest increasing subsequences. Discrete Mathematics 11 (1): 29–35. doi:10.1016/0012-365X(75)90103-X.
  6. Erdős, Paul; Szekeres, George (1935). A combinatorial problem in geometry. Compositio Mathematica 2: 463–470.
  7. Steele, J. Michael (1995). Variations on the monotone subsequence theme of Erdős and Szekeres. У Aldous, David; Diaconis, Persi; Spencer, Joel та ін. Discrete Probability and Algorithms. IMA Volumes in Mathematics and its Applications 72. Springer-Verlag. с. 111–131.
  8. Vershik, A. M.; Kerov, C. V. (1977). Asymptotics of the Plancheral measure of the symmetric group and a limiting form for Young tableaux. Dokl. Akad. Nauk SSSR 233: 1024–1027.
  9. Baik, Jinho; Deift, Percy; Johansson, Kurt (1999). On the distribution of the length of the longest increasing subsequence of random permutations. Journal of the American Mathematical Society 12 (4): 1119–1178. arXiv:math/9810105. doi:10.1090/S0894-0347-99-00307-0..
  10. Samuels, Stephen. M.; Steele, J. Michael (1981). Optimal Sequential Selection of a Monotone Sequence From a Random Sample. Annals of Probability 9 (6): 937–947. doi:10.1214/aop/1176994265.
  11. Arlotto, Alessandro; Nguyen, Vinh V.; Steele, J. Michael (2015). Optimal online selection of a monotone subsequence: a central limit theorem. Stochastic Processes and their Applications 125 (9): 3596–3622. arXiv:1408.6750. doi:10.1016/j.spa.2015.03.009.
  12. Bruss, F. Thomas; Delbaen, Freddy (2001). Optimal rules for the sequential selection of monotone subsequences of maximum expected length. Stochastic Processes and their Applications 96 (2): 313–342.
  13. Bruss, F. Thomas; Delbaen, Freddy (2004). A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length. Stochastic Processes and their Applications 114 (2): 287–311. doi:10.1016/j.spa.2004.09.002.

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.