Задача нахождения наибольшей общей подпоследовательности - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Алгоритм нахождения спектра больших матриц 1 34.61kb.
Ю. О. Чернышев «Разработка параллельного алгоритма нахождения оптимального... 1 80.39kb.
Производная. Алгоритм нахождения производной 1 200.31kb.
Дискретное программирование 1 49.85kb.
Задание Задача нахождения оптимального плана 1 46.66kb.
Контрольные вопросы по курсу Основная задача линейного программирования. 1 44.79kb.
Территориальная подсудность по гражданским делам судов общей юрисдикции 1 23.44kb.
Задача №1 Производственная задача 14 Задача №4 Задача о распределении... 9 799.25kb.
Потоки в сетях Понятие сети. Пример сети. Потоки в сетях. Разрезы. 1 31.69kb.
Задача сегодняшнего дня сделать Академию наук современным действенным... 1 216.35kb.
Территориальная подсудность по гражданским делам судов общей юрисдикции... 1 64.35kb.
Учебно-методический комплекс по дисциплине «050102-11 R. plM» «Исследование... 1 252.45kb.
Направления изучения представлений о справедливости 1 202.17kb.

Задача нахождения наибольшей общей подпоследовательности - страница №1/1

Задача нахождения наибольшей общей подпоследовательности (англ. longest common subsequence, LCS) — это задача поиска последовательности, которая является подпоследовательностью нескольких последовательностей (обычно двух). Часто задача определяется как поиск всех наибольших подпоследовательностей. Это классическая задача информатики, которая имеет приложения, в частности, в задаче сравнения текстовых файлов (утилита diff), а также в биоинформатике.

Подпоследовательность можно получить из некоторой конечной последовательности, если удалить из последней некоторое множество её элементов (возможно пустое). Например, BCDB является подпоследовательностью последовательности ABCDBAB. Будем говорить, что последовательность Z является общей подпоследовательностью последовательностей X и Y, если Z является подпоследовательностью как X, так и Y. Требуется для двух последовательностей X и Y найти общую подпоследовательность наибольшей длины. Заметим, что НОП может быть несколько.



Содержание

  • 1 Решение задачи

    • 1.1 Полный перебор

    • 1.2 Метод динамического программирования

  • 2 Реализация в языках программирования

    • 2.1 C++

    • 2.2 Ruby

  • 3 См. также

Решение задачи

Сравним два метода решения: полный перебор и динамическое программирование.



Полный перебор

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



Метод динамического программирования







A

B

C

B




0

0

0

0

0

D

  0

← 0

← 0

← 0

← 0

C

  0

← 0

← 0

↖ 1

← 1

B

  0

← 0

↖ 1

← 1

↖ 2

A

  0

↖ 1

← 1

← 1

↑ 2

Вначале найдём длину наибольшей подпоследовательности. Допустим, мы ищем решение для случая (n1, n2), где n1, n2 — длины первой и второй строк. Пусть уже существуют решения для всех подзадач (m1, m2), меньших заданной. Тогда задача (n1, n2) сводится к меньшим подзадачам следующим образом:

 f(n_1, n_2) = \left \{ \begin{array}{ll} 0, & n_1 = 0 \or n_2 = 0 \\ f(n_1 - 1, n_2 - 1) + 1, & s[n_1] = s[n_2] \\ max(f(n_1 - 1, n_2), f(n_1, n_2 - 1)), & s[n_1] \neq s[n_2] \end{array} \right.

Теперь вернемся к задаче построения подпоследовательности. Для этого в существующий алгоритм добавим запоминание для каждой задачи той подзадачи, через которую она решается. Следующим действием, начиная с последнего элемента, поднимаемся к началу по направлениям, заданным первым алгоритмом, и записываем символы в каждой позиции. Это и будет ответом в данной задаче.

Очевидно, что время работы алгоритма будет \mathrm{o}\,(n_1 \cdot n_2).

Реализация в языках программирования

string getLongestCommonSubsequence(const string& a, const string& b)

{

vector > max_len;



max_len.resize(a.size() + 1);

for(int i = 0; i <= static_cast(a.size()); i++)

max_len[i].resize(b.size() + 1);

for(int i = static_cast(a.size()) - 1; i >= 0; i--)

{

for(int j = static_cast(b.size()) - 1; j >= 0; j--)



{

if(a[i] == b[j])

{

max_len[i][j] = 1 + max_len[i+1][j+1];



}

else


{

max_len[i][j] = max(max_len[i+1][j], max_len[i][j+1]);

}

}

}



string res;

for(int i = 0, j = 0; max_len[i][j] != 0 && i < static_cast(a.size()) && j < static_cast(b.size()); )

{

if(a[i] == b[j])



{

res.push_back(a[i]);

i++;

j++;


}

else


{

if(max_len[i][j] == max_len[i+1][j])

i++;

else


j++;

}

}



return res;

}

Ruby

#>> a = "aaaaabbbb34354354345"

#>> b = "abbb34aaabbbb"

#>> longest_common_subsequence(a, b)

#=> "aaaabbbb"

def longest_common_subsequence(a, b)

max_len = Array.new(a.size + 1, 0)

max_len.map! {Array.new(b.size + 1, 0)}

(a.size - 1).downto(0) do |i|

(b.size - 1).downto(0) do |j|

if a[i] == b[j]

max_len[i][j] = 1 + max_len[i+1][j+1]

else


max_len[i][j] = [max_len[i+1][j], max_len[i][j+1]].max

end


end

end


res = ""

i = 0


j = 0

while max_len[i][j] != 0 && i < a.size && j < b.size

if a[i] == b[j]

res << a[i]

i += 1

j += 1


else

if max_len[i][j] == max_len[i+1][j]

i += 1

else


j += 1

end


end

end


res

end


№2

Отметим, подпоследовательность может и не являться подстрокой (то есть, её элементы не обязательно идут подряд в исходной последовательности). Формально, для строки x длины n необходимо найти максимальное число l и соответствующую ему возрастающую последовательность индексов i1..il, таких что x[i_{k}] < x[i_{k+1}]\,\forall {k}\,\mathcal{2}{\,1\,..\,l-1} . Наибольшая увеличивающая подпоследовательность имеет применения в физике, математике, теории представления групп, теории случайных матриц. В общем случае известно решение этой задачи за время n log n[1] в худшем случае.



Родственные алгоритмы

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

  • В частном случае, если строка является перестановкой 1..n, задача имеет решение за n log log n[2] с использованием деревьев ван Эмд Босса.

  • При использовании дерева, построенного для элементов алфавита, возможно решение задачи за O( n log A ), где A - мощность алфавита, определяемая заранее. При реализации сбалансированными деревьями, необязательно задавать A наперёд. По очевидным причинам A ограничивается длиной строки.

  • Возможно также свести задачу к поиску длиннейшего пути в ориентированном ациклическом графе, задавая рёбра между возрастающими элементами. Хотя подсчёт длиннейшего пути будет занимать линейное время от числа рёбер, в худшем случае оно может быть квадратично от длины строки.

Пример эффективного алгоритма

Для строки x будем хранить массивы M и P длины n. M[i] содержит наименьший по величине из последних элементов возрастающих подпоследовательностей xnj длины i, (\mathcal{8}j\,\mathcal{2}\,1\,..\,i:x[n_{j}] \le\,m[i]), найденных на данном шаге. P[i] хранит индекс предшествующего символа для наидлиннейшей возрастающей подпоследовательности, оканчивающейся в i-й позиции. На каждом шаге будем хранить текущий максимум длины подпоследовательности и соответствующий индекс конечного символа, не забывая поддерживать свойства массивов. Шаг представляет собой переход к следующему элементу строки, для каждого перехода потребуется не более логарифма времени (бинарный поиск по массиву M).

L = index = M[0] = 0

for i = 1 to n

бинарный поиск наибольшего индекса j ≤ L, удовлетворяющего X[M[j]] < X[i]

P[i] = M[j]

if j == L or X[i] < X[M[j+1]] // нашли более оптимальную подпоследовательность

M[j+1] = i



L = max{L, j+1}




Футбольный комментатор: человек, который профессионально мешает смотреть футбол. Максим Звонарев
ещё >>