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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

В інформатиці задача про найдовшу зростаючу підпослідовність полягає у пошуку підпослідовності даної послідовності, в якій елементи підпослідовності розташовані в порядку зростання, тобто, кожен наступний елемент підпослідовності більше попереднього, також, підпослідовність є якомога довшою. Шукана послідовність не обов'язково є неперервною або єдиною. Найбільш довгі зростаючи підпослідовності вивчаються у різних дисциплінах, пов'язаних з математикою, включаючи алгоритміку, теорію випадкових матриць, теорію представлень та фізику[1]. Задача про найдовшу зростаючу підпослідовність розв'язується за час O (n log n), де n — довжина вхідної послідовності[2].

Приклад

[ред. | ред. код]

У перших 16 членах двійкової послідовності ван дер Корпута[en]

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 — результат сортування[en] S . Однак для окремого випадку, коли вхідними даними є перестановка цілих чисел 1, 2, …, n, цей підхід можна зробити набагато ефективнішим, так, щоб він виконувався за час O(n log log n)[3].

Найбільша кліка в графі перестановки відповідає найдовшій спадній підпослідовності перестановки, яка визначає граф (припускаючи, що вихідна послідовність без перестановок сортується від найменшого значення до найбільшого). Подібним чином, максимальна незалежна множина[en] в графі перестановок відповідає найдовшій неспадній підпослідовності. Тому найефективніші алгоритми пошуку зростаючої підпослідовності можуть бути використані для ефективного вирішення задачі про кліку в графах перестановки[4].

У відповідності Робінзона – Шенстеда[en] між перестановками і таблицями Юнга довжина першого рядка таблиці, що відповідає перестановці, дорівнює довжині найбільшої зростаючої підпослідовності перестановки, а довжина першого стовпця дорівнює довжині найдовшої спадної підпослідовністі[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 елементів має розподіл, що наближається до розподілу Трейсі – Відома[en], розподілу найбільшого власного значення випадкової матриці в універсальному гауссовому ансамблі[9].

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

[ред. | ред. код]

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

Застосування

[ред. | ред. код]
  • Частина системи MUMmer[en] (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, doi:10.4153/CJM-1961-015-3, MR 0121305
  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, архів оригіналу за 19 лютого 2019, процитовано 21 липня 2021
  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 (PDF), IMA Volumes in Mathematics and its Applications, т. 72, Springer-Verlag, с. 111—131, архів оригіналу (PDF) за 11 червня 2019, процитовано 21 липня 2021
  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 (PDF), Annals of Probability, 9 (6): 937—947, doi:10.1214/aop/1176994265{{citation}}: Обслуговування CS1: Сторінки з параметром url-status, але без параметра archive-url (посилання)
  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

Посилання

[ред. | ред. код]
Отримано з https://uk.wikipedia.org/w/index.php?title=Задача_про_найдовшу_зростаючу_підпослідовність&oldid=42320052