8 262 
Оставить комментарий
Сохранить статью:
В статье рассказывается:
- Что такое динамическое программирование
- Преимущества и недостатки динамического программирования
- Пример решения задачи при помощи динамического программирования
- Роль таблиц в динамическом программировании
- Использование динамического программирования в реальной жизни
-
Пройди тест и узнай, какая сфера тебе подходит:
айти, дизайн или маркетинг.Бесплатно от Geekbrains
Динамическое программирование – это раздел математики, который занимается методами решения многошаговых задач по оптимизации. Данный инструмент вычислений сегодня буквально незаменим во многих сферах человеческой деятельности.
Особенно он важен, когда требуется срочная оценка данных, поступивших из разных источников и значительно отличающихся как по объему, так и характеру. В подобных ситуациях динамическое программирование сложно чем-либо заменить.
Что такое динамическое программирование
Своим возникновением и утверждением в научной среде термин «динамическое программирование» обязан Ричарду Беллману, который впервые применил его в 1940 году для задач, решаемых поэтапно с использованием результатов каждого вычисления на следующем шаге. Впоследствии Беллман усовершенствовал это понятие, предложив общепринятую в настоящее время формулировку.
Как следствие, Беллману понадобилось немало времени, чтобы выбрать подходящее название. Вместо слова «планирование», которые вызывало ассоциации с тем, что в это время происходило в Советском Союзе, он предложил вариант «программирование».
А слово «динамическое» оказалось удачным не только потому, что передавало суть методики, но и потому, что оно было понятным и его сложно было подменить чем-либо другим. Для Беллмана было важно, чтобы его термин нельзя было неправильно интерпретировать, исказить смысл. Отсюда и возникло понятие «динамическое программирование».
Далее рассмотрим саму суть динамического программирования. Оно заключается в том, что при решении задачи та разбивается на несколько более мелких подзадач, непосредственно зависящих друг от друга.
«Более мелкие подзадачи» – это то же самое, что «более простые». Другими словами, это задачи, входные данные для которых имеют меньший размер. Входными данными могут быть число, массив, совокупность настраиваемых параметров и т.д. Как пример, можно привести последовательность чисел Фибоначчи, N-й член которой обозначается как Ф(N).
Чтобы найти пятое число Фибоначчи Ф(5), сначала нужно получить третье Ф(3) и четвертое Ф(4) числа в этой последовательности, то есть необходимо решить те самые мелкие подзадачи.
входят в ТОП-30 с доходом
от 210 000 ₽/мес
Скачивайте и используйте уже сегодня:
Топ-30 самых востребованных и высокооплачиваемых профессий 2023
Поможет разобраться в актуальной ситуации на рынке труда
Подборка 50+ бесплатных нейросетей для упрощения работы и увеличения заработка
Только проверенные нейросети с доступом из России и свободным использованием
ТОП-100 площадок для поиска работы от GeekBrains
Список проверенных ресурсов реальных вакансий с доходом от 210 000 ₽
В основе динамического программирования лежит выполнение следующих условий:
- Отдельные элементы должны находиться в зависимости друг от друга. Это может следовать непосредственно из условий, что наиболее характерно для задач на числовые последовательности. Если такую зависимость не удается проследить, можно попробовать найти некоторую числовую последовательность наподобие рассмотренных чисел Фибоначчи, рассчитав значения первых ее членов.
- Должны быть определены начальные значения элементов. Для этого необходимо последовательно разделять функцию на подзадачи до тех пор, пока не будут получены уже известные значения, либо функция не сведется к элементарной.
Преимущества и недостатки динамического программирования
Часто бывает так, что решить поставленную задачу быстро не получается, для этого нужно последовательно перебирать все возможные варианты. Такой подход имеет серьезный недостаток – он требует много времени.
Допустим, что хакеру нужно взломать пароль, для чего он поочередно перебирает различные комбинации символов. Если в пароле могут быть 10 цифр, по 26 больших и маленьких букв, а также 32 специальных символа, то существует 94 варианта одного символа.
То есть, если пароль состоит из одного символа, он имеет 94 возможных значения, если из двух символов, то на каждый из них приходится 24 варианта, и всего нужно 94*94 = 8836 комбинаций. Для десятизначного пароля нужно провести уже 94^10 проверок.
В наиболее общем сценарии для взлома пароля из N символов нужно перебрать 94^N комбинаций. Особенность такого подхода в том, что число попыток растет по экспоненте, то есть при увеличении длины на один знак возможных вариантов становится в 94 раза больше. Можно подумать, что взлом пароля – это условный пример, но в реальности задачи, для решения которых необходимо перебрать все варианты, встречаются повсеместно.
При возрастании по экспоненте временные затраты становятся огромными. Даже если на один элемент приходится всего несколько возможных значений, никто не станет заниматься подобными вычислениями – когда в задаче сто элементов, ее решение может занять миллиарды лет. А в действительности число элементов в задаче может быть намного больше. Именно в таких случаях возникает необходимость в динамическом программировании.
Данный метод обладает рядом преимуществ:
- Скорость. Благодаря этому динамическое программирование является эффективным. Сложнейшие задачи можно решить за максимально короткие сроки – достаточно лишь заполнить каждую ячейку таблицы.
- Универсальность. Для решения задачи любой сложности существует определенный набор правил, которые не предусматривают никаких исключений и требуют проведения минимальных расчетов.
- Точность. В процессе динамического программирования охватываются все возможные варианты событий. Это позволяет найти наиболее оптимальное решение без каких-либо погрешностей и неоднозначностей.
При этом у него есть и слабые стороны:
- Память. Перед тем как запустить алгоритм динамического программирования, нужно построить и заполнить таблицы, которые занимают определенный объем памяти. Возможно, что для решения задачи понадобится строить и размещать в памяти большие таблицы или множество различных таблиц.
- Когнитивная нагрузка. Безусловно, многих привлекает использование компактной системы правил для решения сложных задач. Но в то же время необходимо иметь соответствующий образ мышления, чтобы составлять подобные системы или хотя бы разбираться в них. Из-за этого динамическое программирование зачастую не пользуется большой популярностью.
Пример решения задачи при помощи динамического программирования
Теперь попробуем решить задачу с помощью динамического программирования. Допустим, что нам требуется вычислить сумму n чисел: 1 +2 +3 + … + n
Вначале данная задача может показаться непростой из-за того, что для получения ответа нужно одновременно сложить большое количество чисел. Однако можно решить ее методом динамического программирования, то есть путем разделения на подзадачи.
Динамическое программирование всегда начинается с определения начальных условий. В нашем примере достаточно взять сумму одного первого элемента, равную этому элементу: F(1) = 1
Для нахождения суммы двух элементов надо взять полученную сумму первого элемента и прибавить к ней второй элемент: F(2) = F(1) + 2 = 1 + 2 +3
Для трех элементов сумма равна F(3) = F(2) +3 = 6
на обучение «Инженер-программист» до 28 апреля
Отсюда делаем вывод, что искомая функция имеет вид F(n) = F(n-1) + n
Роль таблиц в динамическом программировании
Принцип динамического программирования состоит в том, что с решениями подзадач необходимо правильно обращаться, а если конкретно – одна и та же подзадача не должна решаться дважды. Все промежуточные решения нужно сохранять в отдельной базе данных. На практике для этих целей чаще всего используется таблица.
В простейшем варианте эта таблица будет представлять собой обычный массив, состоящий из одной строки. Такое динамическое программирование называется одномерным, оно занимает О(n) памяти. Например, в процессе вычисления чисел Фибоначчи лучше всего сохранять результаты отдельных вычислений в обычном массиве. Стандартный алгоритм с использованием рекурсии крайне неудобен – каждый раз приходится заново проводить вычисления, которые уже были сделаны на предыдущих этапах.
В большинстве случаев используется двумерное динамическое программирование, при котором таблицы состоят из строчек и столбиков точно также, как в Excel. Объем потребляемой памяти для таблицы из n строк и n столбцов равен О(n*n) = О(n*2). То есть, таблица в виде квадрата из 10 строк и 10 столбцов состоит из 100 ячеек.
Можно встретить и такие задачи динамического программирования, которые решаются с помощью трехмерных таблиц. Но это скорее исключение, поскольку для многих такие решения связаны с лишними затратами. Если квадратная таблица может занимать несколько мегабайт памяти, то для хранения аналогичной таблицы в форме куба потребуются гигабайты.
ТОП-100 площадок для поиска работы от GeekBrains
20 профессий 2023 года, с доходом от 150 000 рублей
Чек-лист «Как успешно пройти собеседование»
Кроме исходных данных, для динамического решения задачи требуется следующее:
- Таблица для сохранения итогов промежуточных вычислений. При завершении работы среди них будет выбран окончательный результат.
- Набор правил, по которым заносятся данные в пустые ячейки таблицы, исходя из значений в уже заполненных ячейках. Общих рекомендаций здесь нет, для каждой задачи правила составляются индивидуально.
- Правило, по которому из заполненной таблицы получается готовый ответ.
Использование динамического программирования в реальной жизни
Динамическое программирование нельзя назвать сугубо теоретической концепцией, используемой только учеными. Оно находит практическое применение во многих сферах деятельности, таких как прикладная информатика, машиностроение, финансовое прогнозирование. Рассмотрим некоторые типичные примеры динамического программирования.
Довольно часто встречается задача построить маршрут через несколько заданных точек, например, в приложениях для онлайн-карт или вызова такси.
Предположим, у вас была вечеринка, и вам нужно определиться, в каком порядке развозить друзей на такси, и какой маршрут выбрать. Решение этой задачи сводится к динамическому программированию, в теории которого есть похожий пример с коммивояжером.
Аналогичная ситуация имеет место в компьютерных сетях, когда требуется доставить пакет данных по нескольким адресам. Здесь также необходимо рассчитать маршрут и определить последовательность доставки данных получателям.
Использование динамического программирования хорошо демонстрирует утилита diff, которая занимается поиском похожих фрагментов в двух строках. Данный алгоритм основан на известной задаче динамического программирования по поиску наибольшей общей последовательности.
Не меньший интерес вызывает применение динамического программирования для сжатия изображений. Как известно, суть данного процесса в том, что размер файла уменьшается за счет выделения схожих участков изображения. Это значит, что при сжатии содержимое картинки изменяется, но в то же время ее внешний вид должен оставаться неизменным – добиться этого не так уж и просто.
Наконец, запомните, что нет смысла постоянно искать новые способы, как применить динамическое программирование. Вполне достаточно того, что вы имеете представление о таком подходе и знаете, в каких жизненных ситуациях он может оказаться полезным.
Разберем 11 самых важных жизненных вопросов
Только до 
Эксклюзивные лекции по основам программирования
