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

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

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

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

Поехали!

Парадигмы разработки алгоритмов

Термин «динамическое программирование» (сокращенно «DP») имеет репутацию более устрашающего, чем то, чем он является на самом деле . Я думаю, что во многом это связано с его названием, которое - по крайней мере, для меня - звучит действительно сложно. Но к названию мы вернемся чуть позже. Давайте начнем с определения, чтобы попытаться понять, что вообще означает «динамическое программирование».

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

Но как именно динамическое программирование или динамическая оптимизация связаны с оптимизацией алгоритма? Другими словами, что делает эта форма разработки алгоритма для оптимизации алгоритма?

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

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

В этой серии статей мы уже видели два подхода к разработке алгоритмов. Один из них мы знаем по названию: алгоритм разделяй и властвуй. Мы узнали о разделяй и властвуй еще тогда, когда впервые познакомились с алгоритмом сортировки слиянием. Напомним, что алгоритм разделяй и властвуй делит проблему на более простые версии, а затем применяет то же решение, которое он использует для меньших подзадач, к самой большой проблеме. Если мы вспомним, когда мы узнали о сортировке слиянием, мы вспомним, как алгоритм объединил ответы на свои подзадачи и использовал рекурсию для слияния элементов вместе при их сортировке. Это также характерно для алгоритмов d & c.

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

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

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

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

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

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

Если мы сравним эти три формы разработки алгоритмов друг с другом, мы начнем видеть, что есть некоторые очевидные сходства (а также некоторые очевидные различия) между алгоритмами DP и их двумя аналогами.

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

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

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

Итак, как динамическое программирование соотносится с парадигмой жадных алгоритмов?

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

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

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

Более простой способ сравнить алгоритмы динамического программирования с жадными алгоритмами:

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

Это подводит нас к важному вопросу: как же алгоритмы динамического программирования так интенсивно выполняют работу по поиску? Как именно алгоритмы DP отслеживают все перекрывающиеся подзадачи?

Пришло время заняться расследованием.

Не забывайте помнить

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

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

Давайте проиллюстрируем, что я имею в виду, на простом примере. Представьте, что нам нужно решить проблему 5 + 5 + 5 + 5. Как бы мы это решили? Ну, мы бы просто сложили их, не так ли? Мы знаем, что 5 + 5 + 5 + 5 = 20. Выполнено.

Но тогда, что, если мы просто добавим еще один 5 в конце этого? 5 + 5 + 5 + 5 + 5 = ?. Мысленно, что бы мы сделали? Будем ли мы добавлять каждую пятерку, одну за другой, снова и снова?

Ни за что! Мы, наверное, просто подумали бы про себя: «О, я только что подсчитал. Я знаю, что раньше было 20, а теперь еще 5, так что ответ должен быть 25! ». Мы вспомнили решение проблемы, которое мы ранее решали раньше, и использовали его снова, когда нам нужно было решить проблема, которая построена на нем.

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

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

Напомним, что последовательность Фибоначчи, которая тесно связана с золотым сечением, представляет собой последовательность чисел, которая начинается с 0 и 1. Чтобы получить любое число в последовательности Фибоначчи, нам нужно найти и просуммировать два числа, предшествующих этому числу.

Например, чтобы найти число после 0, 1, 2, 3, 5, мы суммируем 3 + 5 и знаем, что следующим числом будет 8. Более абстрактный способ определения формулы для поиска числа в последовательности Фибоначчи: F[n] = F[n-1] + F[n-2], где n представляет индекс в массиве чисел Фибоначчи. Основываясь на этой формуле, мы также знаем, что Фибоначчи можно решить рекурсивно, поскольку мы неизбежно столкнемся с необходимостью использовать рекурсию для нахождения предыдущего числа в последовательности Фибоначчи, если мы его еще не знаем.

Однако, глядя на пример рекурсивного «дерева» значений, проиллюстрированный выше, мы заметим, что повторяемся сами. При рекурсивном решении для числа Фибоначчи F[6] или седьмого числа Фибоначчи нам пришлось вычислить F[5] и F[4]. Но затем, чтобы вычислить F[5], нам снова нужно найти F[4], еще раз!

Вот абстрагированный пример той же проблемы рекурсивного повторения.

На самом деле не имеет значения, что n при решении для F[n]; если мы будем использовать рекурсию, нам придется пересчитывать части последовательности Фибоначчи более одного раза. Например, в приведенном выше дереве мы дважды вычисляем F[n-3] и дважды вычисляем F[n-2]. Это кажется очень неэффективным, и мы должны добиться большего.

Хорошая новость: мы можем! Конечно, используя динамическое программирование.

Мы знаем, что динамическое программирование позволяет нам запоминать решения проблем, которые мы видели и решали раньше. Пример Фибоначчи является ярким примером того, когда мы хотели бы запомнить решения для чисел Фибоначчи, для которых мы уже решили! Метод запоминания алгоритмом DP проблем, которые он уже решил, известен как мемоизация.

Запоминание во многом похоже на создание заметок в блокноте: когда мы сталкиваемся с проблемой, которая кажется важной (и даже если это не так), мы записываем ответ на нее и записываем его, запоминая его. Как и в случае с 5 + 5 + 5 + 5 + 5 проблемой, описанной ранее, если мы столкнемся с той же проблемой позже, нам не нужно будет проводить в уме математические вычисления, заново вычисляя ее. Мы уже решили 80% проблемы, потому что мы можем повторно использовать наше предыдущее решение и просто развивать его, что намного проще, чем решать его с нуля!

Мемоизация позволяет нам выполнить вычисление только один раз, а затем повторно использовать его позже без необходимости повторного вычисления.

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

Теперь, при решении для F[n], мы сначала вычисляем F[n-1]. В рамках рекурсивного поиска решения для F[n-1] мы в конечном итоге решаем для F[n-2] и F[n-3]. Каждый раз, когда мы решаем их впервые, мы запоминаем их решения.

Затем нам нужно решить вторую часть выяснения F[n]: F[n-2]. Когда мы перейдем к вычислению значения F[n-2], мы проверим, решили ли мы уже, прежде чем на самом деле это выяснять. Когда мы видим это во второй раз, мы знаем, что мы уже решили для него, и мы знаем, что у нас уже есть его значение, поскольку мы запомнили его, когда запомнили его решение.

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

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

Давайте ответим на этот вопрос, рассмотрев проблему сложности пространства и времени.

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

Без мемоизации сложность выполнения алгоритма для поиска значения nth в последовательности Фибоначчи… не выглядит привлекательной.

Для любого числа Фибоначчи с индексом n, которое нам нужно найти, нам нужно рекурсивно вызвать тот же алгоритм Фибоначчи для значений n-1 и n-2. Мы уже знаем кое-что из этой математики. Мы знаем, что две величины имеют золотое сечение, если соотношение между двумя величинами такое же, как отношение двух суммированных элементов по сравнению с большей из двух величин. Комбинированное время выполнения этих двух внутренних алгоритмов - время T(n-1) и время T(n-2), достигающее значения phi (φ или ϕ), увеличенное до сила всего, что n.

Существует также некоторое постоянное время O(1), которое включает суммирование чисел и возврат правильного значения, но это незначительно. Важная вещь - рев красной тревоги, которая, мы надеемся, должна сработать в наших головах - это то, что здесь задействован экспонент! Золотое сечение для n степени нашего времени работы не очень хорошо. Фактически, оно дает экспоненциальное время работы, или O(2^n)! Мы всегда хотим этого избежать.

Итак, без мемоизации рекурсивная форма Фибоначчи не слишком хороша.

Но как насчет с мемоизацией? Что ж, хорошая вещь в «запоминаемых», запомненных значениях заключается в том, что они почти не тратят времени на поиск в словаре / хэше / массиве, где мы, вероятно, будем хранить. Другими словами, реальная стоимость поиска мемоизированное значение стоит нам O(1), константа времени.

Однако в первый раз, когда мы сталкиваемся с подзадачей, нам все равно нужно поработать над ее решением, прежде чем мы сможем запоминать ее. Немемоизированные вызовы алгоритма Фибоначчи будут зависеть от того, что такое n. Если мы ищем 10-й элемент, нам потребуется значительно меньше вызовов для вычисления последовательности Фибоначчи, чем если бы мы искали 100-й элемент. Таким образом, работа по первому запуску алгоритма Фибоначчи для каждого немомоизированного элемента занимает линейно O(n) времени.

Подобно немемоизированной версии этого алгоритма, здесь также есть некоторое постоянное время O(1), которое включает суммирование чисел и возврат правильного значения, но это незначительно. Это приводит к O(n) + O(1) + O(1) времени выполнения, которое по-прежнему составляет линейное, O(n) время.

Линейное время намного лучше экспоненциального! Неплохо для небольшого алгоритма динамического программирования, а?

Так как же мемоизированная версия Фибоначчи сравнивается с немемоизированной версией, когда дело касается космоса?

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

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

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

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

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

В случае решения Фибоначчи метод «снизу вверх» включал бы нас решение для первых элементов в Фибоначчи, а затем прокладывание пути вверх, чтобы наконец прийти к решению для любого nth значения, которое мы пытались определить с самого начала. Мы бы по-прежнему использовали мемоизацию, чтобы сохранять ценности - мы бы просто решали проблему с «противоположной стороны», так сказать. Подход снизу вверх, вероятно, был более удобным для большинства из нас, когда мы впервые узнали о Фибоначчи. Если подумать, мы все начинаем считать Фибоначчи с 0, затем 1, затем 1, затем 2, пока не дойдем до искомого числа.

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

Динамическое программирование, даже со всеми его особенностями, не так уж и страшно, если разбить его на движущиеся части!

Я упоминал ранее, что название «динамическое программирование» пугает больше, чем есть на самом деле. За именем DP скрывается забавный факт: на самом деле оно ничего не означает.

Динамическое программирование было изобретено в 1940-х Ричардом Беллманом, ученым-компьютерщиком, который в то время работал над математическими исследованиями в компании RAND. Как оказалось, RAND использовался в ВВС США, а это означало, что им часто приходилось подчиняться министру обороны, которого звали Чарльз Эрвин Уилсон.

В автобиографии Беллмана Глаз урагана: автобиография он объясняет, как он придумал название для этой парадигмы разработки алгоритмов:

[Уилсон] на самом деле испытывал патологический страх и ненависть к слову «исследование». Я не использую этот термин легкомысленно; Я точно использую. Его лицо покрылось кровью, он покраснел и стал бы жестоким, если бы люди использовали термин «исследование» в его присутствии ... Следовательно, я чувствовал, что должен что-то сделать, чтобы защитить Уилсона и ВВС от того факта, что я действительно занимаюсь математикой внутри корпорации RAND. Какое название, какое имя я мог бы выбрать? В первую очередь меня интересовало планирование, принятие решений, мышление. Но планирование - не лучшее слово по разным причинам. Поэтому я решил использовать слово «программирование». Я хотел донести идею, что это было динамично, это было многоэтапно, это было изменяющимся во времени. Я подумал, давай убьем двух зайцев одним выстрелом. Возьмем слово, имеющее абсолютно точное значение, а именно динамический в классическом физическом смысле. У него также есть очень интересное свойство прилагательного, и что нельзя использовать слово динамический в уничижительном смысле. Попробуйте придумать какую-нибудь комбинацию, которая, возможно, придаст этому уничижительное значение. Это невозможно. Таким образом, я подумал, что динамическое программирование - хорошее имя. Против этого не мог возражать даже конгрессмен. Так что я использовал его как зонтик для своей деятельности.

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

Ресурсы

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

  1. Динамическое программирование - Фибоначчи, кратчайшие пути, MITOpenCourseWare
  2. Алгоритмы: мемоизация и динамическое программирование, HackerRank
  3. Введение в динамическое программирование, Hacker Earth
  4. Динамическое программирование, Интерактивный Python
  5. Динамическое программирование (свойство перекрывающихся подзадач), GeeksForGeeks