Теоретический материал: наибольшая возрастающая подпоследовательность

Сайт: Информатикс
Курс: Динамическое программирование
Книга: Теоретический материал: наибольшая возрастающая подпоследовательность
Напечатано:: Гость
Дата: Суббота, 4 Декабрь 2021, 21:02

Наибольшая возрастающая подпоследовательность (НВП, Longest Increasing Subsequence, LIS)

Условие

Дана последовательность a1, …, an. Требуется найти ее возрастающую подпоследовательность наибольшей длины.

Решение

Первый способ

Сделаем копию данной последовательности и отсортируем ее по возрастанию. Тогда НВП будет также НВП для отсортированной последовательности. Поэтому достаточно найти наибольшую общую подпоследовательность исходной и отсортированной последовательности.

Обратите внимание: на самом деле таким способом мы найдем не возрастающую, а неубывающую подпоследовательность. Чтобы найти возрастающую подпоследовательность, нужно сделать еще один шаг (подумайте, какой!).

Сложность этого алгоритма – O(n2).

Второй способ

Попробуем воспользоваться методом динамического программирования. Пусть мы знаем НВП для последовательности a1, …, ak. Можем ли мы найти НВП для последовательности a1, …, ak+1? Кажется, что это легко сделать: если ak+1 больше, чем последний член ранее найденной НВП, то ak+1 нужно добавить в НВП, в противном случае нужно оставить НВП неизменной. К сожалению, такое решение оказывается неверным. Рассмотрим такой пример: 1 2 3 6 4 5. Для первых пяти членов этой последовательности длина НВП равна 4, но есть две различных НВП: 1 2 3 6 и 1 2 3 4. Пусть мы выбрали первую из них. Тогда на следующем шаге мы не сможем дополнить ее числом 5 и получим более короткую НВП (1 2 3 6) для всей последовательности, чем должны был получить (1 2 3 4 5).

Модифицируем предложенный алгоритм. Будем теперь запоминать не произвольную НВП, а ту, которая заканчивается на наименьшую возможную цифру. К сожалению, и этот способ не приведет нас к успеху. Рассмотрим такой пример: 1 4 2 3. Для последовательности из первых двух символов НВП будет иметь длину 2 (1 4). Но при добавлении символов длина НВП не увеличится, поскольку все оставшиеся числа меньше четырех.

Для решения задачи нам потребуется более сложная система подзадач. Пусть для последовательности a1, a2, …, ak мы знаем возрастающие последовательности длины 1, 2, 3, ... Причем среди всех возрастающих последовательностей данной длины мы будем хранить ту, которая оканчивается на меньшее число. Тогда для последовательности a1, a2, …, ak+1 мы сможем построить аналогичный набор последовательностей.

Опишем эту процедуру подробнее. Пусть LIS(ks) – последний элемент возрастающей подпоследовательности длины s последовательности a1, a2, …, ak.

Тогда следующий фрагмент программы полностью описывает динамические вычисления:

For k= 0 to n do
    for s= 1 to n do
          LIS(k, s) = plus infinity
For k= 0 to n do
     LIS(k, 0) = minus infinity
For k= 1 to n do
     for s= 1 to n do
          if ( LIS(k-1, s-1) < x(k) < LIS(k-1, s) 
                 then LIS(k,s)=x(k) 
                 else LIS(k,s)=LIS(k-1,s)

Третий способ

Мы будем постепенно строить возрастающие цепочки и в каждый момент времени для каждого элемента ai хранить длину самой длинной построенной цепочки, заканчивающейся этим элементом.

Идею динамики лучше всего поясняет следующий код:

for i := 1 to n-1 do
  for j := i+1 to n do
    if a[j] > a[i] then
      if length[i] + 1 > length[j] then begin
        length[j] = length[i] + 1;
        predecessor[j] = i; //
предшественник a[j] в цепочке

      end;

Изначально length[i]=1 для всех i, predecessor[i]=0.

Продемонстрируем работу алгоритма для последовательности 1,6,2,3,5.

До начала выполнения циклов:
 
length: [1,1,1,1,1]
 
predecessor: [0,0,0,0,0]

После выполнения цикла для i=1:
  length: [1,2,2,2,2], так как 6,2,3,5 > 1
 
predecessor: [0,1,1,1,1]

После выполнения цикла для i=2:
  length: [1,2,2,2,2] – без изменений, так как 2,3,5 < 6
 
predecessor: [0,1,1,1,1]

После выполнения цикла для i=3:
  length: [1,2,2,3,3], так как 3,5 > 2
 
predecessor: [0,1,1,3,3]

После выполнения цикла для i=4:
 
length: [1,2,2,3,4], так как 5 > 3
 
predecessor: [0,1,1,3,4]

Таким образом, длина НВП равна 4, и всякая НВП заканчивается элементом 5, поскольку length[5]=4.

Используя массив predecessor, легко восстановить всю подпоследовательность:

Predecessor[5]=4, predecessor[4]=3, predecessor[3]=1, predecessor[1]=0.

Таким образом, НВП состоит из 1-го, 3-го, 4-го и 5-го элементов исходной последовательности: 1, 2, 3, 5.

Приведенный алгоритм имеет сложность O(n2).

Четвертый способ

Будем поочередно обрабатывать члены исходной последовательности. Пусть после обработки k-го элемента нам известно, что возрастающая подпоследовательность длины 1 может оканчиваться числом e[1], ВП длины 2 может оканчиваться числом e[2] и т.д., причем указанные числа e[i] – наименьшие возможные. Заметим, что е[1] < e[2] < e[3] <… Рассмотрим теперь число ak+1. Найдем такое i, что e[i-1] ≤ ak+1 e[i] (если изначально положить e[0] = - ∞, а все остальные члены массива e равными +∞, то такое всегда найдется). Положим e[i]:= ak+1, а остальные элементы массива e[i] оставим без изменений.

Заметим, что сложность поиска в упорядоченном массиве есть O(log m), где m – длина НВП, поэтому сложность приведенного алгоритма – О(n log m).