Современные профессии Онлайн-интенсив Только до 3.10
Выберите профессию будущего в ИТ, дизайне, маркетинге и управлении проектами
Кнопка закрыть топ-бар
ГлавнаяБлогДинамическое программирование: его преимущества и недостатки
Динамическое программирование
1 458
Время чтения: 14 минут

Динамическое программирование: его преимущества и недостатки

1 458
Время чтения: 14 минут
Сохранить статью:
Сохранить статью:
В статье рассказывается:   
  1. Что такое динамическое программирование
  2. Преимущества и недостатки динамического программирования
  3. Пример решения задачи при помощи динамического программирования
  4. Роль таблиц в динамическом программировании
  5. Использование динамического программирования в реальной жизни

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

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

Что такое динамическое программирование

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

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

Как следствие, Беллману понадобилось немало времени, чтобы выбрать подходящее название. Вместо слова «планирование», которые вызывало ассоциации с тем, что в это время происходило в Советском Союзе, он предложил вариант «программирование».

А слово «динамическое» оказалось удачным не только потому, что передавало суть методики, но и потому, что оно было понятным и его сложно было подменить чем-либо другим. Для Беллмана было важно, чтобы его термин нельзя было неправильно интерпретировать, исказить смысл. Отсюда и возникло понятие «динамическое программирование».

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

Что такое динамическое программирование
Что такое динамическое программирование

«Более мелкие подзадачи» – это то же самое, что «более простые». Другими словами, это задачи, входные данные для которых имеют меньший размер. Входными данными могут быть число, массив, совокупность настраиваемых параметров и т.д. Как пример, можно привести последовательность чисел Фибоначчи, N-й член которой обозначается как Ф(N).

Чтобы найти пятое число Фибоначчи Ф(5), сначала нужно получить третье Ф(3) и четвертое Ф(4) числа в этой последовательности, то есть необходимо решить те самые мелкие подзадачи.

В основе динамического программирования лежит выполнение следующих условий:

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

Преимущества и недостатки динамического программирования

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

Допустим, что хакеру нужно взломать пароль, для чего он поочередно перебирает различные комбинации символов. Если в пароле могут быть 10 цифр, по 26 больших и маленьких букв, а также 32 специальных символа, то существует 94 варианта одного символа.

То есть, если пароль состоит из одного символа, он имеет 94 возможных значения, если из двух символов, то на каждый из них приходится 24 варианта, и всего нужно 94*94 = 8836 комбинаций. Для десятизначного пароля нужно провести уже 94^10 проверок.

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

Преимущества и недостатки динамического программирования
Преимущества и недостатки динамического программирования

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

Данный метод обладает рядом преимуществ:

  • Скорость. Благодаря этому динамическое программирование является эффективным. Сложнейшие задачи можно решить за максимально короткие сроки – достаточно лишь заполнить каждую ячейку таблицы.
  • Универсальность. Для решения задачи любой сложности существует определенный набор правил, которые не предусматривают никаких исключений и требуют проведения минимальных расчетов.
  • Точность. В процессе динамического программирования охватываются все возможные варианты событий. Это позволяет найти наиболее оптимальное решение без каких-либо погрешностей и неоднозначностей.
ТОП-30 IT-профессий
2022 года с доходом
от 200 000 ₽
Команда GeekBrains совместно с международными специалистами по развитию карьеры подготовили материалы, которые помогут вам начать путь к профессии мечты.
Подборка содержит только самые востребованные и высокооплачиваемые специальности и направления в IT-сфере. 86% наших учеников с помощью данных материалов определились с карьерной целью на ближайшее будущее!

Скачивайте и используйте уже сегодня:

Александр Сагун
Александр Сагун
Исполнительный
директор Geekbrains
pdf иконка

Топ-30 самых востребованных и высокооплачиваемых профессий 2022

Поможет разобраться в актуальной ситуации на рынке труда

doc иконка

Подборка 50+ ресурсов об IT-сфере

Только лучшие телеграм-каналы, каналы Youtube, подкасты, форумы и многое другое для того, чтобы узнавать новое про IT

pdf иконка

ТОП 50+ сервисов и приложений от Geekbrains

Безопасные и надежные программы для работы в наши дни

pdf 3,7mb
doc 1,7mb
Уже скачали 14873 pdf иконка

При этом у него есть и слабые стороны:

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

Пример решения задачи при помощи динамического программирования

Теперь попробуем решить задачу с помощью динамического программирования. Допустим, что нам требуется вычислить сумму n чисел: 1 +2 +3 + … + n

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

Пример решения задачи при помощи динамического программирования
Пример решения задачи при помощи динамического программирования

Динамическое программирование всегда начинается с определения начальных условий. В нашем примере достаточно взять сумму одного первого элемента, равную этому элементу: F(1) = 1

Для нахождения суммы двух элементов надо взять полученную сумму первого элемента и прибавить к ней второй элемент: F(2) = F(1) + 2 = 1 + 2 +3

Для трех элементов сумма равна F(3) = F(2) +3 = 6

Отсюда делаем вывод, что искомая функция имеет вид F(n) = F(n-1) + n

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

Роль таблиц в динамическом программировании

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

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

В большинстве случаев используется двумерное динамическое программирование, при котором таблицы состоят из строчек и столбиков точно также, как в Excel. Объем потребляемой памяти для таблицы из n строк и n столбцов равен О(n*n) = О(n*2). То есть, таблица в виде квадрата из 10 строк и 10 столбцов состоит из 100 ячеек.

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

Только до 3.10
Как за 3 часа
разбираться в IT
лучше, чем 90%
новичков и выйти на
доход в 200 000 ₽?
Приглашаем вас на бесплатный онлайн-интенсив «Путь в IT»! За несколько часов эксперты GeekBrains разберутся, как устроена сфера информационных технологий, как в нее попасть и развиваться.
Александр Волчек CEO GeekBrains

Интенсив «Путь в IT» поможет:

  • За 3 часа разбираться в IT лучше, чем 90% новичков.
  • Понять, что действительно ждет IT-индустрию в ближайшие 10 лет.
  • Узнать как по шагам c нуля выйти на доход в 200 000 ₽ в IT.
При регистрации вы получите в подарок:
pdf иконка

«Колесо компетенций»

Тест, в котором вы оцениваете свои качества и узнаете, какая профессия в IT подходит именно вам

doc иконка

«Критические ошибки, которые могут разрушить карьеру»

Собрали 7 типичных ошибок, четвертую должен знать каждый!

pdf иконка

Тест "Есть ли у вас синдром самозванца?"

Мини-тест из 11 вопросов поможет вам увидеть своего внутреннего критика

Хотите сделать первый шаг и погрузиться в мир информационных технологий? Регистрируйтесь и смотрите интенсив:
Только до 3 октября
Осталось 17 мест

Кроме исходных данных, для динамического решения задачи требуется следующее:

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

Использование динамического программирования в реальной жизни

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

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

Использование динамического программирования в реальной жизни
Использование динамического программирования в реальной жизни

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

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

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

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

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

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

Оцените статью
Рейтинг: 3
( голосов 2 )
Поделиться статьей
Добавить комментарий

Забрать
гарантированный
подарок

Получите бесплатно подборку файлов от GeekBrains:

Осталось 17 мест

Поздравляем! Вы выиграли 2-х дневный интенсив "Путь в IT". Чтобы закрепить подарок и получить к нему доступ, заполните информацию в открывшемся окне

×
Петр Озеров
Петр Озеров печатает ...