Укрощаем динамику в задаче о палиндромах

Я уже давно не студент, но в свободное время изучаю материалы по Computer Science. Мне нравится получать знания и делиться ими. Недавно я наткнулся на любопытную задачу в известном учебнике "Алгоримы: Построение и Анализ". В этой статье я продемонстрирую принципы динамического программирования, используя эту задачу. Она интересная, не очень сложная и для её решения не требуется писать какие-то дополнительные структуры данных или библиотеки. Формулировка умещается в одно предложение:

Найти самую длинную палиндромную подпоследовательность в слове w длиной n.

Кому интересно, прошу под кат.

Не путайте понятия "подстрока" и "последовательность". В первую входят только соседние буквы, а вторая может быть составлена из сколь угодно далёких друг от друга букв. Например, в слове "математика" подпоследовательностями будут: "мак" (математика), "атака" (математика) или "метка" (математика). "Палиндромная" означает, что подпоследовательность должна читаться одинаково как слева-направо, так и справа-налево. Последовательность из одной буквы тоже будет палиндромной, хоть это и вырожденный случай. Понятно, что в одной строке может быть много таких палиднромных подпоследовательностей. Нас же интересует самая длинная. Если w сама палиндром, то ответом будет вся строка. Иначе ответ надо как-то искать, например, в слове "коловорот" ответом будет "оовоо".

Вроде звучит просто, приступим к анализу. Для начала попробуем решить "в лоб". Сколько всего подпоследовательностей есть у слова длиной n? Посчитать несложно. Составляя подпоследовательность, мы либо берём i-ю букву, либо нет. Выходит, каждой подпоследовательности можно поставить в однозначное соответствие двоичное число с n битами (возможно, начинающиеся с нулей). Раз таких чисел всего 2^n, то подпоследовательностей будет на одну меньше, т.к. пустую мы не рассматриваем. Выходит, пространство поиска растёт экспоненциально с ростом n. Такой расклад сразу даёт понять, что "в лоб" решать нет смысла. Никому не нужна программа, которая даже на относительно небольших строках (с n = 1000) будет выполняться веками. Весь смысл компьютеров в том, что они справляются с механическими задачами гораздо быстрее нас, а если компьютер выполняет программу дольше человека, то зачем спрашивается стоило "огород городить"?

Небольшое отступление

Вообще, вы когда-нибудь задумывались откуда берётся качественное различие во времени работы алгоритмов? Почему вообще всем алгоритмы не работают, скажем, за линейное время? Интуитивно понятно, что время выполнения зависит от сложности (энтропии, количества информации) задачи, которую решает алгоритм. Что из себя представляет эта сложность? Я придумал такую аналогию — вот есть определённый объём воды, который нужно переместить из точки А в точку Б. Вода, как известно, вещество несжимаемое, поэтому её можно только перелить в какую-то ёмкость. Изначально этот объём нам неизвестен, мы можем только прийти с ёмкостью, попробовать перелить в неё всю воду и посмотреть не пролито ли что-то. Можно взять с собой несколько ёмкостей разного объёма, можно даже проливать остатки, если мы решим что полный объём нам не нужен.

В этой аналогии вода — это врождённая "энтропия" задачи, процесс переноса — алгоритм, а ёмкости — ресурсы, которые необходимо затратить на решение. В информатике хорошо известен т.н. "time-space trade-off" (компромисс между временем и памятью), когда большую временную сложность можно "перелить" в память, качественно уменьшив время работы алгоритма. Кроме времени и памяти есть ещё и другие ёмкости, например, вероятность. Ради выигрыша во времени требование "всегда завершаться только с правильным результатом" можно ослабить если позволить компьютеру иногда ошибаться, но при этом контролировать вероятность ошибки. В этом привлекательность алгоритмов Монте-Карло. То есть вместе с ёмкостями "время" и "память" мы взяли с собой "вероятность", в которую можно перелить часть воды из "времени", но общий объём останется прежним. Под "пролитием" ненужной воды я имею в виду ограничение задачи на какой-то частный случай, в котором присутствует некая регулярность входных данных. Например, если рассматривать только целые числа из определённого интервала, то можно сортировать за линейное время. Поиск в отсортированном массиве занимает логарифм времени, а не линию. Обычно на практике хватает именно такого частного случая, да и сами размеры редко превышают какие-то разумные пределы. Другая неочевидная ёмкость — длина исходного кода.

Самое главное, что мы не знаем заранее точный объём воды. Мы можем только измерять его ёмкостями, но редко бывает так, что мы находим ёмкость вровень сложности. В истинном объёме многих задач мы не уверенны до сих пор (P vs. NP). Можно конечно взять с собой целую цистерну (решение "в лоб"), тогда точно ничего не прольётся, но в этой цистерне вполне может плескаться одна лишь кружка.

Вернёмся к нашей задаче.

Решение динамикой

На помощь приходит техника динамического программирования. Обычно динамика применяется там, где нужно найти некоторое оптимальное решение. Вкратце, суть — задача разбивается на меньшие подзадачи до тех пор, пока не сведётся к тривиальному случаю. Затем их решения запоминаются (мемоизируются), и в конце комбинируются в решение основной. Главное отличие от метода "разделяй и властвую" заключается том, что оптимальное решение основной задачи состоит из оптимальных решений подзадач. Также решения подзадач запоминаются, чтобы не вычислять одно и то же по несколько раз. В нашей задаче это длина палиндрома. Однако "динамика" не универсальна. Чтобы быть применимой, задача должна обладать т.н. оптимальной структурой, т.е. удовлетворять следующим критериям:

• Оптимальное решение целевой состоит из оптимальных решений подзадач.
• Подзадачи независимы, т.е. решение одной не влияет на решение другой.
• Подзадачи часто повторяются
  Техника запоминания как раз окупается за счёт последнего критерия.

Что такое мемоизация? Это частный случай кеширования, когда сохраняется результат вычисления некоторой функции f в зависимости от значений аргументов. Чтобы мемоизация сработала, f не должна иметь никаких побочных эффектов (т.е. быть "чистой").

Начнём с разбора частных случаев. Если w состоит из одной буквы, то решать нечего. Что, если у нас две буквы? Тогда ответом будет либо вся строка, если они одинаковы, либо одна буква. Если букв три, то надо сравнить первую и третью букву. Если они равны, то ответом будет вся строка, иначе задача сводится к предыдущей. Понятно, что нам надо как-то найти границы палиндрома в строке.

Вообще, в любом алгоритме динамического программирования есть таблица, хранящая решения подзадач. Пусть palindrome[i, j] хранит самую длинную палиндромную подпоследовательность в подстроке w[i, j]. Решение исходной задачи хранится в palindrome[1, n]. Для простоты считаем что индексы начинаются с единицы. Представим, что мы уже заполнили всю таблицу, кроме palindrome[1, n]. Как нам скомбинировать решения подзадач? Понятно, что самая длинная палиндромная подпоследовательность может храниться либо в w[1, n-1], либо в w[2, n], либо в w[2, n-1]. Причём если первая и последняя буквы в w совпадают, то ответом однозначно будет w[1] + palindrome[2, n-1] + w[n]. У нас получилась рекурсивная формула:

1. palindrome[j, i] = пустой строке, если j > i
2. palindrome[i, i] = w[i].
3. palindrome[i, j] = w[i] + palindrome[i + 1, j - 1] + w[j] если w[i] = w[j]
4. palindrome[i, j] = max{palindrome[i+1, j], palindrome[i, j-1], palindrome[i+1, j-1]}
   Здесь хорошо видно для чего нужны три критерия динамики и почему без них этот метод не сработает. Такую формулу легко запрограммировать на любом языке, я выбрал Python из-за его простоты:

def solve(s):
    palindromes = [['' for i in range(len(s))] for j in range(len(s))]
    n = len(s) - 1
    result = solve_memoized_rec(s, palindromes, 0, n)
    return result

def solve_memoized_rec(s, palindromes, i, j):
    if palindromes[i][j]:
        return palindromes[i][j]
    else:
        if i > j:
            solution = ''
        elif i == j:
            solution = s[i]
        elif s[i] == s[j]:
            prev = solve_memoized_rec(s, palindromes, i + 1, j - 1)
            solution = s[i] + prev + s[j]
        else:
            from_left = solve_memoized_rec(s, palindromes, i + 1, j)
            from_right = solve_memoized_rec(s, palindromes, i, j - 1)
            both = solve_memoized_rec(s, palindromes, i + 1, j - 1)
            solution = max(from_left, from_right, both, key=len)
        palindromes[i][j] = solution
        return solution

Рекурсивная функция solve_memoized_rec мемоизирует результаты в таблицу palindromes, это позволяет добиться полиномиального времени работы. Если запоминание отсутствует, то есть опасность того, что время работы будет экспоненциальным. Не знаю как вам, но мне очень нравятся рекурсивные алгоритмы из-за их элегантности (не путать с эффективностью). Если формула, на которой основывается такой алгоритм, верна, то можно не беспокоиться о его корректности. Однако у них есть один серьёзный недостаток — довольно непросто оценить временную сложность такого алгоритма. В итеративных вариантах всё просто — считаешь количество вложенных циклов, получаешь степень n (упрощённо, конечно). Но при реализации итеративного варианта можно легко напортачить с границами циклов, совершив т.н. off-by-one error.

Рекурсивные варианты ещё называют "нисходящим методом", потому что мы как бы идём "сверху вниз" по таблице palindromes. Итеративный вариант наоборот будет "восходящим". В нём мы сначала решаем все тривиальные подзадачи, а потом уже постепенно "восходим" до вычисления palindromes[1, n].

Аккуратное программирование восходящего варианта даст такой результат:

def solve_iterative(s):
    n = len(s)
    palindromes = [['' for i in range(n)] for j in range(n)]
    for k in range(1, n + 1):
        for i in range(n - k + 1):
            j = i + k - 1
            if i == j:
                solution = s[i]
            elif s[i] == s[j]:
                solution = s[i] + palindromes[i + 1][j - 1] + s[j]
            else:
                solution = max(palindromes[i + 1][j], palindromes[i][j - 1], palindromes[i + 1][j - 1], key=len)
            palindromes[i][j] = solution
    return palindromes[0][n - 1]

Заметьте, что формула никуда не делась, разве что отпала надобность в первом пункте с i > j. Понятно, что такой алгоритм отработает за n^2.

Выводы

Мы рассмотрели метод динамического программирования на примере одной алгоритмической задачи, составили формулу и реализовали алгоритм решения как восходящим, так и нисходящим методом. На этом всё, до встречи в следующих статьях!

Я приветствую любую обратную связь как по содержанию статьи, так и по коду. Мой телеграмм: @outofbound