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

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

Content

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

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

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

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

Если последовательность 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 Динамического программирования

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

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

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

We recommend hosting TIMEWEB
We recommend hosting TIMEWEB
Stable hosting, on which the social network EVILEG is located. For projects on Django we recommend VDS hosting.
Support the author Donate

Comments

Only authorized users can post comments.
Please, Log in or Sign up
How to become an author?

Contribute to the evolution of the EVILEG community.

Learn how to become a site author.

Learn it
Donate

Good day, Dear Users!!!

I am Evgenii Legotckoi, developer of EVILEG. And it is my hobby project, which helps to learn programming another programmers and developers

If the site helped you, and you want also support the development of the site, than you can donate by following ways

PayPalYandex.Money
Timeweb

Let me recommend you the excellent hosting on which EVILEG is located.

For many years, Timeweb has been proving his stability.

For projects on Django I recommend VDS hosting

View Hosting Timeweb
n
June 5, 2020, 2:28 a.m.
n1k0m1

Qt - Test 001. Signals and slots

  • Result:0points,
  • Rating points-10
s
June 3, 2020, 1:56 a.m.
silo1995

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

  • Result:35points,
  • Rating points-10
AP
June 2, 2020, 9:11 p.m.
Aleksej Pikenin

C++ - Test 005. Structures and Classes

  • Result:75points,
  • Rating points2
Last comments
June 5, 2020, 1:39 a.m.
Evgenij Legotskoj

Qt/C++ - Tutorial 091. How to write a custom delegate controlling the highlighting of a row in a table

По-моему, смысла в этом нет особого. Если делегат будет игнорировать настройки таблицы, то это приведёт ещё к большему непониманию, что вообще происходит, для программиста, который после вас буд…
June 5, 2020, 1:34 a.m.
IscanderChe

Qt/C++ - Tutorial 091. How to write a custom delegate controlling the highlighting of a row in a table

Сижу, размышляю: можно ли переписать делегата так, чтобы независимо от настроек строк выделялись строки?
June 5, 2020, 1:31 a.m.
Evgenij Legotskoj

Qt/C++ - Tutorial 091. How to write a custom delegate controlling the highlighting of a row in a table

Понятно. Я не обратил внимания на то, что там было в старом коде по настройкам строк :)
June 5, 2020, 1:27 a.m.
IscanderChe

Qt/C++ - Tutorial 091. How to write a custom delegate controlling the highlighting of a row in a table

Разобрался. У вас изначально в проекте были вот эти настройки: ui->tableView->setSelectionBehavior(QAbstractItemView::SelectRows);ui->tableView->setSelectionMode(QAbstractItemVie…
June 4, 2020, 11:10 a.m.
IscanderChe

Qt/C++ - Tutorial 091. How to write a custom delegate controlling the highlighting of a row in a table

Полностью скопировал пример - всё правильно работает. Значит, где-то у меня ошибки в тестовом проекте. Буду разбираться. Извините за беспокойство. :)
Now discuss on the forum
June 5, 2020, 6:13 a.m.
IscanderChe

Фильтр для QtableView sql

Добрый день. Для такой фильтрации необходимо использовать QSortFilterProxyModel. В оффдоках есть хороший пример.
MA
June 4, 2020, 2:46 a.m.
Mihail A

Qt- C++ QTableView подсветить строку

Спасибо.
f
June 3, 2020, 1:49 a.m.
fryn3

Можно ли сделать в QML таблицу как в Excel?

edi-tableview - нашел пока такое выглядит коряво, посмотрим что можно сделать
June 2, 2020, 2:46 a.m.
Evgenij Legotskoj

Медиа файлы Google Firebase

Картинки можете попробовать сжимать через QPixmap, там есть возможность установки scaleFactor, через него можете устанавливать нужные параметры. А что касается конвертации видео, то лучше п…
June 2, 2020, 2:01 a.m.
Evgenij Legotskoj

Перехват обращения к локальным файлам QWebEngineView

В вашем случае вполне адекватное решение. Так сказать меньше зло. В противном случае пришлось бы очень много переписывать и перепиливать.
About
Services
© EVILEG 2015-2020
Recommend hosting TIMEWEB