mafulechka
mafulechkaТам. 2, 2019, 4:28 Т.Ж.

Динамикалық бағдарламалау

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

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


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

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

Если последовательность 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 хостинг.

Ол саған ұнайды ма? Әлеуметтік желілерде бөлісіңіз!

Пікірлер

Тек рұқсаты бар пайдаланушылар ғана пікір қалдыра алады.
Кіріңіз немесе Тіркеліңіз
AD

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

  • Нәтиже:50ұпай,
  • Бағалау ұпайлары-4
m
  • molni99
  • Қаз. 26, 2024, 1:37 Т.Ж.

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

  • Нәтиже:80ұпай,
  • Бағалау ұпайлары4
m
  • molni99
  • Қаз. 26, 2024, 1:29 Т.Ж.

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

  • Нәтиже:20ұпай,
  • Бағалау ұпайлары-10
Соңғы пікірлер
ИМ
Игорь МаксимовҚар. 22, 2024, 11:51 Т.Ж.
Django - Оқулық 017. Теңшелген Django кіру беті Добрый вечер Евгений! Я сделал себе авторизацию аналогичную вашей, все работает, кроме возврата к предидущей странице. Редеректит всегда на главную, хотя в логах сервера вижу запросы на правильн…
Evgenii Legotckoi
Evgenii LegotckoiҚаз. 31, 2024, 2:37 Т.Қ.
Django - Сабақ 064. Python Markdown кеңейтімін қалай жазуға болады Добрый день. Да, можно. Либо через такие же плагины, либо с постобработкой через python библиотеку Beautiful Soup
A
ALO1ZEҚаз. 19, 2024, 8:19 Т.Ж.
Qt Creator көмегімен fb3 файл оқу құралы Подскажите как это запустить? Я не шарю в программировании и кодинге. Скачал и установаил Qt, но куча ошибок выдается и не запустить. А очень надо fb3 переконвертировать в html
ИМ
Игорь МаксимовҚаз. 5, 2024, 7:51 Т.Ж.
Django - Сабақ 064. Python Markdown кеңейтімін қалай жазуға болады Приветствую Евгений! У меня вопрос. Можно ли вставлять свои классы в разметку редактора markdown? Допустим имея стандартную разметку: <ul> <li></li> <li></l…
d
dblas5Шілде 5, 2024, 11:02 Т.Ж.
QML - Сабақ 016. SQLite деректер қоры және онымен QML Qt-та жұмыс істеу Здравствуйте, возникает такая проблема (я новичок): ApplicationWindow неизвестный элемент. (М300) для TextField и Button аналогично. Могу предположить, что из-за более новой верси…
Енді форумда талқылаңыз
m
moogoҚар. 22, 2024, 7:17 Т.Ж.
Mosquito Spray System Effective Mosquito Systems for Backyard | Eco-Friendly Misting Control Device & Repellent Spray - Moogo ; Upgrade your backyard with our mosquito-repellent device! Our misters conce…
Evgenii Legotckoi
Evgenii LegotckoiМаусым 24, 2024, 3:11 Т.Қ.
добавить qlineseries в функции Я тут. Работы оень много. Отправил его в бан.
t
tonypeachey1Қар. 15, 2024, 6:04 Т.Ж.
google domain [url=https://google.com/]domain[/url] domain [http://www.example.com link title]
NSProject
NSProjectМаусым 4, 2022, 3:49 Т.Ж.
Всё ещё разбираюсь с кешем. В следствии прочтения данной статьи. Я принял для себя решение сделать кеширование свойств менеджера модели LikeDislike. И так как установка evileg_core для меня не была возможна, ибо он писался…

Бізді әлеуметтік желілерде бақылаңыз