Задача о наибольшей возрастающей подпоследовательности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 24: Строка 24:
  
 
==== Пример алгоритма, работающего за время <tex> O(n*\log n) </tex> ====
 
==== Пример алгоритма, работающего за время <tex> O(n*\log n) </tex> ====
Для строки ''x'' будем по-прежнему хранить массивы <tex>a</tex> и <tex>pred</tex> длины n. Только теперь <tex> a[i] <tex> содержит наименьший по величине элемент, на который может оканчиваться  возрастающая подпоследовательность длины <tex>i</tex>, среди всех <tex>x[j]</tex>, где <tex>1 \leqslant j \leqslant i-1 </tex>, если мы на шаге <tex>i</tex>. pred[i] хранит индекс предшествующего символа для наибольшей возрастающей подпоследовательности, оканчивающейся в i-й позиции. Заметим, что <tex> a[1] < a[2] < a[3] < \dots < a[n] </tex>. Пусть мы находимся на i-ом шаге, тогда нам надо найти такой номер k <tex> a[k-1] < x[i] < a[k] </tex> (если положить при начальной реализации<tex> a[1] = -\inf a[2] = a[3] = \dots = a[n] = \inf </tex>, то такое k всегда найдется), причем надо наибольшее k из возможных. После этого полагаем <tex> a[k] = x[i] </tex>. В силу упорядоченности массива a, мы можем выполнить поиск k бинарным поиском, а име нно, функцией upper_bound(begin, end, val), максимальный возвращающий номер элемента, который меньше (или не больше, зависит от постановки задачи), чем val.
+
Для строки ''x'' будем по-прежнему хранить массивы <tex>a</tex> и <tex>pred</tex> длины n. Только теперь <tex> a[i] <tex> содержит наименьший по величине элемент, на который может оканчиваться  возрастающая подпоследовательность длины <tex>i</tex>, среди всех <tex>x[j]</tex>, где <tex>1 \leqslant j \leqslant i-1 </tex>, если мы на шаге <tex>i</tex>. pred[i] хранит индекс предшествующего символа для наибольшей возрастающей подпоследовательности, оканчивающейся в i-й позиции. Заметим, что <tex> a[1] < a[2] < a[3] < \dots < a[n] </tex>. Пусть мы находимся на i-ом шаге, тогда нам надо найти такой номер k <tex> a[k] <= x[i] < a[k+1] </tex> (если положить при начальной реализации<tex> a[1] = -\inf a[2] = a[3] = \dots = a[n] = \inf </tex>, то такое k всегда найдется), причем надо наибольшее k из возможных. После этого полагаем <tex> a[k] = x[i] </tex>. В силу упорядоченности массива a, мы можем выполнить поиск k бинарным поиском, а име нно, функцией upper_bound(begin, end, val), максимальный возвращающий номер элемента, который меньше (или не больше, зависит от постановки задачи), чем val.
  
 
<code>
 
<code>
lis = index = 0
 
 
  a[1] = -inf
 
  a[1] = -inf
 
  a[2..n] = inf
 
  a[2..n] = inf
  for i = 1 to n
+
  For i = 1 to n
     j = upper_bound(бинарный поиск наибольшего индекса j ≤ L, удовлетворяющего x[a[j]] < x[i]
+
     j = upper_bound(1, n, x[i]) // бинарный поиск наибольшего индекса среди всех j < i, удовлетворяющих x[a[j]] < x[i]
     P[i] = M[j]
+
     pred[i] = a[j]
     if j == L or X[i] < X[M[j+1]] // нашли более оптимальную подпоследовательность
+
     If j = i or x[i] < X[M[j+1]] // нашли более оптимальную подпоследовательность
 
       M[j+1] = i
 
       M[j+1] = i
 
       L = max{L, j+1}
 
       L = max{L, j+1}
 +
 +
for (int i=0; i<n; i++)
 +
{
 +
unsigned j = upper_bound (d.begin(), d.end(), a[i]) - d.begin() - 1;
 +
if (d[j] < a[i] && a[i] < d[j+1])
 +
d[j+1] = a[i];
 +
}
 
</code>
 
</code>

Версия 11:01, 27 ноября 2010

Определение:
Наибольшая возрастающая подпоследовательность (НВП) (англ. Longest increasing subsequence - LIS) строки [math] x [/math] длины [math] n [/math] - это последовательность [math] x[i_1] \lt x[i_2] \lt \dots \lt x[i_k] [/math] символов строки [math] x [/math] таких, что [math] i_1 \lt i_2 \lt \dots \lt i_k, 1 \le i_j \le n [/math] и [math] k [/math] - наибольшее из возможных.

Задача заключается в том, чтобы отыскать это наибольшее [math] k [/math] и саму подпоследовательность. Известно несколько алгоритмов решения этой задачи.

Пример алгоритма, работающего за время [math] O(n^2) [/math]

Строим таблицу [math] a[1 \dots n]. Каждый её элемент \lt tex\gt a[i] [/math] - длина наибольшей возрастающей подпоследовательности, оканчивающейся точно в позиции [math] i [/math]. Если мы построим эту таблицу, то ответ к задаче - наибольшее число из этой таблицы. Само построение тоже элементарно: ,[math] a[i] = \max{(a[j] + 1)} [/math],для всех [math] j = 1\dotsi-1[/math], для которых [math] x[j] \lt x[i] [/math]. База динамики [math] a[1] = 1 [/math]. Если мы хотим восстановить саму подпоследовательность, то заведем массив предыдущих величин pred такой, что pred[i] - предпоследний элемент в НВП, оканчивающейся в элементе с номером [math] i [/math]. Его значение будет изменяться вместе с изменением соответствующего i-ого элемента матрицы [math]a[/math].

lis = 0           // длина НВП
a = {0..0}        // заполняем нулями
pred = {-1..-1}   // -1 - признак отсутствия предпоследнего элемента, что указывает на то, что данный элемент является первым в подпоследовательности
a[1] = 1         
For i = 2 to n
  For j = 1 to i - 1
    If (x[i] > x[j]) and (a[j] + 1 > a[i]) // нашли более оптимальную подпоследовательность
      a[i] = a[j]+1
      pred[i] = j
    lis = max(lis, a[i])

Для вывода самой подпоследовательности достаточной пройти по массиву pred, начиная с номера того элемента, на котором мы зафиксировали наш ответ lis, и спускаясь по его предыдущим элементам, пока не достигнем -1 в предке очередного элемента.

Пример алгоритма, работающего за время [math] O(n*\log n) [/math]

Для строки x будем по-прежнему хранить массивы [math]a[/math] и [math]pred[/math] длины n. Только теперь [math] a[i] \lt tex\gt содержит наименьший по величине элемент, на который может оканчиваться возрастающая подпоследовательность длины \lt tex\gt i[/math], среди всех [math]x[j][/math], где [math]1 \leqslant j \leqslant i-1 [/math], если мы на шаге [math]i[/math]. pred[i] хранит индекс предшествующего символа для наибольшей возрастающей подпоследовательности, оканчивающейся в i-й позиции. Заметим, что [math] a[1] \lt a[2] \lt a[3] \lt \dots \lt a[n] [/math]. Пусть мы находимся на i-ом шаге, тогда нам надо найти такой номер k [math] a[k] \lt = x[i] \lt a[k+1] [/math] (если положить при начальной реализации[math] a[1] = -\inf a[2] = a[3] = \dots = a[n] = \inf [/math], то такое k всегда найдется), причем надо наибольшее k из возможных. После этого полагаем [math] a[k] = x[i] [/math]. В силу упорядоченности массива a, мы можем выполнить поиск k бинарным поиском, а име нно, функцией upper_bound(begin, end, val), максимальный возвращающий номер элемента, который меньше (или не больше, зависит от постановки задачи), чем val.

a[1] = -inf
a[2..n] = inf
For i = 1 to n
   j = upper_bound(1, n, x[i]) // бинарный поиск наибольшего индекса среди всех j < i, удовлетворяющих x[a[j]] < x[i]
   pred[i] = a[j]
   If j = i or x[i] < X[M[j+1]] // нашли более оптимальную подпоследовательность
      M[j+1] = i
      L = max{L, j+1}

for (int i=0; i<n; i++) { unsigned j = upper_bound (d.begin(), d.end(), a[i]) - d.begin() - 1; if (d[j] < a[i] && a[i] < d[j+1]) d[j+1] = a[i]; }