Задача про найдовшу зростаючу підпослідовністьВ інформатиці задача про найдовшу зростаючу підпослідовність полягає у пошуку підпослідовності даної послідовності, в якій елементи підпослідовності розташовані в порядку зростання, тобто, кожен наступний елемент підпослідовності більше попереднього, також, підпослідовність є якомога довшою. Шукана послідовність не обов'язково є неперервною або єдиною. Найбільш довгі зростаючи підпослідовності вивчаються у різних дисциплінах, пов'язаних з математикою, включаючи алгоритміку, теорію випадкових матриць, теорію представлень та фізику[1]. Задача про найдовшу зростаючу підпослідовність розв'язується за час O (n log n), де n — довжина вхідної послідовності[2]. ПрикладУ перших 16 членах двійкової послідовності ван дер Корпута[en]
найдовша зростаюча підпослідовність
Ця підпослідовність має довжину шість, що є максимальним значенням, бо вхідна послідовність не має зростаючих підпослідовностей із семи елементів. Найдовша зростаюча підпослідовність у цьому прикладі має декілька розв'язків. Наприклад,
Це різні зростаючі підпослідовності однакової довжини в одній і тій же вхідній послідовності. Зв'язок з іншими алгоритмічними задачамиЗадача найдовшої зростаючого підпослідовності тісно пов'язана з найдовшою спільною підпослідовністю, яка розв'язується за допомогою динамічного програмування за квадратичний час: найдовша зростаюча підпослідовність послідовності 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], алгоритм буде зберігати значення у двох масивах:
Крім того, алгоритм зберігає змінну 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]. Застосування
Див. також
Примітки
Посилання
|
Portal di Ensiklopedia Dunia
