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

Материал из Викиконспекты
Версия от 14:03, 29 декабря 2013; 188.227.78.144 (обсуждение) (→‎Решение за время O(N2))
Перейти к: навигация, поиск

Даны два массива: [math] a[1..n] [/math] и [math] b[1..m] [/math]. Требуется найти их наибольшую общую возрастающую подпоследовательность (НОВП).

Определение:
Наибольшая общая возрастающая подпоследовательность (НОВП) (англ. longest common increasing subsequence - LCIS) массива [math] A [/math] длины [math] n [/math] и массива [math] B [/math] длины [math] m [/math] — это последовательность [math] X = \left \langle x_1, x_2, ..., x_k \right \rangle [/math] такая, что [math] x_1 \lt x_2 \lt \dots \lt x_k [/math], [math] X [/math] является подпоследовательностью [math] A [/math] и [math] B [/math].


Решение за время O(N4)

Построим следующую динамику: [math] d[i][j] [/math] - это длина наибольшей возрастающей подпоследовательности массивов [math] a [/math] и [math] b [/math], последний элемент которой [math] a[i] [/math] и [math] b[j] (a[i] = b[j]) [/math]. Будем заполнять [math] d[i][j] [/math] сначала по увеличению [math] i [/math], а при равенстве по увеличению [math] j [/math]. Ответом на задачу будет максимум из всех элементов [math] d[i][j] [/math] (где [math] i = 1...n [/math], [math] j = 1...m. [/math])

Заполнять [math] d [/math] будем следующим образом: на очередном шаге сравниваем элементы [math] a[i] [/math] и [math] b[j] [/math]:

  • Если [math] a[i] \neq b[j] [/math], то [math] d[i][j] = 0 [/math] (так как нет НОВП, оканчивающейся в разных элементах).
  • Если [math] a[i] = b[j] [/math], то эти элементы могут быть частью НОВП. Переберём, какие элементы стояли перед ними в массивах [math] a [/math] и [math] b [/math]. Заметим, что предыдущие значения [math] d [/math] уже известны, тогда очередное значение [math] d[i][j] = max(d[k][l]) + 1, [/math] для всех [math] k = 1..i-1 [/math] и [math] l = 1..j-1, [/math] при условии, что [math] a[k] = b[l]. [/math]

Для восстановления подпоследовательности можно хранить массив предков [math] prev[1..n] [/math] массива [math] a: prev[i] [/math] - индекс предыдущего элемента НОВП, которая оканчивается в [math] a[i] [/math]. 

vector<int> LCIS(vector<int> a, vector<int> b)
  d = int[n][m] // динамика
  prev = int[n] // массив предков
  for i = 1...n 
    for j = 1...m
      if a[i] == b[j]
        d[i][j] = 1 // НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j]
          for k = 1...i-1
            for l = 1...j-1
              if a[k] == b[l] and a[k] < a[i] and d[i][j] < d[k][l] + 1
                d[i][j] = d[k][l] + 1
                prev[i] = k
  // восстановление
  b_i = 1          // ищем лучшую пару (b_i, b_j)
  b_j = 1          // d[b_i][b_j] [math] \rightarrow [/math] max
  for i = 1...n
    for j = 1...m 
      if d[b_i][b_j] < d[i][j]
        b_i = i
        b_j = j
  vector<int> answer
  pos = b_i        // проходим по массиву a, выписывая элементы НОВП
  while pos != 0
    answer.push(a[pos])
    pos = prev[pos]
  return answer

Решение за время O(N3)

Улучшим предыдущее решение. Пусть теперь [math] d[i][j] [/math] - динамика, в которой элемент [math] a[i] [/math] по-прежнему последний представитель НОВП массива [math] a [/math], а [math] b[j] [/math] может не быть быть последним представителем массива [math] b [/math]:

  • Если [math] a[i] \neq b[j] [/math], будем "протаскивать" последнее удачное сравнение в динамике: [math] d[i][j] = d[i][j-1] [/math] (понять это можно так: [math] a[i] \neq b[j] [/math] , поэтому [math] b[j] [/math] не последний представитель НОВП из массива [math] b [/math], а значит предыдущий элемент НОВП находится в префиксе [math] b[1..j-1] [/math], но [math] d[i][j-1] [/math] уже посчитан).
  • Если [math] a[i] = b[j] [/math], то одним дополнительным циклом пробежим по [math] a [/math] и найдём предыдущий элемент НОВП, оканчивающейся в [math] a[i] [/math] (он меньше [math] a[i] [/math]). Из подходящих элементов выберем тот, для которого [math] d[k][j] [/math] - максимальна.

[math] d[i][j] = max(d[k][j]) + 1, [/math] для всех [math] k = 1..i-1, a[k] \lt a[i]. [/math] 

vector<int> LCIS(vector<int> a, vector<int> b)
  d = int[n][m] // динамика
  prev = int[n] // массив предков
  for i = 1...n 
    for j = 1...m
      if a[i] == b[j]
        d[i][j] = 1   // НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j]
          for k = 1...i-1
            if a[k] < a[i] and d[i][j] < d[k][j] + 1
              d[i][j] = d[k][j] + 1
              prev[i] = k
      else
        d[i][j] = d[i][j-1] 
  // восстановление
  b_i = 1         // ищем лучший элемент d[b_i][m] [math] \rightarrow [/math] max
  for i = 1...n
    if d[b_i][m] < d[i][m]
      b_i = i
  vector<int> answer
  pos = b_i        // проходим по массиву a, выписывая элементы НОВП
  while pos != 0
    answer.push(a[pos])
    pos = prev[pos]
  return answer

Решение за время O(N2)

Модифицируем предыдущее решение, добавив небольшую "хитрость". Теперь [math] d[i][j] [/math] - это длина наибольшей общей возрастающей подпоследовательности префиксов [math] a[1..i] [/math] и [math] b[1..j] [/math], причем элемент [math] b[j] [/math] - последний представитель НОВП, а [math] a[i] [/math] может не быть таковым. Вычислять [math] d [/math] будем всё так же: сначала по увеличению [math] i [/math], а при равенстве - по увеличению [math] j [/math]. Тогда для очередного значения [math] d[i][j] [/math] есть два варианта:

  • [math] a[i] [/math] не входит в НОВП. Тогда [math] d[i][j] = d[i-1][j] [/math]: значение динамики уже посчитано на префиксе [math] a[1..i-1] [/math].
  • [math] a[i] [/math] входит в НОВП. Это значит, что [math] a[i] = b[j] [/math], то есть для подсчёта [math] d[i][j] [/math] нужно пробегать циклом по [math] b [/math] в поисках элемента [math] b[k] \lt b[j] [/math] с наибольшим значением [math] d[i-1][k] [/math]. Но мы считаем [math] d [/math] сначала по увеличению [math] i [/math], поэтому будем считать [math] a[i] [/math] фиксированным. Чтобы не запускать цикл при каждом равенстве [math] a[i] [/math] элементу [math] b[k] [/math], в дополнительной переменной [math] best [/math] будем хранить "лучший" элемент (и его индекс [math] ind [/math] в массиве [math] b [/math]) такой, что этот элемент строго меньше [math] a[i] [/math] (а также меньше [math] b[i] [/math]) и значение динамики для него максимально: [math] b[ind] \lt a[i] = b[i] [/math] и [math] best = d[i-1][ind] \rightarrow [/math] max.
vector<int> LCIS(vector<int> a, vector<int> b)
  d = int[n][m]   // динамика
  prev = int[n]   // массив предков 
  for i = 1...n
    ind = 0       // позиция "лучшего" элемента в массиве b
    best = 0      // значение динамики для "лучшего" элемента
    for j = 1...m	
      d[i][j] = d[i-1][j]                          // НОВП на a[1..i-1] и b[1..j] (без элемента a[i])
        if a[i] == b[j] and d[i-1][j] < best + 1   // используем a[i]-й элемент для увеличения НОВП
          d[i][j] = best + 1                         
          p[j] = ind                            
       if a[i] > b[j] and d[i-1][j] > best // при следующем равенстве a[i] == b[j']
         best = d[i-1][j]                  // в best будет храниться "лучший" элемент:            
         ind = j                      // b[best_ind] < b[j'] и d[i][best_ind] - максимальна
  // восстановление (по массиву b)
  b_j = 1 // ищем лучший элемент d[n][b_j][math] \rightarrow [/math] max
  for j = 1...m
    if d[n][b_j] < d[n][j]
      b_j = j
  vector<int> answer
  pos = b_j //проходим по массиву b, выписывая элементы НОВП
  while pos != 0
    answer.push(b[pos])
    pos = prev[pos]
  return answer

См. также

Источники

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Задача_о_наибольшей_общей_возрастающей_последовательности&oldid=34829»