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

Дерево, Tree, Алгоритм

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

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

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

Возьмем случай генерации последовательности Фибоначчи .

Если последовательность F (1) F (2) F (3) ........ F (50), то следует правило F (n) = F (n-1) + F (n-2)
F(50) = F(49) + F(48)
F(49) = F(48) + F(47)
F(48) = F(47) + F(46)
...

Обратите внимание, что здесь существуют перекрывающиеся подзадачи, потому как нам нужно вычислить F (48), чтобы вычислить, как F (50), так и F (49). Это именно тот алгоритм, где хорошо виден пример динамического программирования.

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

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

Эта техника хранения значения подзадач называется мемоизацией (запоминанием) . Сохраняя значения в массиве, мы экономим время для вычислений подзадач, с которыми мы уже сталкивались.

var m = map(0 → 0, 1 → 1)
function fib(n)
    if key n is not in map m 
           m[n] = fib(n − 1) + fib(n − 2)
    return m[n]

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

function fib(n)
       if n = 0
           return 0
       else
           var prevFib = 0, currFib = 1
           repeat n − 1 times
               var newFib = prevFib + currFib
               prevFib = currFib
               currFib  = newFib
       return currentFib

Рекурсия vs Динамического программирования

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

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

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

Жадные алгоритмы vs Динамического программирования

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

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

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

Рекомендуем хостинг TIMEWEB
Рекомендуем хостинг TIMEWEB
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.
Поддержать автора Donate

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
Ищу работу?
25,000.00 руб. - 30,000.00 руб.
Разработчик Qt/C++
Barnaul, Altai Krai, Russia

Для зарегистрированных пользователей на сайте присутствует минимальное количество рекламы

СВ
23 октября 2019 г. 1:00
Семен Волох

C++ - Тест 004. Указатели, Массивы и Циклы

  • Результат:70баллов,
  • Очки рейтинга1
SS
22 октября 2019 г. 14:31
Samantha Smith

Qt - Тест 001. Сигналы и слоты

  • Результат:52баллов,
  • Очки рейтинга-4
МБ
21 октября 2019 г. 1:25
Михаил Булатов

C++ - Тест 002. Константы

  • Результат:16баллов,
  • Очки рейтинга-10
Последние комментарии
17 октября 2019 г. 2:17
Евгений Легоцкой

Используем, там где требуется :)
MP
17 октября 2019 г. 2:15
Mikhail Petrov

Совет: подключайте ресурсы динамически. Используйте Resource Compiler: https://doc.qt.io/qt-5/rcc.html
16 октября 2019 г. 6:45
Евгений Легоцкой

Если это не чистой воды спам, а по делу, то без проблем. Но в таком случае лучше создавайте отдельный вопрос на форуме . При создании вопроса есть поле, в котором можно указать статью…
КК
16 октября 2019 г. 6:39
Кирилл Кирилыч

А тут можно ссылки на сторонний ресурс показывать? Нашёл на habr похожую статью, только там чуток отличается код и про локальный сервер написано, нужно чтоб кто то понимающий посмотрел и своё …
Сейчас обсуждают на форуме
23 октября 2019 г. 4:06
Евгений Легоцкой

Ну если после обновления начало появляться, то тогда откатить драйвера. А вообще, если это жить не мешает и код работает как и раньше, то просто проигнорировать эти сообщения.
22 октября 2019 г. 2:42
Pavel K.

Всем привет , Пытаюсь реализовать класс для работы с блютуз (Bluetooth Handler) для мобилки , с использование QBluetoothDeviceInfo и QBluetoothDeviceDiscoveryAgent . Может у кого е…
22 октября 2019 г. 2:16
Pavel K.

попробуй сделать через свой собственный компонет , те возьми контрол Component, например , переорпедели как свой , в нем что нить типо проперти type : disk1, disk2 (сделай метод в структуре …
Е
22 октября 2019 г. 0:03
Евгений_Канусовский@1981

Этот алгоритм предназначен для того чтобы исключить из обработки строки содержащие буквенные символы. Если Вам не трудно опишите пожалуйста как бы Вы написали этот алгоритм, желательно в коде?
MP
21 октября 2019 г. 7:03
Mikhail Petrov

Зависит от вашей задачи. Можете обратить внимание на этот пример: https://doc.qt.io/qt-5/qtqml-referenceexamples-properties-example.html QQmlListProperty используется мною достаточно ч…
EVILEG
О нас
Услуги
© EVILEG 2015-2019
Рекомендует хостинг TIMEWEB