Пошаговый метод с использованием мемоизации и табуляции

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

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

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

С этого момента я буду называть динамическое программирование DP.

Общие шаги к решению проблем с использованием динамического программирования

Прежде всего, спросите себя: могу ли я решить эту проблему с помощью DP?

Предполагая, что проблема имеет необходимую структуру (подробно описанную ниже) для применения к ней методов DP, тогда:

  1. Определите состояние (я).
  2. Определите рекуррентные отношения.
  3. Перечислите все переходы между состояниями с соответствующими условиями.
  4. Определите базовый вариант (а).
  5. Реализуйте наивное рекурсивное решение.
  6. Оптимизируйте рекурсивное решение кеширования (мемоизации).
  7. Удалите накладные расходы на рекурсию с помощью восходящего подхода (табуляции).

Прежде чем мы начнем углубляться в пошаговые инструкции, пара деталей. Во-первых, эта статья представляет собой общий обзор некоторых тем, которые охватывает динамическое программирование. На формальном курсе DP вы получите более строгие объяснения. Во-вторых, здесь не помогает запоминание решений DP для конкретных задач; изучение подхода к поиску решения делает. Наконец, я не эксперт по DP. Эти советы я нашел полезными, будучи студентом информатики, когда учился решать задачи с помощью DP.

Могу ли я решить эту проблему с помощью DP?

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

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

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

  • Чтобы оценить оптимальную структуру, спросите себя, можете ли вы описать решение как рекуррентное отношение. Если это так, вы можете найти оптимальное решение проблемы в функции решений ее подзадач. Примером может служить знаменитая последовательность Фибоначчи. Число Фибоначчи - это сумма двух предыдущих чисел Фибоначчи, которая переводится в это рекуррентное соотношение: Fib (n) = Fib (n-1) + Fib (n-2).
  • Чтобы оценить перекрывающиеся подзадачи, спросите себя, обнаруживаете ли вы, что при решении проблемы ваша программа решает одну и ту же подзадачу несколько раз. Если да, то у вас есть частично совпадающие подзадачи.

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

Рекурсия и возврат с возвратом важны

Рекурсия - это фундаментальный метод при создании решений DP. В рекурсии у вас есть функция, которая вызывает себя до тех пор, пока не будет достигнут базовый вариант. Эти функции называются рекурсивными.

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

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

Приведенный выше код печатает все перестановки размера k данной коллекции. Обратите внимание, что рекурсивные вызовы происходят в строке 30. Перед этим мы изменяем список current_state, добавляя текущий элемент и отмечая его как используемый.

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

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

Найдите время, чтобы попрактиковаться в рекурсии и возврате. Практика - единственный способ освоить идею о том, что функции вызывают сами себя. Как только вы освоитесь с этим, вы начнете видеть рекурсивные решения повсюду. В этот момент у вас есть новые проблемы.

Подходы к ДП

Двумя основными подходами к динамическому программированию являются мемоизация (подход сверху вниз) и табуляция (подход снизу вверх).

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

Чтобы наивное рекурсивное решение могло применяться в качестве решения DP, оно должно быть оптимизировано для кэширования результатов вычисленных подзадач. В приведенном выше кратком определении DP упор делается на однократное решение более мелких экземпляров - с сильным акцентом на «только один раз».

Мемоизация

Мемоизация = Рекурсия + Кеширование

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

Обратите внимание, сколько раз мы решаем одну и ту же подзадачу. Например, Fib (3) вычисляется пять раз, и каждый вызов fib (3) рекурсивно вызывает еще два fib. Это десять вызовов функций, решающих одну и ту же подзадачу fib (3).

Теперь мы заговорили о DP! Вместо того чтобы решать одну и ту же проблему несколько раз, почему бы нам не решить ее только один раз и не сохранить в какой-либо структуре данных на случай, если она нам понадобится позже? Это мемоизация!

Этот подход является самым простым из двух представленных здесь подходов DP. Как только вы сможете получить рекурсивное решение проблемы, просто убедитесь, что вы кешируете решения для подзадач. Прежде чем делать рекурсивные вызовы для решения подзадачи, проверьте, была ли она уже решена. Обратите внимание, что здесь мы делаем обмен: для экономии времени на архивирование мы готовы отказаться от места в памяти для выделения решений всех вычисленных подзадач.

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

При кэшировании решенных подзадач вы можете использовать массив, если решение проблемы зависит только от одного состояния. Например, в приведенном выше коде fib решением подзадачи является «n-е число Фибоначчи». Мы можем использовать n как индекс в одномерном массиве, где его значение представляет решение подзадачи fib (n).

Иногда решение проблемы может зависеть от двух состояний. В этом случае вы можете кэшировать результаты, используя 2D-массив, где столбцы представляют одно состояние, а строки - другое. Например, в известной задаче о рюкзаке (которую мы рассмотрим позже) мы хотим оптимизировать общую ценность, учитывая ограничение максимального веса и список предметов. Подзадача о рюкзаке может выглядеть так: KS (W, i) → ( Максимальное значение), где мы интерпретируем это как: «Какое максимальное значение я могу получить с весом« W » и учитывая «i-й» пункт? » Поэтому, если мы хотим кэшировать это решение, нам нужно учитывать оба состояния, и это может быть выполнено с помощью 2D-массива.

Мемоизация - это здорово - у нас есть рекурсивное описание проблемы, и мы решаем перекрывающиеся подзадачи только один раз. Что ж, не все так хорошо. Мы все еще делаем кучу рекурсивных вызовов. Рекурсия требует больших затрат как на процессорное время, так и на объем памяти. Большинство рекурсивных функций потребляют память стека вызовов линейно с количеством рекурсивных вызовов, необходимых для выполнения задачи.

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

Рекурсивные функции всегда несут на себе вес потенциальных проблем, связанных с переполнением стека. Ниже представлена ​​команда Python для проверки предела глубины рекурсии. Если я попытаюсь использовать Python с рекурсией для решения проблемы, решение которой включает рекурсивную глубину более 1000 вызовов, я получу исключение переполнения стека. Это количество можно увеличить, но мы перейдем к темам, связанным с конкретным языком.

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

Табулирование

Табулирование направлено на решение тех же проблем, но полностью устраняет рекурсию. Удаление рекурсии означает, что нам не нужно беспокоиться о проблемах с переполнением стека, а также об общих накладных расходах рекурсивных функций. В подходе к DP (также известном как метод заполнения таблиц) мы решаем все подзадачи и сохраняем их результаты в матрице. эти результаты затем используются для решения более крупных задач, которые зависят от ранее вычисленных результатов. По этой причине метод табуляции также известен как восходящий подход. Это как начать с нижнего уровня вашего рекурсивного дерева и двигаться вверх.

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

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

Мы много говорили о состояниях, но у нас до сих пор нет формального определения того, что мы подразумеваем под состояниями в нашем контексте DP. Под состояниями я понимаю параметры, которые влияют на результат рекурсивного вызова. Состояния - это то, что отличает один звонок от другого и позволяет нам изучить различные варианты и получить оптимальный результат. В конце статьи мы познакомимся с определением состояний.

Поскольку табулирование предлагает восходящий подход, мы должны сначала решить все подзадачи, от которых может зависеть более крупная проблема. Если мы не решим меньшую проблему, мы не сможем перейти к решению большей. В табулировании мы используем один цикл for для каждого состояния проблемы. Но с чего мне начать? Где мне это закончить? Чтобы ответить на этот вопрос, давайте исследуем следующее рекуррентное соотношение.

Допустим, у нас есть функция, которая решает некоторую проблему оптимизации - назовем ее оптимальной или для краткости OP. Предположим, что природа проблемы заставляет OP (n) зависеть от OP (n-1), поэтому OP (n) = OP (n-1).

Это отношение повторения говорит вам, что вы не можете знать, что такое OP (n), если вы не знаете, что такое OP (n-1). Это означает, что нам нужно начать с наименьшего значения n, скажем 0, и решить каждую подзадачу полностью до n. В этом весь трюк: если ваше отношение повторения показывает, что ваши состояния уменьшаются, тогда ваши циклы должны быть увеличены, чтобы вы вычисляли каждую подзадачу, от которой зависят более крупные проблемы. Помните снизу вверх.

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

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

Мы начнем применять наш систематический подход к DP на знаменитой задаче о рюкзаке 0/1. Наша задача заключается в следующем: нам дается сумка с дискретным количеством предметов, где каждая единица имеет ценность и вес. Мы хотим брать предметы так, чтобы приносить максимальную пользу. Но вот условие: мы можем носить с собой только ограниченное количество груза. Таким образом, задано n элементов со значениями [v0, v2, v3,…, v (n-1)] и весами [w0, w1, w2,… w (n-1)] соответственно, а также пределом веса (W ). Какую максимальную ценность мы можем забрать домой?

Следует ли мне использовать DP для решения этой проблемы?

Ты заметил? Задача просит нас максимизировать результат некоторой задачи на основе условий. Я уже чувствую запах оптимизации. Но есть ли у него оптимальная структура?

Да, решение проблемы, сколько ценности я могу получить с элементами [0, n] и их соответствующими значениями [v0,…, v (n-1)] и весами [w0,…, w (n-1) ], а общий предел веса W можно разбить на максимальное значение, которое я могу получить, либо добавив n-й элемент и оценив оптимальный результат, который я получаю с оставшимся весом и оставшимися элементами, либо не добавляя его и изучив оптимальный результат. Получаю с таким же весом и остальные предметы.

Чего ждать? Я знаю, много слов, но математика объяснит это лучше, когда мы определим рекуррентное отношение и переходы состояний.

Шаг 1. Определите состояния

Какие параметры будут влиять на результат наших рекурсивных вызовов? В этой задаче у нас есть два фактора, которые влияют на наши результаты: предел веса и предмет, который мы рассматриваем, добавлять в сумку или нет. Состояние рекурсивного вызова будет определяться его доступным весом W и индексом рассматриваемого элемента в момент «i».

Шаги 2 и 3: Определите рекуррентное отношение и изучите переходы состояний.

Функция затрат, которую мы пытаемся оптимизировать, будет KS (W, i), которая должна дать нам максимальный вес, который мы можем получить с элементами [0, i] и остаточным весом W.

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

KS (W, i) = MAX (val [i] + KS (W- w [i], i-1), KS (W, i-1)) i f W ≥ w [ я]

KS (W, i) = KS (W, i-1) иначе

Шаг 4. Определите базовые варианты

Когда нам следует перестать рассматривать варианты? Одно условие остановки будет, если у нас больше нет места (W == 0), другое будет, если у нас больше нет элементов для рассмотрения (i == -1). Оба базовых случая не представляют для нас ценности, поэтому:

вернуть 0 , если W == 0 или i == -1

Шаг 5. Реализуйте наивное рекурсивное решение

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

Шаг 6. Оптимизируйте рекурсивное решение для кеширования (мемоизация)

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

Шаг 7. Удалите накладные расходы на рекурсию с помощью восходящего подхода (табулирование)

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

Вместо того:

KS (W, i) = MAX (val [i] + KS (W- w [i], i-1), KS (W, i-1)), если W ≥ w [i]

KS (W, i) = KS (W, i-1) иначе

у нас есть:

KS [W] [i] = MAX (val [i] + KS [W-w [i]] [i-1], KS [W] [i-1]), если W ≥ w [i]

KS [W] [i] = KS [W] [i-1] иначе

Мы изменили наше рекуррентное отношение к обозначениям матриц, так как теперь мы заполняем матрицу.

Помните о двух важных моментах при составлении таблиц:

  • Один цикл for для каждого состояния.
  • Если ваши состояния уменьшаются в цене, тогда ваши петли увеличиваются в цене, и наоборот.

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

Обратите внимание на то, что изменилось:

  • Наша функция больше не рекурсивная. Нам не нужно передавать измененные состояния. Теперь KS получает ограничение по весу и коллекцию элементов и возвращает оптимальный результат. В этом случае можно сказать, что KS теперь чисто функциональный.
  • В нашем подходе к табулированию базовые случаи жестко запрограммированы в таблице. Иногда это требует от нас добавления фиктивных строк / столбцов. Если вы видите наш базовый случай для i, это было i == - 1. Однако на матрице у нас не может быть отрицательного индекса. Чтобы решить эту проблему, мы выполняем сдвиг индекса. То, что раньше было (i == - 1), теперь будет (i == 0), поэтому мы будем хранить значения базового случая.
  • Давайте потратим время на дальнейший анализ смещения индекса, потому что это очень распространенная практика. Наше рекуррентное отношение показывает:

KS [W] [i] = MAX (val [i] + KS [W-w [i]] [i-1], KS [W] [i-1]), если W ≥ w [i]

KS [W] [i] = KS [W] [i-1] иначе

Обратите внимание на [i-1]. Если мы начнем наш цикл с i = 0, это приведет к исключению за пределами диапазона. Но мы сказали, что i = 0 и W = 0 - наши базовые случаи. Нет причин для их вычисления, поэтому давайте начнем с 1. Однако нам нужно изменить то, как мы ссылаемся на val [i] и w [i], поскольку теперь (i = 1) должен отображаться на первый элемент (который находится в позиции 0 ). Мы просто балансируем эффект смещения индекса, используя (i-1) всякий раз, когда мы хотим проиндексировать элемент в нашей входной коллекции.

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

Самое важное, что нужно помнить

Я знаю, что информации было много. Попробуем выделить некоторые из наиболее важных деталей:

  • DP - это метод решения проблем, который направлен на решение сложных проблем, сначала решая более мелкие экземпляры этих проблем ровно один раз.
  • Хорошими целями DP являются проблемы, имеющие оптимальную структуру и перекрывающиеся подзадачи.
  • Двумя основными подходами к динамическому программированию являются мемоизация (нисходящий подход) и табуляция (восходящий подход).
  • Мемоизация = Рекурсия + Кеширование
  • Рекурсия стоит дорого как с точки зрения процессорного времени, так и с точки зрения объема памяти.
  • При табличном подходе к DP мы решаем все подзадачи и сохраняем их результаты в матрице. затем мы продолжаем решать более крупные проблемы, которые зависят от этих вычисленных подзадач.
  • Практика, практика, практика.

Спасибо за прочтение.