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

Дерево, 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 Динамического программирования

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

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

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

10% refund of hotel reservation amount on Booking
10% refund of hotel reservation amount on Booking
We offer a link with a 10% return on the amount of the order when booking a hotel through Booking
Support the author Donate

Comments

Only authorized users can post comments.
Please, Log in or Sign up
D
Aug. 16, 2019, 11:58 a.m.
Damir

C++ - Тест 003. Условия и циклы

  • Result:92points,
  • Rating points8
D
Aug. 16, 2019, 11:46 a.m.
Damir

C++ - Test 005. Structures and Classes

  • Result:75points,
  • Rating points2
u
Aug. 14, 2019, 1:55 p.m.
unrealproro

C++ - Test 005. Structures and Classes

  • Result:83points,
  • Rating points4
Last comments
Aug. 19, 2019, 6:41 a.m.
Andrej Jankovich

это проблема дистрибутива, попробуйте установить через пакетный менеджер snap Суть проблемы: libQt5Core которая лежит в дистрибутиве требует версию glibc >= 2.25 у вас видимо …
b
Aug. 18, 2019, 5:09 a.m.
bbb116

cqtdeployer /home/aleks/CQtDeployer/bin/cqtdeployer: /lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.25' not found (required by /home/aleks/CQtDeployer/lib/libQt5Core.so.5) linux mint …
D
Aug. 17, 2019, 8:04 a.m.
Damir

github ChekableTView Правой групповая смена значения при перетаскивании левой как обычно.
Aug. 16, 2019, 12:03 p.m.
Evgenij Legotskoj

Потому, что в минуте 60 секунд
Aug. 16, 2019, 11:16 a.m.
Dmitrij

а почему делитель 60000, а не 1000?
Now discuss on the forum
Aug. 20, 2019, 12:17 p.m.
Evgenij Legotskoj

Добрый день. Вы делаете некорректную попытку создать исключение. Исключения генерируются кодом, то есть любое исключение, которое вы перехватываете, всегда генерируется оператором th…
Aug. 20, 2019, 8:04 a.m.
IscanderChe

Ещё раз здравствуйте. Собираю Qt-проект с помощью CMake. Применяю к полученному exe-файлу windeployqt. В результате подцепляются почему-то dll-ки, оканчивающиеся в наименованиях на "d": Qt…
Aug. 20, 2019, 7:46 a.m.
IscanderChe

Да, с таргетом тоже работает. Спасибо!
Aug. 20, 2019, 7:25 a.m.
Evgenij Legotskoj

вы можете испльзовать QList, просто помещайте туда QPair, будет примерно тоже самое. Просто QMap автоматически сортируется по ключу. QList<QPair<QString, QString>> list_with_pair;…
Looking for a Job?
14,000.00 руб. - 40,000.00 руб.
Разработчик Qt
Annino, Moscow Oblast, Russia
5,000.00 руб. - 15,000.00 руб.
Дизайнер
Moskovskiy, Moscow, Russia
25,000.00 руб. - 30,000.00 руб.
Разработчик Qt/C++
Barnaul, Altai Krai, Russia

For registered users on the site there is a minimum amount of advertising

EVILEG
About
Services
© EVILEG 2015-2019
Recommend hosting TIMEWEB