algorithm
Самая длинная общая подпоследовательность
Поиск…
Наибольшая общая подпоследовательность Объяснение
Одна из наиболее важных реализаций динамического программирования - поиск самой длинной общей подпоследовательности . Сначала определим некоторые основные термины.
подпоследовательности:
Подпоследовательность представляет собой последовательность, которая может быть получена из другой последовательности путем удаления некоторых элементов без изменения порядка остальных элементов. Допустим, у нас есть строка ABC . Если мы стираем нуль или один или несколько символов из этой строки, мы получаем подпоследовательность этой строки. Таким образом, подпоследовательности строки ABC будут { "A" , "B" , "C" , "AB" , "AC" , "BC" , "ABC" , "" }. Даже если мы удалим все символы, пустая строка также будет подпоследовательностью. Чтобы узнать подпоследовательность, для каждого символа в строке мы имеем два варианта: либо мы берем символ, либо нет. Поэтому, если длина строки равна n , существует 2 n подпоследовательностей этой строки.
Самая длинная общая подпоследовательность:
Как следует из названия, из всех общих подпоследовательностей между двумя строками самая длинная общая подпоследовательность (LCS) - это та, которая имеет максимальную длину. Например: общие подпоследовательности между «HELLOM» и «HMLD» - это «H» , «HL» , «HM» и т. Д. Здесь «HLL» является самой длинной общей подпоследовательностью, длина которой 3.
Метод грубой силы:
Мы можем сгенерировать все подпоследовательности двух строк с использованием обратного отсчета . Затем мы можем сравнить их, чтобы выяснить общие подпоследовательности. После того, как нам понадобится узнать ту, которая имеет максимальную длину. Мы уже видели, что существует 2 n подпоследовательностей строки длины n . Потребуются годы, чтобы решить проблему, если наши русские кресты 20-25 .
Метод динамического программирования:
Давайте подходим к нашему методу с примером. Предположим, что мы имеем две строки abcdaf и acbcf . Обозначим их с s1 и s2 . Таким образом, самая длинная общая подпоследовательность этих двух строк будет «abcf» , которая имеет длину 4. Снова напоминаю вам, подпоследовательности не обязательно должны быть непрерывными в строке. Чтобы построить «abcf» , мы игнорировали «da» в s1 и «c» в s2 . Как это узнать, используя динамическое программирование?
Мы начнем с таблицы (2D-массив), содержащей все символы s1 в строке и все символы s2 в столбце. Здесь таблица 0-индексируется, и мы помещаем символы от 1 до и далее. Мы будем перемещать таблицу слева направо для каждой строки. Наша таблица будет выглядеть так:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Здесь каждая строка и столбец представляют длину самой длинной общей подпоследовательности между двумя строками, если мы берем символы этой строки и столбца и добавляем к префиксу перед ним. Например: Таблица [2] [3] представляет длину самой длинной общей подпоследовательности между «ac» и «abc» .
0-й столбец представляет собой пустую подпоследовательность s1 . Точно так же 0-я строка представляет собой пустую подпоследовательность s2 . Если взять пустую подпоследовательность строки и попытаться сопоставить ее с другой строкой, независимо от того, как долго длина второй подстроки, то общая подпоследовательность будет иметь длину 0. Таким образом, мы можем заполнить 0-й ряд и 0-й столбцы нулями. Мы получаем:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Давай начнем. Когда мы заполняем таблицу [1] [1] , мы спрашиваем себя, если бы у нас была строка a и другая строка a и ничего больше, какая будет самая длинная общая подпоследовательность здесь? Длина LCS здесь будет 1. Теперь рассмотрим таблицу [1] [2] . У нас есть строка ab и строка a . Длина LCS будет равна 1. Как вы можете видеть, остальные значения будут также 1 для первой строки, так как он рассматривает только строку a с abcd , abcda , abcdaf . Итак, наша таблица будет выглядеть так:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Для строки 2, которая теперь будет включать c . Для таблицы [2] [1] мы имеем ac с одной стороны, а с другой стороны. Таким образом, длина LCS равна 1. Откуда у нас это 1? С вершины, обозначающей LCS a между двумя подстроками. Итак, мы говорим, что если s1 [2] и s2 [1] не совпадают, то длина LCS будет максимальной длины LCS сверху или слева . Взяв длину LCS сверху, это означает, что мы не берем текущий символ из s2 . Аналогично, взяв длину LCS слева, мы не берем текущий символ из s1 для создания LCS. Мы получаем:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Итак, наша первая формула будет:
if s2[i] is not equal to s1[j]
Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif
Двигаясь дальше, для таблицы [2] [2] имеем строку ab и ac . Поскольку c и b не являются одинаковыми, мы помещаем максимум сверху или слева здесь. В этом случае это снова 1. После этого для таблицы [2] [3] имеем строку abc и ac . На этот раз текущие значения обеих строк и столбцов совпадают. Теперь длина LCS будет равна максимальной длине LCS до + 1. Как мы получаем максимальную длину LCS до сих пор? Мы проверяем диагональное значение, которое представляет наилучшее совпадение между ab и a . Из этого состояния для текущих значений мы добавили еще один символ к s1 и s2, который оказался одним и тем же. Таким образом, длина LCS, разумеется, возрастет. Мы поместим 1 + 1 = 2 в таблицу [2] [3] . Мы получаем,
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Итак, наша вторая формула будет:
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
endif
Мы определили оба случая. Используя эти две формулы, мы можем заполнить всю таблицу. После заполнения таблицы это будет выглядеть так:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | 1 | 2 | 3 | 3 | 3 | 3 |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | 1 | 2 | 3 | 3 | 3 | 4 |
+-----+-----+-----+-----+-----+-----+-----+-----+
Длина LCS между s1 и s2 будет равна таблице [5] [6] = 4 . Здесь 5 и 6 - длина s2 и s1 соответственно. Наш псевдокод будет:
Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
Table[0][i] = 0
endfor
for i from 1 to s2.length
Table[i][0] = 0
endfor
for i from 1 to s2.length
for j from 1 to s1.length
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
else
Table[i][j] = max(Table[i-1][j], Table[i][j-1])
endif
endfor
endfor
Return Table[s2.length][s1.length]
Сложность времени для этого алгоритма: O (mn), где m и n обозначает длину каждой строки.
Как узнать самую длинную общую подпоследовательность? Мы начнем с нижнего правого угла. Мы проверим, откуда это значение. Если значение идет по диагонали, то есть, если таблица [i-1] [j-1] равна таблице [i] [j] - 1 , мы нажимаем либо s2 [i], либо s1 [j] (оба одинаковы) и двигаться по диагонали. Если значение идет сверху, это означает, что если таблица [i-1] [j] равна таблице [i] [j] , мы переходим к вершине. Если значение идет слева, это означает, что если таблица [i] [j-1] равна таблице [i] [j] , мы перемещаемся влево. Когда мы достигнем самого левого или верхнего столбца, наш поиск заканчивается. Затем мы выставляем значения из стека и печатаем их. Псевдокод:
Procedure PrintLCS(LCSlength, s1, s2)
temp := LCSlength
S = stack()
i := s2.length
j := s1.length
while i is not equal to 0 and j is not equal to 0
if Table[i-1][j-1] == Table[i][j] - 1 and s1[j]==s2[i]
S.push(s1[j]) //or S.push(s2[i])
i := i - 1
j := j - 1
else if Table[i-1][j] == Table[i][j]
i := i-1
else
j := j-1
endif
endwhile
while S is not empty
print(S.pop)
endwhile
Следует отметить: если обе таблицы [i-1] [j] и таблица [i] [j-1] равны таблице [i] [j], а таблица [i-1] [j-1] не является равной таблице [i] [j] - 1 , для этого момента может быть два LCS. Этот псевдокод не рассматривает эту ситуацию. Вам придется решить эту проблему, чтобы найти несколько LCS.
Сложность времени для этого алгоритма: O (max (m, n)) .