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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Решение за время O(N2))
(Решение за время O(N2))
Строка 73: Строка 73:
  
 
==Решение за время O(N<sup>2</sup>)==
 
==Решение за время O(N<sup>2</sup>)==
Модифицируем предыдущее решение, добавив небольшую "хитрость". Теперь <tex> d[i][j] </tex> - это длина наибольшей общей возрастающей подпоследовательности префиксов <tex> a[1..i] </tex> и <tex> b[1..j] </tex>, причем элемент <tex> b[j] </tex> - последний представитель НОВП, а <tex> a[i] </tex> может не быть таковым. Вычислять <tex> d </tex> будем всё так же: по увеличению <tex> i </tex>, а при равенстве - по увеличению <tex> j </tex>. Тогда для очередного значения <tex> d[i][j] </tex> существу два варианта:
+
Модифицируем предыдущее решение, добавив небольшую "хитрость". Теперь <tex> d[i][j] </tex> - это длина наибольшей общей возрастающей подпоследовательности префиксов <tex> a[1..i] </tex> и <tex> b[1..j] </tex>, причем элемент <tex> b[j] </tex> - последний представитель НОВП, а <tex> a[i] </tex> может не быть таковым. Вычислять <tex> d </tex> будем всё так же: по увеличению <tex> i </tex>, а при равенстве - по увеличению <tex> j </tex>. Тогда для очередного значения <tex> d[i][j] </tex> есть два варианта:
 
*<tex> a[i] </tex> не входит в НОВП. Тогда <tex> d[i][j] = d[i-1][j] </tex>: значение динамики уже посчитано на префиксе <tex> a[1..i-1] </tex>.
 
*<tex> a[i] </tex> не входит в НОВП. Тогда <tex> d[i][j] = d[i-1][j] </tex>: значение динамики уже посчитано на префиксе <tex> a[1..i-1] </tex>.
*<tex> a[i] </tex> входит в НОВП. Тогда в префиксе <tex> b[1..j] </tex> нужно найти элемент <tex> b[k] = a[i] </tex>, для которого <tex> d[i-1][k] \rightarrow max </tex>. А раз мы считаем <tex> d </tex> сначала по увеличению <tex> i </tex>, будем считать <tex> a[i] </tex> ''фиксированным''. Чтобы не запускать цикл при каждом равенстве <tex> a[i] </tex> элементу <tex> b[k] </tex>, в дополнительной переменной <tex> best </tex> будем хранить "лучший" элемент (и его индекс <tex> best </tex>_<tex>ind </tex> в массиве <tex> b </tex>) такой, что этот элемент строго меньше <tex> a[i] </tex> и значение динамики для него максимально.
+
*<tex> a[i] </tex> входит в НОВП. Это значит, что <tex> a[i] = b[j]> </tex>, то есть для подсчёта <tex> d[i][j] </tex> нужно пробегать циклом по <tex> b </tex> в поисках элемента, меньшего <tex> b[j] </tex> с наибольшей <tex> d[i-1][k] </tex>. Но мы считаем <tex> d </tex> сначала по увеличению <tex> i </tex>, будем считать <tex> a[i] </tex> ''фиксированным''. Чтобы не запускать цикл при каждом равенстве <tex> a[i] </tex> элементу <tex> b[k] </tex>, в дополнительной переменной <tex> best </tex> будем хранить "лучший" элемент (и его индекс <tex> best </tex>_<tex>ind </tex> в массиве <tex> b </tex>) такой, что этот элемент строго меньше <tex> a[i] </tex> (а также меньше <tex> b[i] </tex>) и значение динамики для него максимально.
 +
Из этих двух вариантов выберем лучший.
  
 
  vector<int> '''LCIS'''(vector<int> a, vector<int> b)
 
  vector<int> '''LCIS'''(vector<int> a, vector<int> b)

Версия 21:23, 28 декабря 2013

Даны два массива: [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]\gt [/math], то есть для подсчёта [math] d[i][j] [/math] нужно пробегать циклом по [math] b [/math] в поисках элемента, меньшего [math] 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] best [/math]_[math]ind [/math] в массиве [math] b [/math]) такой, что этот элемент строго меньше [math] a[i] [/math] (а также меньше [math] b[i] [/math]) и значение динамики для него максимально.

Из этих двух вариантов выберем лучший.

vector<int> LCIS(vector<int> a, vector<int> b)
  d = int[n][m]   // динамика
  prev = int[n]   // массив предков 
  for i = 1...n
    best_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] = best_ind                            
       if a[i] > b[j] and d[i-1][j] > best // при следующем равенстве a[i] == b[j']
         best = d[i-1][j]                  // в best будет храниться "лучший" элемент:            
         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

См. также

Источники