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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 7: Строка 7:
 
==== Пример алгоритма, работающего за время <tex> O(n^2) </tex> ====
 
==== Пример алгоритма, работающего за время <tex> O(n^2) </tex> ====
 
Строим таблицу <tex> a[1 \dots n]. Каждый её элемент <tex> a[i] </tex> - длина наибольшей возрастающей подпоследовательности, оканчивающейся точно в позиции <tex> i </tex>. Если мы построим эту таблицу, то ответ к задаче - наибольшее число из этой таблицы.
 
Строим таблицу <tex> a[1 \dots n]. Каждый её элемент <tex> a[i] </tex> - длина наибольшей возрастающей подпоследовательности, оканчивающейся точно в позиции <tex> i </tex>. Если мы построим эту таблицу, то ответ к задаче - наибольшее число из этой таблицы.
Само построение тоже элементарно: ,<tex> a[i] = \max{i-1}_{j = 1} {(a[j] + 1)} </tex>, для которых <tex> x[j] < x[i] </tex>. База динамики <tex> a[1] = 1 </tex>.
+
Само построение тоже элементарно: ,<tex> a[i] = \max{(a[j] + 1)} </tex>,для всех <tex> j = 1\dotsi-1</tex>, для которых <tex> x[j] < x[i] </tex>. База динамики <tex> a[1] = 1 </tex>.
 
Если мы хотим восстановить саму подпоследовательность, то заведем массив предыдущих величин pred такой, что pred[i] - предпоследний элемент в НВП, оканчивающейся в элементе с номером <tex> i </tex>. Его значение будет изменяться вместе с изменением соответствующего i-ого элемента матрицы <tex>a</tex>.
 
Если мы хотим восстановить саму подпоследовательность, то заведем массив предыдущих величин pred такой, что pred[i] - предпоследний элемент в НВП, оканчивающейся в элементе с номером <tex> i </tex>. Его значение будет изменяться вместе с изменением соответствующего i-ого элемента матрицы <tex>a</tex>.
 
<code>
 
<code>
Строка 19: Строка 19:
 
       a[i] = a[j]+1;
 
       a[i] = a[j]+1;
 
       pred[i] = j;  
 
       pred[i] = j;  
  lis = <tex>\max{n}_{i = 1} {a[i]}</tex>
+
  lis = <tex>\max{a[i]}, i = 1\dotsn</tex>,
 
</code>
 
</code>
 
Для вывода самой подпоследовательности достаточной пройти по массиву pred, начиная с номера того элемента, на котором мы зафиксировали наш ответ lis, и спускаясь по его предыдущим элементам, пока не достигнем -1 в предке очередного элемента.
 
Для вывода самой подпоследовательности достаточной пройти по массиву pred, начиная с номера того элемента, на котором мы зафиксировали наш ответ lis, и спускаясь по его предыдущим элементам, пока не достигнем -1 в предке очередного элемента.
 +
<tex> (max^n)_1 </tex>

Версия 10:18, 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 = [math]\max{a[i]}, i = 1\dotsn[/math], 

Для вывода самой подпоследовательности достаточной пройти по массиву pred, начиная с номера того элемента, на котором мы зафиксировали наш ответ lis, и спускаясь по его предыдущим элементам, пока не достигнем -1 в предке очередного элемента. [math] (max^n)_1 [/math]