наибольшая общая подпоследовательность c код

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

Содержание

Наивное решение [ править ]

Переберем все различные подпоследовательности обеих строк и сравним их. Тогда искомая [math]LCS[/math] гарантированно найдётся, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.

Динамическое программирование [ править ]

Для решения данной задачи используем Принцип оптимальности на префиксе.

Доказательство оптимальности [ править ]

Решение [ править ]

Обозначим как [math] lcs[i][j] [/math] [math]LCS[/math] префиксов данных последовательностей, заканчивающихся в элементах с номерами [math] i [/math] и [math] j [/math] соответственно. Получается следующее рекуррентное соотношение:

Построение подпоследовательности [ править ]

Псевдокод [ править ]

Оптимизация для вычисления только длины [math]LCS[/math] [ править ]

Длина кратчайшей общей суперпоследовательности [ править ]

Решение для случая k строк [ править ]

Найдем решение для 3 строк.

Наивное решение подсчёта [math]LCS[/math] нескольких строк при помощи последовательного нахождения [math]LCS[/math] двух строк и уменьшением набора строк на единицу, не срабатывает. Это доказывается следующим контрпримером. Даны три последовательности:

[math]X = \left \langle A, B, C, D, E\right \rangle [/math]

[math]Y = \left \langle D, E, A, B, C\right \rangle [/math]

[math]Z = \left \langle D, E, F, G, H\right \rangle [/math]

Подсчитаем [math]V = LCS(X,Y) = \left \langle A, B, C \right \rangle[/math]

Это неверно, так как [math]LCS(X,Y,Z) = \left \langle D, E \right \rangle[/math]

Доказательство:[math]\triangleright[/math]Доказательство аналогично доказательству для двух последовательностей.[math]\triangleleft[/math]

Решение [ править ]

Алгоритм Хиршберга [ править ]

Алгоритм [ править ]

Псевдокод [ править ]

Доказательство корректности [ править ]

Асимптотика [ править ]

Источник

Нахождение максимальной общей подпоследовательности

Определения

Последовательность представляет собой упорядоченный набор элементов. Строка — это частный случай последовательности, дальнейшие примеры будут для простоты рассматривать именно строки, но без изменений их можно использовать и для произвольного текста или чего-нибудь последовательного еще.
Пусть имеется последовательность x, состоящая из элементов x₁x₂. x_m и последовательность y, состоящая из элементов y₁y₂. y_n. z — подпоследовательность x в том случае, если существует строго возрастающий набор индексов элементов x, из которых получается z.
Общей подпоследовательностью для x и y считаем такую последовательность z, которая является одновременно подпоследовательностью x и подпоследовательностью y.
Максимальная общая подпоследовательность — это общая подпоследовательность с максимальной длинной. Далее по тексту будем использовать сокращение LCS.
В качестве примера, пусть x=HABRAHABR, y=HARBOUR, в этом случае LCS(x, y)=HARBR. Можно уже переходить непосредственно к алгоритму вычисления LCS, но, хорошо бы понять, для чего нам может это может понадобиться.

Применение на практике

Наиболее частое применение — использование в программах для сравнения файлов, например GNU diff. Имея найденную для двух текстов LCS, составить список элементарных изменений для превращения x в y или обратно задача тривиальная. В качестве бонуса, на основе длины общей подпоследовательности можно задать метрику для определения схожести двух последовательностей. Все, теперь точно можно переходить к делу.

Первый подход или народное творчество

Теперь можно подумать, что с этой реализацией не так. В наихудшем случае, когда между x и y нет одинаковых элементов LCS_RECURSIVE вызовется 2 len(x)+len(y) раз, при уровне рекурсии len(x)+len(y). Даже если закрыть глаза на производительность, код:

без дополнительного вызова sys.setrecursionlimit удачно не выполнится. Не самая удачная реализация.

Динамическое программирование или 64 кб хватит всем

Рассматриваемый алгоритм также известен как алгоритм Нидлмана—Вунша (Needleman-Wunsch).
Весь подход сводится к поэтапному заполнению матрицы, где строки представляют собой элементы x, а колонки элементы y. При заполнении действуют два правила, вытекающие из уже сделанных наблюдений:
1. Если элемент x_i равен y_j то в ячейке (i,j) записывается значение ячейки (i-1,j-1) с добавлением единицы
2. Если элемент x_i не равен y_j то в ячейку (i,j) записывается максимум из значений(i-1,j) и (i,j-1).
Заполнение происходит в двойном цикле по i и j с увеличением значений на единицу, таким образом на каждой итерации нужные на этом шаге значения ячеек уже вычислены:

Иллюстрация происходящего:

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

Сложность алогоритма — O(len(x)*len(y)), такая же оценка по памяти. Таким образом, если я захочу построчно сравнить два файла из 100000 строк, то нужно будет хранить в памяти матрицу из 10 10 элементов. Т.е. реальное использование грозит получением MemoryError почти на ровном месте. Перед тем как перейти к следующему алгоритму заметим, что при заполнении матрицы L на каждой итерации по элементам x нам нужна только строка, полученная на предыщем ходу. Т.е. если бы задача ограничивалась только нахождением длины LCS без необходимости вычисления самой LCS, то можно было бы снизить использование памяти до O(len(y)), сохраняя одновременно только две строки матрицы L.

Борьба за место или Алгоритм Хишберга (Hirschberg)

Теперь непосредственно, о самом алгоритме. Он представляет собой классический divide and conquer: пока в последовательности x есть элементы, мы делим x пополам, находим подходящее разбиение для y и возвращаем сумму рекурсивных вызовов для пар последовательностей (xb,yb) и (xe,ye). Заметим, что в тривиальном случае, если x состоит из одного элемента и встречается в y мы просто возвращаем последовательность из этого единственного элемента x.

Теперь требования по памяти у нас O(len(y)), время, необходимое для вычисления, удвоилось, но асимптотически по-прежнему O(len(x)len(y)).

Алгоритм Ханта-Шуманского (Hunt-Szymanski Algorithm)

Первое что нам потребуется это создание хэш таблицы matchlist, которая будет содержать индексы элементов второй последовательностей. Время необходимое для этого O(len(y)). Следующий код на питоне делает это:

Далее, перебирая элементы последовательности x, заполняем массив THRESH соответсвующими индексами из заготовленного matchlist, таким образом, что значением k-го элемента THRESH должен быть индекс y_index, при условии что THRESH[k-1]

Источник

Наибольшая общая подпоследовательность

Здравствуйте,
написал код для задачи

Наибольшая общая подпоследовательность
Задана последовательность A[1..N] и последовательность B[1..M]. Выведите длину наибольшей общей подпоследовательности.

Входные данные
В первой строке заданы N, M (1 0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Наибольшая общая подпоследовательность
Я правда не знаю в том ли разделе я создал. Надо определить наибольшую общую.

Наибольшая возрастающая подпоследовательность (LIS)
Доброго времени суток! Я не сильно разбираюсь в шарпе(совсем) и при выполнении одного задания.

Наибольшая общая подпоследовательность
Здравствуйте, подскажите, пожалуйста, каким способом можно найти НОП для количества строк >=2

здесь 2 строки могут быть разного размера

Добавлено через 26 минут
Вот, я подправил, вдруг кому-то понадобится

на входных данных
3 2
1 2 3
1 2
выдает 3

объясните пожалуйста Ваш ход мысли
я немного не понимаю зачем вы сравниваете числа?

здесь наибольшей общей подпоследовательностью называется срока, которая состоит из элементов входящих и в 1ую и 2ую строку, элементы могут браться не все и по порядку, а например через один, но порядок букв должен соблюдться, например из строки 3 4 0 2 мы не можем взять подпоседовательность 0 3, а можем 3 0

ну вот как-то коряво, но тем не менее вроде понятно)

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Наибольшая пилообразная подпоследовательность
добрый вечер. Кто нибудь может подсказать? Числовая последовательность называется пилообразной.

Наибольшая монотонная подпоследовательность
Пожалуйста, подскажите не готовый ответ, а идею. Хочется самой дойти. Дана конечная.

Источник

Наибольшая общая подпоследовательность

Требуется вывести наибольшую общую подпоследовательность для двух наборов чисел (длины n и m).
Мое решение не проходит половину тестов. Как исправить?

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Наибольшая возрастающая подпоследовательность за O(NlogN)
Здравствуйте! Вот тут написал код НВП за О(NlogN).Но на тестирующей системе он выдает на тесты.

Задача «Общая подпоследовательность»
Добрый день. Имеется, с виду, тривиальная задача. Напрягает только то, что даны три.

Наибольшая общая подстрока
Люди из раздела «алгоритмы» молчат.. спрошу тут..Прошу прощения за «флуд». На днях отправил резюме.

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Динамическое программирование. Требуется идея для решения. Общая подпоследовательность
Заданы две строки длиной не больше 10000. Нужно найти самую хорошую подпоследовательность, которая.

Самая длинная общая подпоследовательность строк/ НОП строк (Динамическое программирование)
Доброго времени суток. Помогите пожалуйста разобраться с алгоритмом НОП строк. Суть алгоритма.

Наибольшая общая подпоследовательность
Я правда не знаю в том ли разделе я создал. Надо определить наибольшую общую.

Источник

Задача «Общая подпоследовательность»

Добрый день. Имеется, с виду, тривиальная задача. Напрягает только то, что даны три последовательности.

Условие
Даны три последовательности целых чисел. Ваша задача — найти их наибольшую общую
подпоследовательность.

Формат входного файла
Входной файл содержит описание трех последовательностей. Каждая последовательность
задается двумя строчками. Первая строка содержит длину последовательности n (1 ≤ n ≤ 100),
а вторая — ее элементы (32-х битные целые числа).

Формат выходного файла
Первая строка выходного файла должна содержать длину максимальной общей
подпоследовательности. Саму подпоследовательность необходимо вывести во второй строке.
Если таких строк несколько, можно вывести любую из них.

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Динамическое программирование. Требуется идея для решения. Общая подпоследовательность
Заданы две строки длиной не больше 10000. Нужно найти самую хорошую подпоследовательность, которая.

Самая длинная общая подпоследовательность строк/ НОП строк (Динамическое программирование)
Доброго времени суток. Помогите пожалуйста разобраться с алгоритмом НОП строк. Суть алгоритма.

Просто я просил ко мне обращаться на Вы. Но Вы этого не видите или не хотите видеть, поэтому я себя сейчас веду не спокойной. И отзыв этот будет не последним.

приличный компилятор должен выдавать ошибку, т.к. результат выполнение функции «_intersection» не может быть передан по ссылке.

А свой пример я покажу тогда, когда посчитаю нужным. Я сюда не хвастаться пришёл.

Источник