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

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

В предыдущей статье было о: жадных алгоритмах. Здесь далее текст пойдёт о динамическом программировании.

Задача о рюкзаке

Задача о рюкзаке была описана в предыдущей статье.

Вернёмся к задаче о рюкзаке. У вас есть рюкзак, в котором можно унести товары общим весом до 4 кг. Есть 3 предмета, которые можно положить в рюкзак.

Какие предметы следует положить в рюкзак, чтобы стоимость добычи была максимальной?

Простое решение

Простой способ решения выглядит так: вы перебираете все возможные множества товаров и находите множество с максимальной стоимостью. Такое решение работает очень медленно. Для 3 предметов приходится обработать 8 множеств, для 4 — 16 и т.д. С каждым добавленным предметом количество множеств удваивается. Такое решение будет выполняться за время: . Это слишком медленно!

Для любого сколько-нибудь значительного количества предметов это неприемлемо долго! Можно воспользоваться приближённым решением, но такое решение может существенно не совпадать с оптимальным. Как вычислить оптимальное решение? С помощью динамического программирования!

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

Рассмотрим как работает данный способ решения задачи. Процедура решения начинается с решения подзадач с постепенным переходом к решению полной задачи. В задаче о рюкзаке начать следует с решения задачи для меньшего рюкзака(или "подрюкзака"), а потом на этой основе попытаться решить исходную задачу.

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

Для начала рассмотрим алгоритм в действии. Каждый алгоритм динамического программирования начинается с таблицы. Вот как выглядит таблица для задачи о рюкзаке:

Строки таблицы представляют предметы, а столбцы — ёмкость рюкзака от 1 до 4 кг. Все эти столбы нужны, потому что они упрощают вычисление стоимостей "подкрюкзаков". В исходном состоянии таблица пуста. Нам предстоит заполнить каждую ячейку таблицы. После того как таблица будет заполнена, вы получите ответ на свою задачу. Пожалуйста, внимательно разберитесь в происходящем. Нарисуйте собственную таблицу.

Гитара

Точная формула для вычисления значений в таблице будет приведена позднее, а пока ограничимся общим описанием. Начнём с первой строки. Строка снабжена пометкой «гитара»; это означает, что вы пытаетесь уложить гитару в рюкзак. В каждой ячейке принимается простое решение:класть гитару в рюкзак или нет? Помните: мы пытаемся найти множество элементов с максимальной стоимостью.

В первой ячейке емкость рюкзака равна 1 кг. Гитара также весит 1 кг — значит, она поместится в рюкзак! Итак, стоимость этой ячейки составляет 1500₽, а в рюкзаке лежит гитара. Начнем заполнять ячейку:

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

Процедура повторяется для остальных ячеек строки. Вспомните, что текущей является первая строка, поэтому выбирать приходится только из одного предмета — гитары. Считайте, что два других предмета пока недоступны. Почему все это делается для рюкзаков с емкостью 1, 2 и т.д., если в задаче речь идет о рюкзаке с емкостью 4 кг? Метод динамического программирования начинает с малых задач, а затем переходит к большой задаче. Вы решаете подзадачи, которые помогут в решении большой задачи. После того как первая строка будет заполнена, таблица будет выглядеть так:

Помните, что мы стремимся обеспечить максимальную стоимость предметов в рюкзаке. Эта строка представляет текущую лучшую оценку максимума. Итак, на данный момент из этой строки следует, что для рюкзака с емкостью 4 кг максимальная стоимость предметов составит 1500₽. Это решение неокончательно. В процессе работы алгоритма оценка будет уточняться.

Магнитофон

Займемся следующей строкой, которая относится к магнитофону. Теперь, когда вы перешли ко второй строке, появляется выбор между магнитофоном и гитарой. В каждой строке можно взять предмет этой строки или предметы, находящиеся в верхних строках. Таким образом, сейчас нельзя выбрать ноутбук, но можно выбрать магнитофон и/или гитару. Начнем с первой ячейки (рюкзак с емкостью 1 кг). Текущая максимальная стоимость предметов, которые можно положить в рюкзак с емкостью 1 кг, составляет 1500₽. Брать магнитофон или нет? Емкость рюкзака составляет 1 кг. Поместится туда магнитофон? Нет, он слишком тяжел! Так как магнитофон не помещается в рюкзак, максимальная оценка для 1-кг рюкзака остается равной 1500₽.

То же самое происходит со следующими двумя клетками. Емкость этих рюкзаков составляет 2 и 3 кг соответственно. Максимальная стоимость для обеих ячеек была равна 1500₽.

Магнитофон все равно не помещается, так что оценка остается неизменной. А если емкость рюкзака увеличивается до 4 кг? Ага, магнитофон наконец-то войдет в рюкзак! Старая максимальная стоимость была равна 1500₽, но если вместо гитары положить магнитофон, она увеличится до 3000₽! Берем магнитофон.

Оценка только что обновилась! Имея рюкзак емкостью 4 кг, вы можете положить в него товары стоимостью по крайней мере 3000₽. Из таблицы видно, что оценка постепенно возрастает.

Ноутбук

А теперь проделаем то же для ноутбука! Ноутбук весит 3 кг, поэтому он не поместится в рюкзак с емкостью 1 или 2 кг. Оценка для первых двух ячеек остается на уровне 1500₽.

Для 3 кг старая оценка составляла 1500₽. Но теперь вы можете выбрать ноутбук, который стоит 2000₽. Следовательно, новая максимальная оценка равна 2000₽!

При 4 кг ситуация становится по-настоящему интересной. Это очень важная часть. В настоящее время оценка составляет 3000₽. В рюкзак можно положить ноутбук, но он стоит всего 2000₽. В соответствии с последней оценкой в свободном месте емкостью в 1 кг можно разместить гитару стоимостью 1500₽. Следовательно, настоящее сравнение выглядит так: 3000₽(магнитофон) или (2000₽(ноутбук) + 1500₽(гитара)). Зачем мы вычисляем максимальную стоимость для рюкзаков меньшей емкости? Надеюсь, теперь всё ясно! Если в рюкзаке остается свободное место, вы можете использовать ответы на эти подзадачи для определения того, чем заполнить это пространство. Вместо магнитофона лучше взять ноутбук + гитару за 3500₽. В завершающем состоянии таблица выглядит так:

Итак, мы получили ответ: максимальная стоимость товаров, которые поместятся в рюкзак, равна 3500₽ — для гитары и ноутбука. Стоимость каждой ячейки вычисляется по постоянной формуле, которая выглядит так: максимум из предыдущего элемента или стоимость текущего элемента плюс стоимость оставшегося пространства. Таким образом, в данной задаче объединяется решение двух подзадач для решения ещё одной большей задачи.

Вопросы по задаче

Ответим на вопросы которую могут возникнуть.

Что произойдет при добавлении элемента?

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

Это означает, что в рюкзак с емкостью 4 кг можно упаковать товары стоимостью до 3500₽. Добавим новую строку для смартфона.

Оказывается, в таблице появляется новый максимум! Заполним последнюю строку. Начнем с первой ячейки. Смартфон сам по себе помещается в рюкзак с емкостью 1 кг. Старый максимум был равен 1500₽, но Смартфон стоит 2000₽. Значит, берем Смартфон. В следующей далее можно разместить смартфон и гитару.

Для ячейки 3 ничего лучшего, чем снова взять смартфон вместе с гитарой, все равно не найдется. А вот в последней ячейке ситуация становится интересной. Текущий максимум до смартфона был равен 3500₽. Снова можно взять смартфон, и еще останется свободное место на 3 кг. Но эти 3 кг можно заполнить на 2000₽! 2000₽ от смартфона + 2000₽ из старой подзадачи: получается 4000₽. Новый максимум! Вот как выглядит новая завершающая таблица:

Вопрос: может ли значение в столбце уменьшиться? Ответ: нет. При каждой итерации сохраняется текущая оценка максимума. Эта оценка ни при каких условиях не может быть меньше предыдущей!

Что произойдет при изменении порядка строк?

Допустим, строки заполняются в другом порядке: магнитофон, ноутбук, гитара. Как будет выглядеть таблица? Изменится ли ответ? Заполните таблицу самостоятельно и убедитесь — ответ не изменился. Ответ не зависит от порядка строк.

Можно ли заполнять таблицу по столбцам, а не по строкам?

В данной задаче это ни на что не влияет, но в других задачах возможны изменения.

Что произойдет при добавлении меньшего элемента?

Допустим, вы можете выбрать ожерелье, которое весит 0,5 кг и стоит 1000₽. Изначально наша структура таблицы предполагает, что все веса являются целыми числами. Теперь вы решаете взять ожерелье. Остается еще 3,5 кг. Какую максимальную стоимость можно разместить в объеме 3,5 кг? Неизвестно! Мы вычисляли стоимость только для рюкзаков с емкостью 1, 2, 3 и 4 кг. Теперь придется определять стоимость для рюкзака на 3,5 кг. Из-за ожерелья приходится повысить точность представления весов, поэтому таблица должна измениться.

Можно ли взять часть предмета?

Допустим, вы наполняете рюкзак в продуктовом магазине. Вы можете взять мешки с чечевицей и рисом. Если весь мешок не помещается, его можно открыть и отсыпать столько, сколько унесете. В этом случае вы уже не действуете по принципу «все или ничего» — можно взять только часть предмета. Как решить такую задачу методом динамического программирования? Ответ: никак. В решении, полученном методом динамического программирования, вы либо берете предмет, либо не берете. Алгоритм не предусматривает возможности взять половину предмета. Однако проблема легко решается с помощью жадного алгоритма! Сначала вы берете самый ценный предмет — настолько бóльшую его часть, насколько возможно. Когда самый ценный предмет будет исчерпан, вы берете максимально возможную часть следующего по ценности предмета и т.д.

Оптимизация туристического маршрута

Представьте, что вы приехали в Лондон на выходные. У вас два дня, а мест, которые хочется посетить, слишком много. Побывать везде не получится, поэтому вы составляете список. Для каждой достопримечательности, которую вы захотите увидеть, вы указываете, сколько времени займет осмотр и насколько сильно вы хотите ее увидеть. Сможете ли вы построить оптимальный туристический маршрут на основании этого списка? Да это все та же задача о рюкзаке! Вместо ограниченной емкости рюкзака — ограниченное время. Вместо магнитофонов и ноутбуков — список мест, которые вы хотите посетить.

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

Вы изобразили ее правильно? Теперь заполните. Какие достопримечательности вы выберете? Ответ: аббатство, галерея, собор.

Взаимозависимые элементы

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

На их посещение потребуется много времени, потому что сначала придется приехать из Лондона в Париж. Переезд отнимает полдня. Если вы захотите посмотреть все 3 достопримечательности, осмотр займет 4,5 дня. Небольшая поправка: не обязательно приезжать в Париж ради каждой достопримечательности. После того как вы там окажетесь, каждый последующий элемент займет всего один день. Следовательно, потребуется 1 день на каждую достопримечательность + 1 день на переезды = 3,5 дня, а не 4,5.

Если вы положите Эйфелеву башню в свой «рюкзак», то Лувр станет «дешевле» — он займет всего 1 день вместо 1,5. Как смоделировать это обстоятельство в динамическом программировании? Ответ: никак. Динамическое программирование — мощный метод, способный решать подзадачи и использовать полученные ответы для решения большой задачи. Динамическое программирование работает только в том случае, если каждая подзадача автономна, то есть не зависит от других подзадач. Из этого следует, что учесть поездки в Париж в алгоритме динамического программирования не удастся.

Может ли оказаться, что решение требует более двух «подрюкзаков»?

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

Возможно ли, что при лучшем решении в рюкзаке остается пустое место?

Да. Представьте, что вы можете также положить в рюкзак бриллиант. Бриллиант очень крупный: он весит целых 3,5 кг и стоит 1 миллиард долларов — намного больше, чем любые другие предметы. Безусловно, нужно брать именно его! Но в рюкзаке остается еще пустое место на 0,5 кг, и в нем ничего не поместится.

Выводы

Мы рассмотрели одну задачу динамического программирования. Какие выводы из нее можно сделать?

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

Построить решение на базе динамического программирования бывает непросто. Несколько общих рекомендаций:

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

Ещё пример задачи

Допустим, вы открыли сайт dictionary.com. Пользователь вводит слово, а сайт возвращает определение. Но если пользователь ввел несуществующее слово, нужно предположить, какое слово имелось в виду. Алексей ищет определение «fish», но он случайно ввел «hish». Такого слова в словаре нет, но зато у вас есть список похожих слов. Какое слово он хотел ввести на самом деле: fish или например, vista?

Построение таблицы

Как должна выглядеть таблица для этой задачи? Вы должны ответить на следующие вопросы.

• Какие значения должны содержаться в ячейках?
• Как разбить эту задачу на подзадачи?
• Каков смысл осей таблицы?

В динамическом программировании вы пытаетесь максимизировать некоторую характеристику. В данном случае ищется самая длинная подстрока, общая в двух словах. Какую общую подстроку содержат hish и fish? А как насчет hish и vista? Именно это требуется вычислить. Как говорилось ранее, значения в ячейках обычно представляют ту характеристику, которую вы пытаетесь оптимизировать. Вероятно, в данном случае этой характеристикой будет число: длина самой длинной подстроки, общей для двух строк. Как разделить эту задачу на подзадачи? Например, можно заняться сравнением подстрок. Вместо того чтобы сравнивать hish и fish, можно сначала сравнить his и fis. Каждая ячейка будет содержать длину самой длинной подстроки, общей для двух подстрок. Такое решение также подсказывает, что строками и столбцами таблицы, вероятно, будут два слова. А значит, таблица будет выглядеть примерно так:

Заполнение таблицы

Сейчас вы уже достаточно хорошо представляете, как должна выглядеть таблица. По какой формуле заполняются ячейки таблицы? Мы можем немного упростить свою задачу, потому что уже знаем решение — у hish и fish имеется общая подстрока длины 3: ish. Однако этот факт ничего не говорит о том, какая формула должна использоваться. По правде говоря, простого способа вычислить формулу для данного случая не существует. Вам придется экспериментировать и искать работоспособное решение. Иногда алгоритм предоставляет не точный рецепт, а основу, на которую вы наращиваете свою идею. Попробуйте предложить решение этой задачи самостоятельно. Часть таблицы выглядит так:

Попытайтесь вывести формулу самостоятельно, прежде чем продолжить читать.

Решение

Итоговая версия таблицы выглядит так:

Формула заполнения ячеек:

1. Если буквы не совпадают, значение равно 0;
2. Если буквы совпадают, то значение равно значению ячейки наверху слева +1.

На Python эта формула реализуется так:

dp_table_hish = ["h", "i", "s", "h"]
dp_table_fish = ["f", "i", "s", "h"]
dp_table = [[0 for i in range(len(dp_table_hish))] for i in range(len(dp_table_fish))]
for i in range(0, len(dp_table_fish)):
    for j in range(0, len(dp_table_hish)):
        if dp_table_hish[j] == dp_table_fish[i]:  # Буквы совпадают
            dp_table[i][j] = dp_table[i-1][j-1] + 1
        else:  # Буквы не совпали
            dp_table[i][j] = 0
for i in dp_table:
    print(i)

Аналогично для строк hish и vista:

dp_table_hish = ["h", "i", "s", "h"]
dp_table_vista = ["v", "i", "s", "t", "a"]
dp_table = [[0 for i in range(len(dp_table_hish))] for i in range(len(dp_table_vista))]
for i in range(0, len(dp_table_vista)):
    for j in range(0, len(dp_table_hish)):
        if dp_table_hish[j] == dp_table_vista[i]:
            dp_table[i][j] = dp_table[i-1][j-1] + 1
        else:
            dp_table[i][j] = 0
for i in dp_table:
    print(i)

Таблица:

Важный момент: в этой задаче окончательное решение далеко не всегда находится в последней ячейке! В задаче о рюкзаке последняя ячейка всегда содержит окончательное решение. Но в задаче поиска самой длинной общей подстроки решение определяется самым большим числом в таблице — и это может быть не последняя, а какая-то другая ячейка. Вернемся к исходному вопросу: какая строка ближе к hish? У строк hish и fish есть общая подстрока длиной в три буквы. У hish и vista есть общая подстрока из двух букв. Скорее всего, Алексей хотел ввести строку fish.

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

Предположим, Алексей ввел строку fosh. Какое слово он имел в виду: fish или fort? Сравним строки, по способу выше, длину общей подстроки. Окажется, что длина подстрок одинакова: две буквы! Но fosh при этом ближе к fish. Мы сравниваем самую длинную общую подстроку, а на самом деле нужно сравнивать самую длинную общую подпоследовательность: количество букв в последовательности, общих для двух слов. Как вычислить самую длинную общую подпоследовательность? Ниже приведена частично заполненная таблица для fish и fosh:

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

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

Формула для заполнения каждой ячейки(для соседелй наверху слева):

1. Если буквы не совпадают, выбрать большее значение;
2. Если буквы совпадают, значение равно значению ячейки наверху слева +1 (как и в случае с самой длинной общей подстрокой).

Окончательные версии таблиц:

На Python это решение выглядит так:

dp_table_fosh = ["f", "o", "s", "h"]
dp_table_fish = ["f", "i", "s", "h"]
dp_table = [[0 for i in range(len(dp_table_fosh))] for i in range(len(dp_table_fish))]
for i in range(0, len(dp_table_fish)):
    for j in range(0, len(dp_table_fosh)):
        if dp_table_fosh[j] == dp_table_fish[i]:  # Буквы совпадают
            dp_table[i][j] = dp_table[i-1][j-1] + 1
        else:  # Буквы не совпали
            dp_table[i][j] = max(dp_table[i-1][j], dp_table[i][j-1])
for i in dp_table:
    print(i)

dp_table_fosh = ["f", "o", "s", "h"]
dp_table_fort = ["f", "o", "r", "t"]
dp_table = [[0 for i in range(len(dp_table_fosh))] for i in range(len(dp_table_fort))]
for i in range(0, len(dp_table_fort)):
    for j in range(0, len(dp_table_fosh)):
        if dp_table_fosh[j] == dp_table_fort[i]:  # Буквы совпадают
            dp_table[i][j] = dp_table[i-1][j-1] + 1
        else:  # Буквы не совпали
            dp_table[i][j] = max(dp_table[i-1][j], dp_table[i][j-1])
for i in dp_table:
    print(i)

Ещё примеры применения динамического программирования:

• Биологи используют самую длинную общую подпоследовательность для выявления сходства в цепях ДНК. По этой метрике можно судить о сходстве двух видов животных, двух заболеваний и т.д. Самая длинная общая подпоследовательность используется для поиска лекарства от рассеянного склероза.
• Вы когда-нибудь пользовались ключом diff (например, в команде git diff)? Этот ключ выводит информацию о различиях между двумя файлами, а для этого он использует динамическое программирование.
• Расстояние Левенштейна оценивает, насколько похожи две строки, а для его вычисления применяется динамическое программирование. Расстояние Левенштейна используется в самых разных областях, от проверки орфографии до выявления отправки пользователем данных, защищенных авторским правом.

Поздравляю — вы справились! Безусловно, это была одна из самых сложных тем в программировании. Ниже посмотрите и выполните упражнения, чтобы закрепить свои знания по теме.

В следующей статье речь идёт про алгоритм k ближайших соседей.

Попробуйте сами скопировать и запустить код в окне ниже с интерпретатором Python и повторите примеры из статьи чтобы самим увидеть и понять как всё это работает. Для этого в ячейке с кодом нажмите клавиши на клавиатуре Shift+Enter или запустите код через кнопку Run по значку ▶.