Решатель динамического программирования Самая длинная общая подпоследовательность

предисловие

Запущена новая серия «Глядя на картинки, чтобы легко понять структуры данных и алгоритмы», в основном с использованием изображений для описания общих структур данных и алгоритмов, которые легко читать и понимать. В эту серию входят десятки куч, очередей, списков, деревьев, графов, сортировки и так далее.

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

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

Кроме того, следует отметить, что самая длинная общая подпоследовательность не совпадает с самой длинной общей подпоследовательностью.Давайте рассмотрим пример ниже.

Имеются последовательности S1 и S2, где S1=hello, S2=hero. Тогда самая длинная общая подпоследовательностьheo, а самая длинная общая подстрокаhe. Видно, что разница в том, что один допускает прерывность, другой требует непрерывности, а общим является сохранение порядка.

Жестокое истощение

Метод грубой силы является самым простым и интуитивным решением, поскольку он является насильственным, эффективность определенно самая низкая. имеют X_m=<x_1,x_2,…,x_m> и Y_n=<y_1,y_2,…,y_n> Две последовательности, исчерпывающий процесс сначала перечисляет все возможные подпоследовательности, для последовательности X количество ее подпоследовательностей достигает 2^m , поэтому временная сложность этой части достигает O(2^m) . И временная сложность каждой подпоследовательности, соответствующей последовательности Y, равна O(n) , поэтому временная сложность всего процесса равна O(n*2^m) . То есть временная сложность метода полного перебора достигает экспоненциального уровня, а длина последовательности на практике может быть большой, поэтому этот метод практически невозможно использовать.

Каково количество подпоследовательностей 2^m ? Все подпоследовательности последовательности можно рассматривать как последовательность, состоящую из нескольких (от 0 до m) элементов, удаленных из последовательности, например, ABC, когда 0 элементов удалено, это {ABC}, а удален 1 элемент. {BC, AC,AB}, когда удаляются 2 элемента, {C,B,A}, когда удаляются 2 элемента, и пусто, когда удаляются 3 элемента.

Грубые шаги сильного истощения:

Для последовательности X перечислите все подпоследовательности;
Для каждой подпоследовательности, совпадающей с последовательностью Y на шаге 1, запишите самую длинную совпадающую подпоследовательность;

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

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

оптимальное основание

Предположим, есть X_m=<x_1,x_2,…,x_m> и Y_n=<y_1,y_2,…,y_n> Две последовательности, обозначают самую длинную общую подпоследовательность, соответствующую двум последовательностям X и Y, как LCS(X_m,Y_n) ,КонечноПроцесс представляет собой задачу оптимизации. Чтобы проанализировать оптимальную подструктуру, нам нужно начать с последнего элемента последовательности X и последовательности Y. Есть два случая:

если, то есть последний элемент последовательности X и последовательности Y совпадают, что указывает на то, что элемент должен быть последним элементом общей подпоследовательности.В это время формула перехода состояния исходной задачи: $LCS(X_m,Y_n) =LCS(X_{m-1},Y_{n-1}) +X_m$ . Видно, что в этом случае исходная задача была успешно разложена на подзадачи, и оптимальное решение каждого этапа может быть получено через оптимальное решение подзадачи, которое соответствует оптимальной подзадаче.
если $x_m \neq y_n$ , то есть последние элементы последовательности X и последовательности Y не совпадают. На данный момент необходимо рассмотреть две ситуации:
1. еслине является последним элементом самой длинной общей подпоследовательности, формула перехода состояния задачи имеет вид $LCS(X_m,Y_n) =LCS(X_{m-1},Y_{n})$ , т.е. из $X_m=<x_1,x_2,…,x_{m-1}>$ ивстречается в обеих последовательностях.
2. еслине является последним элементом самой длинной общей подпоследовательности, формула перехода состояния задачи имеет вид $LCS(X_m,Y_n) =LCS(X_{m},Y_{n-1})$ , т.е. изи $Y_n=<y_1,y_2,…,y_{n-1}>$ встречается в обеих последовательностях.

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

перекрывающиеся подзадачи

После приведенного выше анализа мы разбиваем исходную проблему на три подзадачи:

$LCS(X_m,Y_n) =LCS(X_{m-1},Y_{n-1}) +X_m$
$LCS(X_m,Y_n) =LCS(X_{m-1},Y_{n})$
$LCS(X_m,Y_n) =LCS(X_{m},Y_{n-1})$

Можно видеть, что подзадачи перекрываются, например, для $LCS(X_{m-1},Y_{n})$ , когда последовательность $X_{m-1}$ с последовательностью $Y_{n}$ Когда последний элемент не совпадает, подзадача продолжает разлагаться на $LCS(X_{m-2},Y_{n-1})$ и $LCS(X_{m-1},Y_{n-1})$ , то же, что и предыдущая подзадача $LCS(X_m,Y_n) =LCS(X_{m-1},Y_{n-1}) +X_m$ середина $LCS(X_{m-1},Y_{n-1})$ перекрываются.

Следовательно, исходная задача имеет свойство перекрытия подзадач.

нет последействия

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

рекурсивная формула

Все проблемы были проанализированы, а затем определена рекурсивная формула, и все состояния и переходы состояний четко описаны рекурсивными формулами.

Предполагать c[i,j] за LCS(X_i,Y_j) длина, гдеi = 0,1,2,...m,j=0,1,2,...n.

c[i,j]= \left\{\begin{matrix} 0,& &if \quad i=0 \ or j=0\\ c[i-1,j-1]+1, & &if \quad i,j>0 \ and \ x_i=y_j \\ max(c[i,j-1],c[i-1,j])& &if \quad i,j>0 \ and \ x_i≠y_j \end{matrix}\right.

Как реализовать динамическое программирование

Существует два способа реализации динамического программирования, а именно: «сверху вниз» и «снизу вверх».

Нисходящий подход: в этом подходе результат вычисляется непосредственно с использованием рекурсивной формулы, а решение проблемы может быть представлено рекурсивно с использованием решений подзадач. Кроме того, для перекрывающихся подзадач ее можно запомнить, то есть сохранить в таблице кеша, и таблица кеша проверяется перед решением подзадачи.Если подзадача решена, мы можем использовать ее напрямую . Для нерешенных подзадач мы сначала решаем подзадачи, а затем сохраняем решения подзадач в кэш-таблице.

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

Статья слишком длинная и не будет опубликована сверху вниз.

подход «снизу вверх

В практической инженерии подход «снизу вверх» может использовать двумерную таблицу для записи процесса решения самой длинной общей подпоследовательности.

Теперь у нас есть последовательность X=HELLO и последовательность Y=HERO, и мы используем динамическое программирование для решения их самой длинной общей подпоследовательности восходящим образом. Инициализируйте всю таблицу в начале. Обратите внимание, что два измерения таблицы на одно измерение больше, чем соответствующие длины последовательностей. Дополнительное одно измерение используется для сохранения начального состояния. Исходное состояние — все 0. Эти начальные состояния используются в процессе расчета.

Создать форму подвопроса

Начните с первого элемента последовательности X и сравните его с первым элементом последовательности Y, потому чтоH=H, так что LCS(1,1)=LCS(0,0)+1=1.

тогдаH!=E, так что LCS(1,2)=max(LCS(1,1), LCS(0,2)), то есть LCS(1,2)=LCS(1,1)=1.

тогдаH!=R, так что LCS(1,3)=max(LCS(1,2), LCS(0,3)), то есть LCS(1,3)=LCS(1,2)=1.

тогдаH!=O, так что LCS(1,4)=max(LCS(1,3), LCS(0,4)), то есть LCS(1,4)=LCS(1,3)=1.

Аналогично второй элемент последовательности X также сравнивается с каждым элементом последовательности Y и результат заносится в соответствующую таблицу Результат сравнения второго элемента последовательности X следующий.

Результат сравнения третьего элемента последовательности X следующий.

Результат сравнения четвертого элемента последовательности X следующий.

Сравнивается пятый элемент последовательности X, то есть конечный результат следующий.

Итак, можно видеть, что LCS(5,4)=3, что означает, что длина самой длинной общей подпоследовательности последовательности X и последовательности Y равна 3.

В то же время видно, что с помощью восходящего метода динамического программирования нам нужно только построить таблицу, чтобы получить окончательный результат, а временная сложность построения таблицы составляет O (m * n), что значительно снижает временную сложность.

Построить самую длинную общую подпоследовательность

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

То есть сначала оцените, одинаковы ли заданные элементы двух последовательностей. чтобы идти влево или вверх в зависимости от размера значения.Если значение одинаковое, вы можете идти влево и вверх.

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

так какO=O, поэтому O принадлежит элементу самой длинной общей подпоследовательности, выведите его и вернитесь на одну клетку назад по диагонали.

так какL!=R, поэтому ни один из них не принадлежит элементам самой длинной общей подпоследовательности, а значения слева направо равны, что может быть выбрано произвольно Здесь мы выбираем подняться на одну сетку.

продолжать, потому чтоL!=R, поэтому ни один из них не принадлежит элементам самой длинной общей подпоследовательности, а значения слева направо равны, что может быть выбрано произвольно Здесь мы выбираем подняться на одну сетку.

продолжать, потому чтоE!=R, так что ни один из них не принадлежит к элементам самой длинной общей подпоследовательности, где значение слева больше, чем значение вверху, выберите переход на одну сетку влево.

продолжать, потому чтоE=E, значит, E принадлежит элементу самой длинной общей подпоследовательности, выведите его, а затем вернитесь на одну клетку назад по диагонали.

продолжать, потому чтоH=H, значит, H принадлежит элементу самой длинной общей подпоследовательности, выведите ее, она в это время подошла к концу, и теперь весь вывод — это самая длинная общая подпоследовательность, то естьHEO. Временная сложность построения самой длинной общей подпоследовательности составляет O(m+n).

------------- Рекомендуем прочитать ------------

Краткое изложение моих проектов с открытым исходным кодом (машинное и глубокое обучение, НЛП, сетевой ввод-вывод, AIML, протокол mysql, чат-бот)

Зачем писать «Анализ проектирования ядра Tomcat»

2018 Алгоритмы структуры сводных данных

Сборник статей по машинному обучению за 2018 г.

Сводка статей о глубине Java за 2018 г.

Резюме по обработке естественного языка за 2018 г.

Резюме глубокого обучения за 2018 г.

Сводка статей об исходном коде JDK за 2018 г.

Обзор Java Concurrency Core за 2018 г.

Итоговые чтения за 2018 год

Поговори со мной, задай мне вопросы:

Добро пожаловать, чтобы следовать: