Динамическое программирование что такое: Что такое динамическое программирование — объясняют эксперты

Содержание

Что такое динамическое программирование — объясняют эксперты

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

Некоторые подобные задачи можно решить путем разбиения исходной задачи на подзадачи меньшего размера и сложности, решив которые и объединив результаты, можно получить решение исходной задачи. Такой подход называется динамическим программированием и был предложен Ричардом Беллманом в 1940-х годах.

N), что существенно больше.

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

Данную задачу можно решить методом полного перебора ― сгенерировать все возможные маршруты (всего их N!) для N адресов, а затем выбрать маршрут минимальной длины. Сложность данного алгоритма O(N! * N) и время вычисления очень быстро растет при росте количества адресов ― если для трех адресов нужно рассмотреть шесть вариантов, то для 10 уже около четырех миллионов!

Использование подходов динамического программирования может не дать наилучшего решения, но, тем не менее, оно будет достаточно хорошим и за приемлемое время. Суть подхода к решению данной задачи заключается в поиске ближайшего адреса на каждом шаге ― из исходной точки, затем следующего ближайшего пункта назначения из первого адреса и так далее. N), что для тех же 10 адресов 1124 вычислений.

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

Динамическое программирование теория графов сетевое планирование (учебное пособие для студентов)

Самаров К.Л.

Учебное пособие для студентов по математике

Элементы теории графов. Динамическое программирование. Сетевое планирование

СОДЕРЖАНИЕ

  1. Элементы теории графов
    • Основные понятия, определения и термины
    • Задача о построении минимального остовного дерева
  2. Динамическое программирование
    • Общая схема метода динамического программирования
    • Задача о распределении средств
  3. Сетевое планирование. Применение алгоритмов динамического программирования
    • Понятие сети
    • Построение сетевого графика технологического комплекса
    • Постановка задачи о нахождении наименьшего времени выполнения технологического комплекса
    • Описание алгоритма динамического программирования для решения задачи о наименьшем времени выполнения технологического комплекса
      • Построение сетевого графика, упорядоченного по этапам
      • Расчет времени завершения узлов
      • Построение критического пути и нахождение критического времени завершения комплекса работ
      • Нахождение свободных резервов времени на некритических операциях
      • Применение алгоритма динамического программирования для решения задачи о наименьшем времени выполнения технологического комплекса
    • Постановка задачи о поиске в сети кратчайшего пути
    • Применение алгоритма динамического программирования для решения задачи о поиске в сети кратчайшего пути

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

ЛИТЕРАТУРА

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

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

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

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

Возьмем случай генерации

последовательности Фибоначчи .

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

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

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

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

Динамическое программирование. Базовые понятия. — Паскаль: экспресс-курс олимпиадного бойца

   Задача 1. Новый Лабиринт Амбера

   Идея решения: Понятно, что в первую ячейку согласно условия мы попасть не можем, поэтому после чтения исходных данных занесем в нее 0, в не зависимости от того, что нам предлагается для неё при считывании исходных данных, а во вторую и третью мы можем попасть единственным образом с начальной  нулевой ячейки. Для всех остальных ячеек у нас есть выбор: попасть в нее либо с ячейки под номером i–2, либо с ячейки под номером  i–3. Выбирать, естественно будем ту, где перед этим уже имеется большая сумма. Схематически это можно изобразить так (на примере с условия задачи):

Номера ячеек

0

1

2

3

4

5

0

1000

2

3

1

3

Содержимое ячеек

    Заменяем содержимое ячейки 1 и начиная с четвертой ячейки, начинаем заниматься решением вопроса, откуда же выгоднее в неё попасть: с ячейки a[i–2] или a[i–3]?

   Естественно, что выгоднее в ячейку под номером 4 попасть с ячейки под номером 2 (с индексом i–2), так как там уже есть 2 монетки и сумма будет 3, а в ячейке под номером 1 (с индексом i–3) уже накоплено 0 монеток, и сумма будет 1, что является не выгодным. Не заводя дополнительный массив, будем хранить в этой текущей рассматриваемой ячейке найденную сумму, которую формально можно описать так:

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

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

              Номера ячеек

0

1

2

3

4

5

0

0

2

3

3

6

Содержимое ячеек

   В результате у нас в конечной (N-той) ячейке всегда будет находится ответ к задаче.

   Описанный выше подход лежит в основе динамического программирования. В основу принципа динамического программирования положено следующую простую стратегию оптимальной политики, указанную Р.Беллманом и названную им принципом оптимальности: „Именно оптимальной политике присуще то свойство, что какими бы не были начальное состояние и первое решение, последующие решения составляют оптимальную политику относительно начального состояния, полученного в результате первого решения.”

   Задача 2. Лесенка

   Идея решения: Решение данной задачи немногим отличается от предыдущей только тем, что на каждую текующую рассматривуемую ступеньку мы можем попасть уже имея выбор не из 2-х возможных, а из K предыдущих ступенек. Этот подход легко реализуется при помощи дополнительного цикла. Чтобы не изменять логику поиска предыдущей программы зададим массив используя ту особенность языка паскаль, что нумеровать массив можно начиная с произвольного индекса.  

   Подсказка: массив чисел, хранящихся на ступеньках, следует объявить как a : array[-1000..1001] of longint;

   Задача 3. Единицы

   Идея решения: Понятно, что для того, чтобы получить число 1 достаточно просто написать одну единицу, а число 2 получается путем сложения двух еиниц. Дальнейшая логика такова: мы можем любое следующее число найти, прибавив к предыдущему одну единицу (a[k] = a[k-1] + 1) — это и есть первое приближение оптимального решения. После этого пробуем число k разложить на два множителя, и если это удалось, то сума единиц, входящих в каждый из сомножителей проверятся с текущим оптимальным значением a[k], если найденное число оказывется меньшим, естественно принимаем его за оптимальное. Искать разложение достаточно до sqrt(k).

   Задача 4. Paint2D

   Идея решения: Идею решения данной задачи разберем более детально.

(Продолжение следует)

Динамическое программирование как метод оптимизации процессов

    Применение метода динамического программирования для оптимизации процессов с распределенными параметрами или в задачах динамической оптимизации приводит к решению диф([)еренциальных уравнений в частных производных. Вместо решения таких уравнений зачастую значительно проще представить непрерывный процесс как дискретный с достаточно большим числом стадий. Подобный прием оправдан особенно в тех случаях, когда имеются ограничения на переменные задачи и прямое решение дифференциальных уравнений осложняется необходимостью учета указанных ограничений. [c.32]
    Более сложная задача возникает при использовании метода динамического программирования для оптимизации процессов с байпасными потоками. Поскольку направление расчета противоположно направлению такого потока, при выборе оптимального управления на стадии, к которой он подводится, состояние этого потока, так же как и состояние выхода предшествующей стадии, необходимо исследовать во всем возможном диапазоне изменения его параметров.
Другими словами, размерность задачи выбора оптимального управления изданной стадии увеличивается на размерность состояния байпасного потока. [c.297]

    Эти затруднения при применении динамического программирования для оптимизации процессов высокой размерности создатель метода Р. Беллман образно назвал проклятием размерности . [c.280]

    Вьиие уже была рассмотрена вычислительная процедура метода динамического программирования при оптимизации процесса, в котором размерность векторов состояния п управления на каждой стадии равна 1. Очевидно, что решение задачи может усложниться, если размерность вектора состояния гп или векторов управления г [c.259]

    Для решения задач оптимизации ХТС с многостадийной структурой, а также для процессов, которые могут быть математически описаны как многостадийные, успешно применяют метод динамического программирования. [c.222]

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

    В простейших случаях, когда целевая функция задана аналитически, используют классические методы нахождения экстремума методами дифференциального исчисления. При наличии ограничений типа равенств, наложенных на независимые переменные, используют метод множителей Лагранжа. В более сложных случаях, когда критерий оптимальности представлен в виде функционалов, используют методы вариационного исчисления-, при оптимизации процессов, описываемых системами дифференциальных уравнений, применяют принцип максимума Понтрягина. Используют также динамическое, линейное программирование и другие методы оптимизации. [c.38]


    Для оптимизации процессов с распределенными параметрами предпочтительнее все же оказывается принцип максимума, которому посвящена следующая глава. Однако всегда нужно учитывать воз-мо кность аппроксимации непрерывного процесса дискретным многостадийным процессом и пользоваться указанной возмо кностью для решения оптимальных задач невысокой размерности. Это обусловлено 1см, что метод динамического программирования представляет в распоряжение исследователя весьма удобную процедуру оптимизации многостадийных процессов, которая сравнительно легко программируется на вычислительных ма1[шнах. [c.319]

    Пап этом величины ( > (>ч. А,.,), однократного использования метода динамического программирования для оптимизации многостадийного процесса при заданных постоянных значениях и X.,. [c.303]

    Основное преимущество рассмотренного метода по сравнению с методом динамического программирования состоит в том, что при вычислительном процессе не требуется запоминания в ЦВМ про- межуточных результатов счета на каждом шаге итерационного процесса. Однако динамическое программирование неизбежно обеспечивает онределение глобального экстремума, в то время как описанный метод позволяет находить лишь стационарное значение функции цели. Еслп же эта функция имеет не один экстремум, решение с помощью данного метода значительно усложняется, поскольку приходится исследовать всю область, где определен критерий оптимизации, для нахождения глобального экстремального значения. К тому же вид уравнений (VI,32) определяет безусловный экстремум функции цели, что не характерно для реальных ХТС, в которых всегда существуют ограничения технологического характера. [c.311]

    В предыдущих разделах настоящей главы рассматривались вопросы применения метода динамического программирования для оптимизации дискретных многостадийных процессов. Именно при анализе таких процессов, которые допускают четкое разбиение на стадии, наиболее наглядно проявляются основные достоинства этого метода как способа решения оптимальных задач для процессов с произвольным числом управляемых стадий. Однако метод динамического программирования можно использовать также и для оптимизации процессов с распределенными параметрами и нестационарных процессов с сосредоточенными параметрами, которые изменяются непрерывно. При этом закон их изменения описывается системами дифференциальных уравнений [c.295]

    В качестве метода оптимизации процесса управления водным режимом сельскохозяйственных культур выбран метод стохастической поэтапной оптимизации, основанный на принципе динамического программирования. Стохастические задачи динамического программирования решаются ходом назад , так как стохастическая природа процесса не позволяет задать состояние системы в конце планируемого периода. Поэтому оптимальное решение, принимаемое в начале первого периода, находится из заданного условия оптимальности функции цели за весь планируемый промежуток времени. Поскольку величина этой [c.247]

    Идея использования методов динамического программирования для оптимизации каскада реакторов принадлежит Арису [1, 85]. Однако в его работах эта задача решалась при упрощающих предположениях об ограничениях, накладываемых на режим процесса в каскаде. [c.186]

    Оптимизация узла обезвоживания может осуществляться с применением динамического программирования, широко применяемого в химической технологии, в графическом и аналитическом виде. Авторами сделана попытка применить динамическое программирование для оптимизации не только узлов обезвоживания, но и всего комплекса сооружений. Показана возможность применения динамического программирования для оптимизации схем очистки сточных вод, схем промышленного водопользования в рамках предприятий. Вероятно, следует отдавать предпочтение графическому методу, который обеспечивает наглядность, точность оптимизационных расчетов, так как в настоящее время отсутствует возможность получения в аналитическом виде технико-экономических моделей отдельных процессов, описывающих их с достаточной точ- [c.87]

    Для решения задач оптимизации химико-технологических процессов обычно используют методы нелинейного программирования (поисковые методы) [1, 3] и методы теории оптимального управления вариационного исчисления [4], динамического программирования 15], принципа максимума Понтрягина [6], дискретного принципа максимума 17]. Наибольшее распространение получили поисковые методы как наиболее гибкие и универсальные. Эти методы находят также широкое применение при решении задач идентификации (определение некоторых коэффициентов уравнений, представляющих собой математическую модель исследуемого процесса). Кроме того, поисковые методы могут быть эффективно использованы при синтезе оптимальной структуры химико-технологических систем, который в общем случае представляет собой задачу дискретно-непрерывного программирования в частности, они могут быть использованы при получении нижних оценок в методе ветвей и границ (см. гл. VI). [c.14]

    Важной характеристикой любой оптимальной задачи является ее размерность п, равная числу переменных, задание значений которых необходимо для однозначного определения состояния оптимизируемого объекта. Как правило, решение задач высокой размерности связано с необходимостью выполнения большого объема вычислений. Ряд методов (например, динамическое программирование и дискретный принцип максимума) специально предназначен для решения задач оптимизации процессов высокой размерности, которые могут быть представлены как многостадийные процессы с относительно невысокой размерностью каждой стадии.[c.34]

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

    При рассмотрении задачи последовательной оптимизации метод динамического программирования позволяет разбить ее на несколько отдельных задач с меньшим числом переменных, что весьма облегчает вычисления в процессе решения. В частности, если ХТС имеет только последовательные технологические связи, задача совместной максимизации параметров может быть сведена к максимизации [c.309]

    У.5.1. Оптимизация многостадийных процессов методом динамического программирования [c.222]

    В книге в доступной форме изложены основы методов оптимизации химических производств (классический анализ, вариационное исчисление, принцип максимума, динамическое, линейное, нелинейное и геометрическое программирование). Сформулированы общие положения, касающиеся выбора критериев оптимальности химико-технологических процессов, и приведены их математические модели. Рассмотрены задачи оптимизации конкретных процессов. Второе издание (первое издание выпущено в 1969 г.) дополнено изложением основ геометрического программирования, а также примерами, иллюстрирующими практическую реализацию методов нелинейного программирования. [c.4]

    Оптимальное управление комплексом процессов по глобальному критерию может быть реализовано с помощью пакета программ, содержащего модели всех стадий и процедуры поиска экстремальных значений функций п переменных известными методами оптимизации. При расчете оптимальных значений управляющих воздействий и в процессе производства сульфонола можно, например, использовать метод динамического программирования. [c.393]

    Известен ряд работ, где для управления процессом ферментации используют оптимальные подпитки субстратом в ходе периодического процесса ферментации [3, 28], оптимальный температурный профиль [23, 27], изменения рОг среды в течение режима ферментации [25]. При рещении указанных задач применяют такие методы оптимизации, как принцип максимума Понтрягина, динамическое, нелинейное программирование. [c.33]

    Арис [1, 2] дает введение к использованию динамического программирования для оптимизации дискретных и непрерывных процессов и рассматривает применение этого метода к широкому классу реакторов. Четкое описание способов использования классического вариационного исчисления для определения наилучшего распределения температур в реакторах с принудительным движением потока дано Катцем [5]. Катц показал, что применение динамического программирования к этой задаче приводит к дифференциальному уравнению в частных производных. Рассмотренные в предыдущей главе доклады Хорна посвящены применению градиентного [c.381]

    В книге в доступной форме изложены основы методом оптимизации (классический анализ, вариационное исчисление, принцип максимума, динамическое, линейное и нелинейное программирование) с иллюстрацией их на объектах химической технологии. Сформулированы общие положения, касающиеся выбора критериев о[1ти-мальности химико-технологических процессов, и приведены их математические модели. Рассмотрены задачи, связанные с оптимизацией конкретных процессов. [c.4]

    Динамическое программирование идеально приспособлено для решения задач оптимизации многостадийных процессов, особенно задач, в которых на каждой стадии имеется небольшое число пере-мепньгх. Однако при наличии значительного числа этих переменных, т. е. при высокой размерности каждой стадии, применение метода динамического программирования затруднительно вследствие ограниченных быстродействия и объема памяти вычислительных машин. [c.29]

    Динамическое программирование (см. главу VI) служит эффективным методол решения задач оптимизации дискретных многостадийных процессов, для которых общий критерий оптимальности 01И1сьшается аддитивной функцией критериев оптимальности отдельных стадии. Без особых затруднений указанный метод можно распространить на многостадийные процессы с байпасными и рецир- [c. 31]

    Ряд методов оптимизации, как, например, динамическое программирование, дает достаточную информацию о чувствительности оптимума уже в процессе их использования для решения оптимальных задач. Другие методы менее приспособлены к анализу чувствител ,-ностн оптимума. Лишь для задач линейного программирования имеется до некоторой степени разработанный математический аппарат (параметрическое линейное программирование), позволяюи1Ий изучать поведение оптимального решения при измеиенпи коэффициентов математического описания . [c.39]

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

    Именно для решения задач оптимизации многостадийных процессов, а также процессов, которые могут быть математически описаны как многостадийные, создан и в настоящее время уснеишо применяется метод динамического программирования. [c.244]

    Динамическое программирование, как и все методы, рассмотренные в предыдущих главах, применяется для оптимизации математически описанных процессов. Поэтому в дальнейшем для многостадийного процесса (рис, VI- ) предполагается изгзестиым математическое описание его каждо стадии, которое представляется в об1цем виде системой уравнений [c.246]

    Рассмотрим теперь, каким образом можно решить сформулиро-вапную вьипе комбинаторную задачу, используя метод динамического программирования. Как отмечалось выше, процедура решении задачи оптимизации при помощи принципа оптимальности начинается с оптимизации последней стадии процесса, результатом чего является иабор оптимальных ре1иений (управлений) па ней для любых в(имож-пых состояний входа этой стадии. [c.250]

    Общая процедура решения задачи методом динамического программирования. Проиллюстрируем процедуру решения задачи оптимизации многостадийного процесса на примере процесса, в котором размергюсть векторов состояния и управления на каждой стадии равна единице. Это позволяет повысить наглядность проводимых рассуждений при помощи графическ[1Х построений. [c.255]

    Метод принципа максимума для сложвцх процессов значительно экономнее метода динамического программирования. На основе данного метода удается создать общий подход к решет нию задач оптимизации стационарных и нестационарных каталитических процессов. Этот метод заключается в решении краевой задачи для системы обыкновенных дифференциальных уравнений и определении оптимального управления на каждом шаге интегрирования исходя из условия максимума некоторой функции Решение состоит в выборе некоторых начальных условий и их дальнейшего уточнения для нахождения оптимального режима. Указанная процедура позволяет разработать эффективный численный метод решения краевых задач. [c.495]

    Проблема размерности. Таким образом, метод динамического программирования дает возможность при оптимизации многостадийных процессов расчленить задачу врлбора оптимальных управлений (t 1,. . ., N) па N задач, в каждой из которых выбирается только одно управление и. [c.259]

    После того как оптимальное значение у > определено выражением ( 1,160), оптимизация следующих (предыдущих) стадин проводится обычным порядком для завершения первого этапа решеиия оптимальной задачи методом динамического программирования, в результате чего находится стратегия оптимального управления для всех стадий процесса. [c.296]

    Метод динамического программирования применим к любым многостадийным процессам, в которых на каждой стадий надо принимать решения для оптимизации всего процесса. Среди работ, в которых этот метод использовался для оптимизации химических реакторов, прежде всего надо отметить цикл работ Р. Арпса, которые затем были обобщены в его монографии . При полющи указанного метода Р. Арис рассмотрел оптимизацию последовательности реакторов идеального смешения адиабатических полочных реакторов с охлаждением потоков между полками теплообменниками (или исходным реакционным газом, либо газом, отличным от исходного), а также оптимизацию реактора идеального вытеснения. В частности, он получил ранее найденные методом вариационного исчисления уравнения оптимальной температурной кривой в реакторе идеального вытеснения для общего случая. [c.10]

    Прп оптимизации дискретных многостадийных процессов использование математического аппарата принципа максимума зачастую оказывается более эффективным, чем нримепенне метода динамического программирования. В особенности это относится к ранению оптимальных задач, где размерность отдельных стадий затрудняет использование вычислительной процедуры метода динамического программирования [c.393]

    Показано, что использование методов динамического программирования в задачах оптимизации с управляемым, многопараметрическим рециклом по непрореагировавшему массопотоку достаточно эффективно в случае, когда математические модели отдельных стадий достаточно просты. Процессы в технологической схеме совместного получения метанола и высших спиртов сложны Это предполагает использование распределенных математических моделей Общая размерность задачи оптимизации в данном случае становится очен1 большой. [c.59]

    Книга посвящена актуальному в настоящее время вопросу применения математических методов для расчета оптимальных (наилучших) режимов технологических процессов. Дана характеристика основных этапов работ по статической, квазистатической и динамической оптимиаации как действующих химических реакторов, так и при их проектировании. Сопоставлены два важнейших метода оптимизации — метод поиска на объекте и метод оптимизации с помощью математической модели. Большое внимание уделено математическим способам оптимизации — нелинейному программированию и Принципу максимума. [c.4]

    Достоинство работ Р. Ариса заключается в том, что он с единых позиций подошел к решению большого числа задач оптимизации химических реакторов. {1}$, не являются полностью упорядоченными. По этой причине $\textit{граф структурных связей}$ между элементами (пикселами) изображения, в отличие от аналогичного графа для элементов одномерных функций, имеет вид не $\textit{цепи}$, а $\textit{решетки}$, то есть включает множество $\textit{циклов}$. Между тем, как известно из теории динамического программирования, этот метод работает только для таких структур, граф структурных связей между элементами которых имеет вид $\textit{ациклического графа}$ (ACG) или $\textit{дерева}$ , поскольку только для таких графов существует возможность в любой точке разделить все влияющие на результат вычислений элементы на две группы: те, что находятся «выше» по дереву, и те, что «ниже». Таким образом, растровое изображение (прямоугольная решетка пикселов) оказывается неподходящей структурой данных для непосредственного строгого применения методов динамического программирования.

Эта проблема породила, с одной стороны, ряд работ, предлагающих другие вычислительные техники для оптимизации целевых критериев на дискретных двумерных функциях, среди которых выделяется, в частности, группа подходов, основанных на технике «имитационного отжига» , а с другой стороны — стремление к разработке таких структурных моделей двумерных объектов, которые бы достаточно адекватно описывали яркостно-геометрическую и/или топологическую структуру изображения, но при этом, в отличие от решетки пикселов, имели искомый вид ациклического графа. Однако методы $\textit{распространения состояний}$ (evidence propagation) типа имитационного отжига являются существенно итеративными и, как и большинство других итеративных методов оптимизации, не гарантируют сходимости решения к искомому глобальному оптимуму. С практической точки зрения получаемые этими методами квазиоптимальные решения во многих случаях являются «достаточно хорошими», однако с точки зрения реализации проективных морфологических проекторов их квазиоптимальность является принципиальным недостатком. Поскольку все доказательства проективности тех или иных операторов по необходимости основаны на том, что соответствующие критерии являются выпуклыми, что и обеспечивает единственность оптимального решения, квазиоптимальный вычислительный метод сразу превращает хорошо обоснованный критерий в плохо или неопределенно обоснованный, что автоматически делает реализованный таким образом оператор непроективным (негарантированно проективным). Следовательно, необходимо двигаться по второму пути и искать адекватные каждой конкретной задаче способы реализации методов динамического программирования для двумерных и трехмерных данных. Таких попыток известно множество, причем наиболее успешными, как и следовало ожидать, они оказываются при описании изображений объектов «высокого» уровня — например, структурных остовов в методе двумерных и трехмерных $\textit{обобщенных цилиндров}$ . Однако чем ближе мы оказываемся к уровню растровых данных, тем труднее описать их ациклическими графами так, чтобы не были потеряны какие-то существенные характерно двумерные свойства изображения. Впрочем, для некоторых частных задач такие решения найдены. Так, для анализа бинарных двумерных образов хорошо известна техника построения $\textit{морфологических остовов}$ (skeletons) с последующим разрывом циклов в наиболее «напряженных» узлах. Для другой специфической задачи — стереоотождествления — во многих работах используется граф, представляющий изображение в виде строковых цепочек, связанных между собой только по одному опорному столбцу. Такое представление в виде «дерева строк» достаточно адекватно задаче анализа ректифицированных стереопар, в которых строки двух изображений действительно попарно соответствуют друг другу, но вряд ли может быть признано в качестве общей структуры, универсально пригодной для решения основных типовых задач анализа изображений. Таким образом, вопрос о выборе структуры представления двумерных и трехмерных растровых данных в методе динамического программирования остается на сегодня открытым и является предметом интенсивных исследований.

Динамическое программирование в задаче маршрутизации: схема независимых вычислений | Ченцов

1. Ченцов А. Г., Кошелева М. С. Динамическое программирование в задаче курьера со стоимостями, зависящими от списка заданий // Мехатроника, автоматизация, управление. 2015. Т. 16, № 4. С. 232-244.

2. Ченцов А. Г. Одна параллельная процедура построения функции Беллмана в обобщенной задаче курьера с внутренними работами // АиТ. 2012. № 3. С. 134-149.

3. Ченцов А. Г. Одна параллельная процедура построения функции Беллмана в обобщенной задаче курьера с внутренними работами // Вестник ЮУрГУ. Germany: LAP LAMBERT Academic Publishing GmbH & Co. RG, 2011. 232 c.

7. Коробкин В. В., Сесекин А. Н., Ташлыков О. Л., Чен-цов А. Г. Методы маршрутизации и их приложения в задачах повышения безопасности и эффективности эксплуатации атомных станций. М.: Новые технологии, 2012. 234 с.

8. Петунин А. А. О некоторых стратегиях формирования маршрута инструмента при разработке управляющих программ для машин термической резки материала // Вестник УГАТУ. Серия: Управление, вычислительная техника и информатика. 2009. Т. 13. № 2 (35). С. 280-286.

9. Фроловский В. Д. Автоматизация проектирования управляющих программ тепловой резки металла на оборудовании с ЧПУ // Информационные технологии в проектировании и производстве. 2005. № 4. С. 63-66.

10. Петунин А. А., Ченцов А. Г., Ченцов П. А. К вопросу о маршрутизации движения инструмента в машинах листовой резки с числовым программным управлением // Науч.-техн. ведомости СПбГПУ. Сер. Информатика. Телекоммуникации. Управление. 2013. № 2 (169). С. 103-111.

11. Меламед И. И., Сергеев С. И., Сигал И. Х. Задача коммивояжера. I. Вопросы теории; II. Точные алгоритмы; III. Приближенные алгоритмы // АиТ. 1989. № 9. C. 3-34; № 10. C. 3-29; № 11. C. 3-26.

12. Gutin G., Punnen A. P. The Traveling Salesman Problem and Its Variations // Kluwer. 2002. 830 p.

13. William J. Cook. In pursuit of the traveling salesman. Mathematics at the limits of computation. Princeton University Press, NJ. 2012. P. 248.

14. Литл Дж., Мурти К., Суини Д., Кэрел К. Алгоритм для решения задачи о коммивояжере // Экономика и математические методы. 1965. Т. 1 (Вып. 1). С. 94-107.

15. Беллман Р. Применение динамического программирования к задаче о коммивояжере // Кибернет. сборник. Т. 9. М.: Мир, 1964. С. 219-228.

16. Хелд М., Карп Р. М. Применение динамического программирования к задачам упорядочения // Кибернет. сборник. 1964. Т. 9. С. 202-218.

17. Ченцов А. Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. М., Ижевск: НИЦ «Регулярная и хаотическая динамика», 2008. 240 с.

18. Куратовский К., Мостовский А. Теория множеств. М.: Мир. 1970. 416 c.

19. Дьедонне Ж. Основы современного анализа. М.: Мир, 1964. 430 с.

20. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1990. 960 с.

21. Ченцов А. А., Ченцов А. Г., Ченцов П. А. Элементы динамического программирования в экстремальных задачах маршрутизации // Проблемы управления. 2013. № 5. С. 12-21.

22. Ченцов А. Г. Задача последовательного обхода мегаполисов с условиями предшествования // АиТ. 2014. № 4. С. 170-190.

23. Ченцов А. Г. К вопросу о маршрутизации комплексов работ // Вестник Удм. ун-та. Математика. Механика. Комп. науки. 2013. № 1. С. 59-82.

24. Ченцов А. Г. , Ченцов А. А. К вопросу о нахождении значения маршрутной задачи с ограничениями // Проблемы управления и информатики. 2016. № 1. С. 41-54.

Демистификация динамического программирования

by Alaina Kafkes

Как создавать и кодировать алгоритмы динамического программирования

Возможно, вы слышали об этом при подготовке к собеседованию по программированию. Может быть, вы пытались это сделать на курсе алгоритмов. Может быть, вы пытаетесь научиться программировать самостоятельно, и где-то по пути вам сказали, что важно понимать динамическое программирование. Использование динамического программирования (DP) для написания алгоритмов столь же важно, как и опасения.

И кто может винить тех, кто уклоняется от этого? Динамическое программирование кажется устрашающим, потому что его плохо учат. Многие учебные пособия сосредоточены на результате — объясняет алгоритм, а не процесс — находит алгоритм. Это способствует запоминанию, а не пониманию.

На уроках алгоритмов в этом году я собрал воедино свой собственный процесс решения задач, требующих динамического программирования. Части его исходят от моего профессора алгоритмов (которому следует большая заслуга!), А частично — из моего собственного анализа алгоритмов динамического программирования.

Но прежде чем я расскажу о своем процессе, давайте начнем с основ. Что вообще такое динамическое программирование?

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

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

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

Я надеюсь передать то, что DP — полезный метод для задач оптимизации, тех проблем, которые ищут максимальное или минимальное решение при определенных ограничениях, потому что он просматривает все возможные подзадачи и никогда не пересчитывает решение какой-либо подзадачи. . Это гарантирует правильность и эффективность, чего нельзя сказать о большинстве методов, используемых для решения или аппроксимации алгоритмов. Уже одно это делает DP особенным.

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

Подзадачи на Подзадачах Подзадачи

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

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

Представьте, что вы еще в 1950-х годах работаете над компьютером IBM-650.Вы знаете, что это значит — перфокарты! Ваша работа для мужчины или женщины — IBM-650 на день. Вам предлагается запустить натуральное число n перфокарт. Каждая перфокарта i должна запускаться в некоторое заранее определенное время начала s_i и останавливаться в некотором заранее определенном времени окончания f_i . На IBM-650 может одновременно работать только одна перфокарта. Каждая перфокарта также имеет соответствующее значение v_i в зависимости от того, насколько она важна для вашей компании.

Проблема : Как лицо, отвечающее за IBM-650, вы должны определить оптимальное расписание перфокарт, которое максимизирует общую ценность всех используемых перфокарт.

Поскольку я подробно рассмотрю этот пример в этой статье, я пока только дразню вас его подзадачей:

Подзадача : График максимального значения для перфокарт с i n , чтобы перфокарты сортировались по времени начала.

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

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

Мотивирующая мемоизация с числами Фибоначчи

Когда вам предложат реализовать алгоритм, который вычисляет значение Фибоначчи для любого заданного числа, что бы вы сделали? Большинство людей, которых я знаю, выберут рекурсивный алгоритм, который в Python выглядит примерно так:

  def fibonacciVal (n): if n == 0: return 0 elif n == 1: return 1 else: return fibonacciVal (n- 1) + fibonacciVal (n-2)  

Этот алгоритм выполняет свою задачу, но стоит огромных затрат . Например, давайте посмотрим, что этот алгоритм должен вычислить, чтобы решить для n = 5 (сокращенно F (5)):

  F (5) / \ / \ / \ F (4) F (3) / \ / \ F (3) F (2) F (2) F (1) / \ / \ / \ F (2) F (1) F (1) F (0) F (1) F (0) / \ F (1) F (0)  

Дерево выше представляет каждое вычисление, которое должно быть выполнено, чтобы найти значение Фибоначчи для n = 5.Обратите внимание, как подзадача для n = 2 решается трижды. Для относительно небольшого примера (n = 5) это много повторяющихся и бесполезных вычислений!

Что делать, если вместо трехкратного вычисления значения Фибоначчи для n = 2 мы создадим алгоритм, который вычисляет его один раз, сохраняет его значение и обращается к сохраненному значению Фибоначчи для каждого последующего появления n = 2? Это , ровно , что делает мемоизация.

Имея это в виду, я написал решение динамического программирования для проблемы значений Фибоначчи:

  def fibonacciVal (n): memo = [0] * (n + 1) memo [0], memo [1] = 0, 1 для i в диапазоне (2, n + 1): memo [i] = memo [i-1] + memo [i-2] return memo [n]  

Обратите внимание, как решение возвращаемого значения происходит из мемоизационного массива memo [], который итеративно заполняется циклом for. Под «итеративно» я подразумеваю, что memo [2] вычисляется и сохраняется перед memo [3], memo [4],… и memo [ n ]. Поскольку memo [] заполняется в этом порядке, решение для каждой подзадачи (n = 3) может быть решено решениями ее предыдущих подзадач (n = 2 и n = 1), потому что эти значения уже были сохранены в memo [] в более раннее время.

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

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

Мой процесс динамического программирования

Шаг 1. Определите подзадачу словами.

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

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

Например, в задаче перфокарты я заявил, что подзадачу можно записать как «график максимального значения для перфокарт от i до n , так что перфокарты сортируются по времени начала». Я обнаружил эту подзадачу, осознав, что для определения графика максимальной стоимости для перфокарт с 1 по n , чтобы перфокарты были отсортированы по времени начала, мне нужно было бы найти ответ на следующие подзадачи:

  • Таблица максимальных значений для перфокарт n-1 от до n , так что перфокарты сортируются по времени начала
  • Таблица максимальных значений для перфокарт с n-2 до n , так что перфокарты сортируются по время начала
  • График максимального значения для перфокарт n-3 n , так что Перфокарты сортируются по времени начала

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

Шаг 2: Запишите подзадачу как повторяющееся математическое решение.

Как только вы определили подзадачу словами, самое время записать ее математически. Зачем? Что ж, математическое повторение , или повторяющееся решение, которое вы обнаружите, в конечном итоге будет тем, что вы вложите в свой код. Кроме того, выписывание подзадачи математически проверяет вашу подзадачу словами из шага 1. Если сложно закодировать подзадачу из шага 1 в математике, то это может быть неправильная подзадача!

Есть два вопроса, которые я задаю себе каждый раз, когда пытаюсь найти повторение:

  • Какое решение я принимаю на каждом этапе?
  • Если мой алгоритм находится на шаге i , какая информация потребуется, чтобы решить, что делать на шаге i + 1 ? (А иногда: если мой алгоритм находится на шаге i , какая информация ему нужна, чтобы решить, что делать на шаге i-1 ?)

Давайте вернемся к проблеме перфокарты и зададим эти вопросы.

Какое решение я принимаю на каждом этапе? Предположим, что перфокарты отсортированы по времени начала, как упоминалось ранее. Для каждой перфокарты, которая на данный момент совместима с расписанием (время ее начала — после времени окончания перфокарты, которая в данный момент выполняется), алгоритм должен выбрать один из двух вариантов: запустить или не запускать перфокарту.

Эта динамичная программа выбирает одну из двух опций на каждом шаге, как наш дорогой друг Гамлет!

Если мой алгоритм находится на этапе i , какая информация потребуется, чтобы решить, что делать на этапе i + 1 ? Чтобы выбрать между двумя вариантами, алгоритму необходимо знать следующую совместимую перфокарту в порядке.Следующая совместимая перфокарта для данной перфокарты p — это перфокарта q , так что s_q (заданное время начала для перфокарты q ) происходит после f_p (заданное время окончания для перфокарты p ) и разница между s_q и f_p сведена к минимуму. Не говоря уже о математике, следующая совместимая перфокарта — это та, у которой время старта происходит раньше всего после завершения работы текущей перфокарты.

Если мой алгоритм находится на этапе i , какая информация ему нужна, чтобы решить, что делать на этапе i-1 ? Алгоритм должен знать о будущих решениях: решениях, принятых для перфокарт i n , чтобы решить, запускать или не запускать перфокарту i-1 .

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

Без лишних слов, вот наше повторение:

  OPT (i) = max (v_i + OPT (next [i]), OPT (i + 1))  

Это математическое повторение требует некоторых пояснений, особенно для тех, кто кто не написал ни одного раньше. Я использую OPT ( i ) для представления графика максимальных значений для перфокарт от i до n , так что перфокарты сортируются по времени начала. Знакомо, правда? OPT (•) — наша подзадача из шага 1.

Чтобы определить значение OPT ( i ), мы рассматриваем два варианта, и мы хотим взять максимум из этих вариантов, чтобы удовлетворить Наша цель: таблица значений максимум для всех перфокарт.Выбрав вариант, который дает максимальный результат на шаге i , мы запоминаем его значение как OPT ( i ).

Два варианта — запускать или не запускать перфокарту i — математически представлены следующим образом:

  v_i + OPT (next [i])  

Этот пункт представляет решение о запуске перфокарты i . Он добавляет значение, полученное при запуске перфокарты i , в OPT (следующий [ i ]), где следующий [ i ] представляет собой следующую совместимую перфокарту после перфокарты i . OPT (next [ i ]) дает расписание максимальных значений для перфокарт с следующих [ i ] по n , так что перфокарты сортируются по времени начала. Сложение этих двух значений вместе дает график максимальных значений для перфокарт с и по и , так что перфокарты сортируются по времени начала, если перфокарта и запущена.

  OPT (i + 1)  

И наоборот, этот пункт представляет решение не запускать перфокарту i .Если перфокарта i не запущена, ее значение не увеличивается. OPT ( i + 1 ) дает график максимального значения для перфокарт от i + 1 до n , так что перфокарты сортируются по времени начала. Итак, OPT ( i + 1 ) дает график максимальных значений для перфокарт от i до n , так что перфокарты сортируются по времени начала, если перфокарта i не запущена.

Таким образом, решение, принятое на каждом этапе задач перфокарты, кодируется математически, чтобы отразить подзадачу на этапе 1.

Шаг 3: Решите исходную проблему, используя шаги 1 и 2.

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

  OPT (1)  

Это так просто. Поскольку подзадача, которую мы обнаружили на шаге 1, представляет собой график максимального значения для перфокарт с i по n , так что перфокарты сортируются по времени начала, мы можем записать решение исходной проблемы в виде графика максимального значения для перфокарты с 1 по n таким образом, что перфокарты сортируются по времени начала.Поскольку шаги 1 и 2 идут рука об руку, исходную задачу также можно записать как OPT (1).

Шаг 4: Определите размеры массива мемоизации и направление, в котором он должен быть заполнен.

Шаг 3 показался вам обманчиво простым? Кажется, так оно и есть. Вы можете подумать, как OPT (1) может быть решением нашей динамической программы, если она полагается на OPT (2), OPT (next [1]) и т. Д.?

Вы правильно заметили, что OPT (1) полагается на решение OPT (2). Это следует непосредственно из шага 2:

  OPT (1) = max (v_1 + OPT (next [1]), OPT (2))  

Но это не критическая проблема.Вернемся к примеру с мемоизацией Фибоначчи. Чтобы найти значение Фибоначчи для n = 5, алгоритм полагается на тот факт, что значения Фибоначчи для n = 4, n = 3, n = 2, n = 1 и n. = 0 уже были мемоизированы. Если мы заполним нашу таблицу мемоизации в правильном порядке, зависимость OPT (1) от других подзадач не составит большого труда.

Как определить правильное направление заполнения таблицы мемоизации? В проблеме перфокарты, поскольку мы знаем, что OPT (1) полагается на решения OPT (2) и OPT (next [1]), и что перфокарты 2 и next [1] имеют время начала после перфокарты 1 из-за сортировки, мы может сделать вывод, что нам нужно заполнить нашу таблицу мемоизации от OPT ( n ) до OPT (1).

Как мы определяем размеры этого мемоизационного массива? Вот хитрость: размеры массива равны количеству и размеру переменных, на которые опирается OPT (•). В задаче перфокарты у нас есть OPT ( i ), что означает, что OPT (•) полагается только на переменную i , которая представляет номер перфокарты. Это предполагает, что наш массив мемоизации будет одномерным и что его размер будет n , поскольку всего перфокарт n .

Если мы знаем, что n = 5, то наш массив мемоизации мог бы выглядеть так:

  memo = [OPT (1), OPT (2), OPT (3), OPT (4), OPT (5 )]  

Однако, поскольку многие языки программирования начинают индексировать массивы с 0, может быть удобнее создать этот массив мемоизации, чтобы его индексы совпадали с номерами перфокарт:

  memo = [0, OPT (1), OPT (2), OPT (3), OPT (4), OPT (5)]  
Шаг 5: Закодируйте!

Чтобы закодировать нашу динамическую программу, мы объединили шаги 2–4. Единственная новая информация, которая вам понадобится для написания динамической программы, — это базовый случай, который вы можете найти, когда будете работать со своим алгоритмом.

Динамическая программа для проблемы с перфокартой будет выглядеть примерно так:

  def punchcardSchedule (n, values, next): # Инициализировать массив мемоизации - Шаг 4 memo = [0] * (n + 1) # Установить базовый случай memo [n] = values ​​[n] # Создайте таблицу мемоизации от n до 1 - Шаг 2 для i в диапазоне (n-1, 0, -1): memo [i] = max (v_i + memo [next [i] ], memo [i + 1]) # Возврат решения исходной задачи OPT (1) - Шаг 3 return memo [1]  

Поздравляю с написанием вашей первой динамической программы! Теперь, когда вы намочили ноги, я проведу вас через другой тип динамической программы.

Парадокс выбора: несколько вариантов Пример DP

Не имеет отношения к DP, но точно описывает, насколько мучительными могут быть решения с несколькими вариантами.

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

Время для нового примера.

Представьте, что вы продаете браслеты дружбы n клиентам, и ценность этого продукта монотонно растет.Это означает, что продукт имеет цены { p_1 ,…, p_n }, такие что p_i ≤ p_j , если покупатель j идет после покупателя i . У этих клиентов n есть значения { v_1 ,…, v_n }. Данный покупатель i купит браслет дружбы по цене p_i тогда и только тогда, когда p_i v_i ; в противном случае доход, полученный от этого покупателя, равен 0. Предположим, что цены — натуральные числа.

Задача : Вы должны найти набор цен, который обеспечит вам максимально возможный доход от продажи ваших браслетов дружбы.

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

Шаг 1. Определите подзадачу словами.

Подзадача : Максимальный доход, полученный от клиентов с i до n , так что цена для клиента i-1 была установлена ​​на уровне q .

Я обнаружил эту подзадачу, осознав, что для определения максимальной выручки для клиентов с 1 по n мне нужно найти ответ на следующие подзадачи:

  • Максимальный доход, полученный от клиентов n- 1 n , так что цена для клиента n-2 была установлена ​​на уровне q .
  • Максимальный доход, полученный от клиентов с n-2 по n , при этом цена для клиента n-3 была установлена ​​на уровне q .
  • (и так далее)

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

Шаг 2: Запишите подзадачу как повторяющееся математическое решение.

Есть два вопроса, которые я задаю себе каждый раз, когда пытаюсь найти повторение:

  • Какое решение я принимаю на каждом этапе?
  • Если мой алгоритм находится на шаге i , какая информация потребуется, чтобы решить, что делать на шаге i + 1 ? (А иногда: если мой алгоритм находится на шаге i , какая информация потребуется, чтобы решить, что делать на шаге i-1 ?)

Давайте вернемся к проблеме браслета дружбы и зададим эти вопросы.

Какое решение я принимаю на каждом этапе? Я решаю, по какой цене продать мой браслет дружбы текущему покупателю. Поскольку цены должны быть натуральными числами, я знаю, что я должен установить свою цену для клиента i в диапазоне от q — , цена, установленная для клиента i-1 — до v_i — максимальная цена, по которой покупатель i куплю браслет дружбы.

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

Обладая этим знанием, я могу математически записать повторяемость:

  OPT (i, q) = max ~ ([Revenue (v_i, a) + OPT (i + 1, a)])  
  такой что max ~ находит максимум по всем a в диапазоне q ≤ a ≤ v_i  

И снова это математическое повторение требует некоторого объяснения. Поскольку цена для клиента i-1 составляет q , для клиента i цена a либо остается на уровне целого числа q , либо изменяется на некоторое целое число от q + 1 до v_i .Чтобы найти общий доход, мы прибавляем доход от клиента i к максимальному доходу, полученному от клиентов i + 1 n , так что цена для клиента i была установлена ​​на уровне a .

Другими словами, чтобы максимизировать общий доход, алгоритм должен найти оптимальную цену для клиента i , проверив все возможные цены между q и v_i . Если v_i q , то цена a должна оставаться на уровне q .

А как насчет других шагов?

Выполнение шагов 1 и 2 — самая сложная часть динамического программирования. В качестве упражнения я предлагаю вам самостоятельно проработать шаги 3, 4 и 5, чтобы проверить свое понимание.

Анализ динамических программ во время выполнения

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

Обычно среда выполнения динамической программы состоит из следующих функций:

  • Предварительная обработка
  • Сколько раз запускается цикл for
  • Сколько времени требуется повторению для выполнения одной итерации цикла for
  • Пост- обработка

В целом среда выполнения имеет следующий вид:

  Предварительная обработка + цикл * повторение + постобработка  

Давайте проведем анализ проблемы перфокарты во время выполнения, чтобы познакомиться с big-O для динамических программ.Вот динамическая программа проблемы перфокарты:

  def punchcardSchedule (n, values, next): # Инициализировать массив мемоизации - Шаг 4 memo = [0] * (n + 1) # Установить мемо базового случая [n] = values ​​[ n] # Создание таблицы мемоизации от n до 1 - Шаг 2 для i в диапазоне (n-1, 0, -1): memo [i] = max (v_i + memo [next [i]], memo [i + 1 ]) # Вернуть решение исходной проблемы OPT (1) - Шаг 3 вернуть памятку [1]  

Давайте разберем его время выполнения:

  • Предварительная обработка: Здесь это означает создание массива мемоизации. О ().
  • Сколько раз запускается цикл for: O ( n ).
  • Сколько времени требуется повторению для выполнения в одной итерации цикла for: для выполнения повторения требуется постоянное время, потому что оно принимает решение между двумя вариантами в каждой итерации. О (1).
  • Постобработка: Здесь нет! О (1).

Общее время выполнения динамической программы проблемы перфокарты составляет O ( n ) O ( n ) * O (1) + O (1), или, в упрощенной форме, O ( n ).

Вы сделали это!

Ну вот и все — вы на шаг ближе к тому, чтобы стать мастером динамического программирования!

Маргарет Гамильтон: одна из многих мастеров программирования в нашей истории!

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

Так что выходите и проходите собеседования, занятия и жизнь (конечно) с вашими новообретенными знаниями динамического программирования!

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

Нравится то, что вы читаете? Поделитесь этой работой, поставив лайк и поделившись ею. Есть мысли или вопросы? Свяжитесь со мной в Твиттере или в комментариях ниже.

Что такое динамическое программирование: введение, характеристики, элементы

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

Алгоритм Divide & Conquer разбивает проблему на непересекающиеся подзадачи, рекурсивно решает подзадачи, а затем объединяет их решения для решения исходных проблем.

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

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

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

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

Характеристики динамического программирования:

Динамическое программирование работает, когда проблема имеет следующие особенности: —

  • Оптимальная подструктура: Если оптимальное решение содержит оптимальные подрешения, тогда проблема демонстрирует оптимальную подструктуру.
  • Перекрывающиеся подзадачи: Когда рекурсивный алгоритм обращается к одним и тем же подзадачам неоднократно, тогда проблема имеет перекрывающиеся подзадачи.

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

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

Если пространства подзадач достаточно (т. Е. Полиномиально от размера входных данных), динамическое программирование может быть намного более эффективным, чем рекурсия.

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

Существует три основных элемента, характеризующих алгоритм динамического программирования: —

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

Примечание. Снизу вверх означает: —

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

Компоненты динамического программирования

  1. Этапы: Проблему можно разделить на несколько подзадач, которые называются этапами.Этап — это небольшая часть данной проблемы. Например, в задаче о кратчайшем пути они определялись структурой графа.
  2. Состояния: С каждым этапом связано несколько состояний. Состояниями для проблемы кратчайшего пути был достигнут узел.
  3. Решение: На каждом этапе может быть несколько вариантов, из которых следует принять одно из лучших решений. Решение, принимаемое на каждом этапе, должно быть оптимальным; это называется этапным решением.
  4. Оптимальная политика: Это правило, определяющее решение на каждом этапе; Политика называется оптимальной, если она оптимальна в глобальном масштабе. Это известно как принцип оптимальности Беллмана.
  5. Учитывая текущее состояние, оптимальный выбор для каждого из оставшихся состояний не зависит от предыдущих состояний или решений. В задаче о кратчайшем пути необязательно было знать, как мы получили узел, только то, что мы сделали.
  6. Существует рекурсивная взаимосвязь, которая определяет оптимальные решения для этапа j, учитывая, что этап j + 1 уже решен.
  7. Заключительный этап должен решаться сам по себе.

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

Его можно разбить на четыре этапа:

  1. Охарактеризуйте структуру оптимального решения.
  2. Рекурсивно определяется значение оптимального решения. Подобно «Разделяй и властвуй», рекурсивно разделите задачу на две или более оптимальные части. Это помогает определить, как будет выглядеть раствор.
  3. Вычислить значение оптимального решения снизу вверх (начиная с самых маленьких подзадач)
  4. Постройте оптимальное решение для всей проблемы из вычисленных значений меньших подзадач.

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

  1. 0/1 ранцевая задача
  2. Задача математической оптимизации
  3. Задача кратчайшего пути для всех пар
  4. Проблема проектирования надежности
  5. Самая длинная общая подпоследовательность (LCS)
  6. Управление полетом и управление робототехникой
  7. Разделение времени: планирование задания для максимального использования ЦП

Руководство по динамическому программированию для начинающих

(Фото Криса Рида на Unsplash)

РУКОВОДСТВО ПО ПРОГРАММИРОВАНИЮ

Оптимизируйте свой код, используя несколько простых методов

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

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

Совершенно иной подход требуется для решения такого рода задач, то есть «оптимизации кода», следуя концепции динамического программирования .

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

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

Два способа применения динамического программирования:

Сверху вниз:

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

Memoize! = Запомнить

Bottom-Up:

Это эффективный способ избежать рекурсии за счет уменьшения временной сложности, которую создает рекурсия (т. Е. Затрат памяти из-за пересчета тех же значений). Здесь рассчитываются решения небольших проблем, которые составляют решение общей проблемы.(Вы получите больше ясности из примеров, объясненных далее в статье).

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

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

Помните, динамическое программирование не следует путать с рекурсией.

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

Динамическое программирование — это не что иное, как рекурсия с мемоизацией, то есть вычисление и сохранение значений, к которым впоследствии можно будет получить доступ для решения подзадач, которые возникают снова, что ускоряет ваш код и снижает временную сложность (сокращаются вычислительные циклы ЦП).

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

Начнем с базового примера ряда Фибоначчи.

Ряд Фибоначчи — это последовательность чисел таким образом, что каждое число является суммой двух предыдущих, начиная с 0 и 1.

F (n) = F (n-1) + F (n-2)

 def r_fibo (n): 
if n <= 1:
return n
else:
return (r_fibo (n-1) + r_fibo (n-2))

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

Например,

F (4) = F (3) + F (2) = ((F (2) + F (1)) + F (2) = ((F (1) + F (0)) + F (1)) + (F (1) + F (0))

В этом методе значения, подобные F ( 2) вычисляются дважды, а вызовы F (1) и F (0) выполняются несколько раз. Представьте себе количество повторений, если вам нужно вычислить его F (100). Этот метод неэффективен для больших значений.

 def fibo (n, memo): 
if memo [n]! = null:
return memo [n]
if n <= 1:
return n
else:
res = fibo (n-1) + fibo (n +1)
memo [n] = res
return res

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

 def fib (n): 
if n <= 1:
return n
list_ = [0] * (n + 1)
list_ [0] = 0
list_ [1] = 1
для i в диапазоне ( 2, n + 1):
list_ [i] = list_ [i-1] + list [i-2]
return list_ [n]

Этот код вообще не использует рекурсию. Здесь мы создаем пустой список длины (n + 1) и устанавливаем базовый случай для F (0) и F (1) в позициях индекса 0 и 1. Этот список создается для хранения соответствующих вычисленных значений с использованием цикла for. для значений индекса от 2 до n.N)

Теперь давайте посмотрим на другой пример (это задача среднего уровня):

Динамическое программирование | Блестящая вики по математике и науке

Существуют скобки типа kkk, каждая со своей открывающей и закрывающей скобками. Предположим, что первая пара обозначена числами 1 и k + 1, k + 1, k + 1, вторая — 2 и k + 2, k + 2, k + 2 и так далее. Таким образом, открывающие скобки обозначаются 1,2,…, k, 1, 2, \ ldots, k, 1,2,…, k, а соответствующие закрывающие скобки обозначаются k + 1, k + 2,…, 2k, k + 1, k + 2, \ ldots, 2k, k + 1, k + 2,…, 2k соответственно.

Некоторые последовательности с элементами из 1,2,…, 2k1, 2, \ ldots, 2k1,2,…, 2k образуют хорошо заключенные в скобки последовательности, а другие — нет. Последовательность хорошо заключена в квадратные скобки, если мы можем сопоставить или объединить открывающие скобки одного типа таким образом, чтобы выполнялось следующее:

  1. Все скобки объединены в пары.
  2. В каждой подобранной паре открывающая скобка стоит перед закрывающей.
  3. Для совпадающей пары любая другая подобранная пара находится либо полностью между ними, либо вне их.

В этой задаче вам дана последовательность скобок длиной NNN: B [1],…, B [N] B [1], \ ldots, B [N] B [1],…, B [N ], где каждый B [i] B [i] B [i] — одна из скобок. Вам также предоставляется массив значений: V [1],…, V [N] V [1], \ ldots, V [N] V [1],…, V [N].

Среди всех подпоследовательностей в массиве Values, таких, что соответствующая подпоследовательность в квадратных скобках в массиве B является последовательностью в квадратных скобках, вам необходимо найти максимальную сумму.

Задача: Решите указанную выше проблему для этого входа.6−106≤V [i] ≤106, для всех iii

  • 1≤B [i] ≤2k1 \ leq B [i] \ leq 2k1≤B [i] ≤2k, для всех iii
  • Иллюстрированные примеры

    • Для рассмотренных здесь примеров предположим, что k = 2k = 2k = 2. Последовательность 1, 1, 3 плохо заключена в квадратные скобки, так как одна из двух единиц не может быть объединена в пару. Последовательность 3, 1, 3, 1 не заключена в квадратные скобки, так как нет возможности сопоставить вторую 1 с закрывающей скобкой, стоящей после нее. Последовательность 1, 2, 3, 4 плохо заключена в квадратные скобки, поскольку согласованная пара 2, 4 не находится ни полностью между согласованной парой 1, 3, ни полностью за ее пределами.То есть совпадающие пары не могут перекрываться. Последовательность 1, 2, 4, 3, 1, 3 хорошо заключена в скобки. Мы сопоставляем первую 1 с первыми 3, 2 с 4, а вторую 1 со вторыми 3, удовлетворяя всем 3 условиям. Если вы перепишете эти последовательности, используя [, {,],} вместо 1, 2, 3, 4 соответственно, это будет совершенно ясно.

    • Предположим, что N = 6, k = 3, N = 6, k = 3, N = 6, k = 3, а значения VVV и BBB следующие: Затем квадратные скобки в позициях 1, 3 образуют последовательность в квадратных скобках (1, 4), а сумма значений в этих позициях равна 2 (4 + (-2) = 2). Скобки в позициях 1, 3, 4, 5 образуют хорошо заключенную в скобки последовательность (1, 4, 2, 5), а сумма значений в этих позициях равна 4. Наконец, скобки в позициях 2, 4, 5, 6 образуют последовательность в скобках (3, 2, 5, 6), и сумма значений в этих позициях равна 13. Сумма значений в позициях 1, 2, 5, 6 равна 16, но скобки в этих позициях (1, 3, 5, 6) не образуют четко заключенной в скобки последовательности. Вы можете проверить лучшую сумму из позиций, скобки которых образуют хорошо заключенную в скобки последовательность — 13.

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

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

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


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

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

    Если последовательность — 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)
    функция fib (n)
        если ключ n отсутствует на карте m
            m [n] = fib (n - 1) + fib (n - 2)
        вернуть m [n]
     

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

    функция fib (n)
        если n = 0
            возврат 0
        еще
            var prevFib = 0, currFib = 1
            повторить n - 1 раз
                var newFib = prevFib + currFib
                prevFib = currFib
                currFib = newFib
        вернуть currentFib
     

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

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

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

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


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

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

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

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

    Введение в динамическое программирование, Pt. Я | Дакота Лилли

    Последовательность Фибоначчи

    Это все хорошо в теории, но как это работает на самом деле? Как новичок в DP, первый пример, с которым вы неизбежно столкнетесь, — это последовательность Фибоначчи. На это есть веская причина — последовательность Фибоначчи знакома большинству людей, и вычислить ее с помощью DP довольно просто. Таким образом, это отличное место для начала.

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

    fib (n) = fib (n — 1) + fib (n — 2)

    Это классический пример рекурсии. Мы начинаем с наших базовых случаев, fib (0) = 0 и fib (1) = 1 , и далее значение каждого вызова fib равно сумме двух вызовов fib для условий, предшествующих Это. В коде реализация этой функции может выглядеть примерно так:

    Easy peasy. Но хороший ли это подход? Задавая этот вопрос, я обнаружил, что это может быть полезно на карте рекурсивного дерева алгоритма, чтобы вы действительно могли видеть, что происходит:

    Время выполнения этого алгоритма, мягко говоря, не очень хорошее. Его временная сложность составляет приблизительно 2ⁿ , или экспоненциальное время (на самом деле больше похоже на 1,6ⁿ, поскольку одна сторона дерева короче другой). Это выполнимо, в то время как наше значение для n относительно невелико, но оно быстро увеличится, и эта методология станет неприменимой. Попробуйте запустить это, чтобы вычислить значение 50-го числа Фибоначчи, и ваша программа будет зависать в течение хорошей минуты (значение также выйдет за границы, которые может представлять значение int, но это отдельная проблема).

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

    Действительно ли необходимо вычислять fib (2) пять раз? Вы уверены, что нет! Вместо этого, после того, как мы вычислим его в первый раз, мы можем просто сохранить вычисленное значение в HashMap или массиве… другими словами, мы можем запомнить его . Затем, в следующий раз, когда нам нужно будет найти это значение, мы можем просто получить его из хранилища, процесс, который занимает постоянное время (0 (1)).

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

    Какая разница! Используя динамическое программирование, мы улучшили наш алгоритм, чтобы иметь линейную временную сложность всего O (n), что является значительным улучшением по сравнению с экспоненциальной временной сложностью, которую мы имели раньше. (Хотите верьте, хотите нет, но на самом деле это не самый быстрый способ вычисления числа в последовательности Фибоначчи — есть другие методы, которые занимают только логарифмическое время).

    Как бы вы на самом деле реализовали это в коде? Что ж, давайте запишем это:

    Это в основном то же самое, что и раньше, за исключением того, что мы добавили массив int [] memo , в который мы вставляем результат для определенного значения n. Теперь, прежде чем вычислять результат с помощью рекурсивных вызовов fib, мы сначала проверяем, существует ли уже результат для данного числа. (Проверка выставлена ​​на ноль, потому что когда массив создается в Java, он заполняется нулями. Имейте в виду, что, поскольку массивы в Java имеют статический размер, вам необходимо инициализировать этот массив размером n + 1 .)

    И готово! Ваш самый первый алгоритм динамического программирования!

    Страница не найдена | MIT

    Перейти к содержанию ↓
    • Образование
    • Исследование
    • Инновации
    • Прием + помощь
    • Студенческая жизнь
    • Новости
    • Выпускников
    • О MIT
    • Подробнее ↓
      • Прием + помощь
      • Студенческая жизнь
      • Новости
      • Выпускников
      • О MIT
    Меню ↓ Поиск Меню Ой, похоже, мы не смогли найти то, что вы искали!
    Попробуйте поискать что-нибудь еще! Что Вы ищете? Увидеть больше результатов

    Предложения или отзывы?

    .