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



Контур

  1. Методы решения задач и задачи оптимизации
  2. Знакомство DP с примером резки стержня
  3. Иллюстрация DP с помощью примера самой длинной общей подпоследовательности
  4. Резюме и комментарии по оптимальной субструктуре

Чтения и скринкасты

  • Прочтите всю главу 15 CLRS. Основное внимание уделяется стратегии решения задач: Читайте примеры прежде всего для того. Чтобы понять стратегию динамического программирования, а не для того. Чтобы запомнить специфику каждой задачи (хотя вам будет предложено проследить некоторые алгоритмы).
  • Я также опубликовал главу Седжвика в

    В этом случае я не думаю, что Седжвик более ясен, чем Кормен и др. Пример резки стержней в Cormen et al. довольно хорошо иллюстрирует основы ДП. Кроме того, хотя обычно сначала легче понять примеры, примеры DP включают утомительные комбинации подзадач. Поэтому в этом случае вам лучше попытаться сначала понять суть стратегии.

  • Скринкасты 12A, 12B, 12C, 12D (также в Лаулиме)


Установка контекста

Методы Решения Проблем

В этом курсе мы изучаем множество хорошо определенных алгоритмов, в том числе (пока что) алгоритмы для ADT. Сортировки и поиска. А также другие алгоритмы для работы с графами.

Существуют качественные реализации с открытым исходным кодом: вам часто не нужно их реализовывать.

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

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

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

Задачи оптимизации

Задача оптимизации требует нахождения

Динамическое программирование-это один из нескольких методов. Которые мы рассмотрим. (Жадные алгоритмы и линейное программирование также могут быть применимы к задачам оптимизации.)

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

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

Это звучит знакомо: разделяй и властвуй также объединяет решения подзадач, но применяется. Когда подзадачи не пересекаются. Например, вот дерево рекурсии для сортировки слиянием по массиву A[1..8]. Обратите внимание. Что индексы на каждом уровне не перекрываются):

Динамическое программирование применяется. Когда подзадачи накладываютсядруг на друга . Например, вот дерево рекурсии для задачи Обратите внимание. Что повторяются не только длины, но и целые поддеревья. Было бы излишним повторять вычисления в этих поддеревьях.

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

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


Пример: Резка Стержня

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

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

Вход: Длина n и таблица цен pi для i = 1, 2, …, n.

Выход: Максимальный доход , доступный для стержней, длина которых равна n, вычисляется как сумма цен на отдельные стержни.

Мы можем выбрать вырезать или не вырезать в каждой из n-1 единиц измерения. Поэтому можно разрезать стержень 2n-1 способами. Очевидно. Что мы не хотим тестировать все эти возможные решения, если мы можем найти кратчайший путь.

Если pn достаточно велик, оптимальное решение может не потребовать сокращений.

Пример экземпляра проблемы

Вот пример таблицы цен на стержни длиной до 8 футов.

Предположим, у нас есть стержень длиной 4. Есть 2n-1 = 23 = 8 способов разрезать его вверх (цифры показывают цену. Которую мы получаем за каждую длину. Исходя из приведенного выше графика):

Перечислив все решения, мы видим. Что для стержня длиной 4 мы получаем наибольший доход. Разделив его на две единицы длиной 2 каждая: р2 + р2 = 5 + 5 = 10.

Оптимальная подструктура стержневой резки

Претензия: Оптимальное решение общей задачи должно включать в себя оптимальное решение этой подзадачи.

Доказательство: Доказательство-это доказательство

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

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

Продолжая пример

Вот таблица ri, максимального дохода для стержня длины i, для этого примера задачи.

Чтобы решить задачу размера 7, найдите наилучшее решение для подзадач размера 7; 1 и 6; 2 и 5; или 3 и 4. Каждая из этих подзадач также обладает оптимальной субструктурой.

Одним из оптимальных решений является разрез на 3 см, дающий две подзадачи длиной 3 см и 4 см. Нам нужно решить оба вопроса оптимально. Оптимальным решением для стержня длиной 3 см является отсутствие разрезов. Как мы видели выше, оптимальное решение для стержня длиной 4 см заключается в разрезании на 2 части. Каждая длиной 2 см. Эти подзадачи оптимальных решений затем используются в решении задачи 7 см стержня.

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

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

Для любой длины стержня nмы можем определить оптимальные доходы rn , взяв максимум:

  • пн.: цена. Которую мы получаем, не делая сокращения,
  • r1 + rn-1: максимальная выручка от стержня 1см и стержня n-1см,
  • r2 + rn-2: максимальная выручка от стержня 2см и стержня n-2см, ….
  • rn-1 + r1

Итак, rn = max (pn, r1 + rn-1, r2 + rn-2, … rn-1 + r1 ).

В этом уравнении есть избыточность: если мы решили для ri и rni, нам также не нужно решать для rni и ri.

Более Простая Декомпозиция

Вместо того чтобы рассматривать все способы разделить стержень пополам. Оставив две подзадачи. Рассмотрите все способы отрезать первый кусок длины i, оставив только одну подзадачу длины ni:

Мы не знаем заранее, какой должна быть первая часть длины i, но мы знаем. Что один из них должен быть оптимальным выбором. Поэтому мы пробуем их все.

Рекурсивное Нисходящее Решение

Приведенное выше уравнение сразу же приводит к прямой рекурсивной реализации (p-это вектор цены. Поэтому p[i] — это цена. Которую вы получаете за стержень длины i; n-размер задачи или общая длина данного стержня):

Это работает, но неэффективно. Он неоднократно называет себя по подзадачам, которые он уже решил (обведен). Вот дерево рекурсии для n = 4:

Фактически мы можем показать. Что этот рост носит экспоненциальный характер. Пусть T(n) — количество обращений к Cut-Rod со вторым параметром = n.

Начальная цифра 1 предназначена для корневого вызова. А T(j) подсчитывает рекурсивные вызовы в строке 5. Это имеет решение 2n. (Используйте индуктивную гипотезу. Что она справедлива для j

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

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

Сверху вниз с запоминанием

Запоминание-это воспоминание того, что мы вычислили ранее. Мы модифицируем рекурсивный алгоритм для хранения и поиска результатов в таблице r:

Подход Он имеет недостаток накладных расходов рекурсии (и алгоритм не является хвост-рекурсивным. Поэтому не может быть преобразован в итерацию компилятором).

Снизу вверх

Можно также отсортировать подзадачи по

Например, здесь мы снова используем таблицу r, но мы организуем (через цикл в строке 3) сначала решение наименьшей задачи. А затем последовательно более крупных задач. Так что мы всегда знаем. Что меньшие решения доступны. Ссылка на массив r[ji] гарантирует , что мы ссылаемся только на подзадачи меньше j, над которыми мы сейчас работаем.

Подход Подход

Асимптотическое время работы

Как нисходящая, так и восходящая версии выполняются за время Θ(n2).

  • Снизу вверх: существуют дважды вложенные циклы, и число итераций для внутреннего цикла образует арифметический ряд.
  • Сверху вниз: Каждая подзадача решается только один раз. Подзадачи решаются для размеров 0, 1, … n. Чтобы решить подзадачу размера n, цикл for в строке 6 Memomized-Cut-Rod повторяется n раз. Поэтому для всех рекурсивных вызовов общее число итераций представляет собой арифметический ряд. (Здесь используется агрегатный анализ. Рассмотренный в следующей лекции.)

Построение решения

Приведенные выше программы возвращают значение оптимального решения. Чтобы построить само решение, нам нужно записать выбор. Который привел к оптимальным решениям. Используйте таблицу s для записи места, где был сделан оптимальный разрез (сравните с разрезом снизу вверх-Стержень):

Для нашей задачи входные данные и построенные таблицы являются:

Затем мы проследим сделанный выбор обратно через таблицу s с помощью этой процедуры:

Упражнение: Проследите вызовы, сделанные Print-Cut-Rod-Solution(p, 8)


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

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

  1. Охарактеризуйте структуру оптимального решения:

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

    • Напишите рекурсивную функцию затрат. Которая отражает приведенную выше структуру
    • Пример: показанное рекуррентное соотношение
  3. Вычислите значение оптимального решения:

    • Напишите код для вычисления рекурсивных значений, запоминая или решая сначала более мелкие задачи. Чтобы избежать избыточных вычислений
    • Пример: Bottom-Up-Cut-Rod
  4. Построить оптимальное решение на основе вычисленной информации:

    • Дополняйте код по мере необходимости для записи структуры решения
    • Пример: Extended-Bottom-Up-Cut-Rod и Print-Cut-Rod-Решение

Эти шаги проиллюстрированы в следующем примере.


Пример: Самая длинная Общая подпоследовательность

Подпоследовательность последовательности S оставляет ноль или более элементов, но сохраняет порядок.

Zобщая подпоследовательность X и Y, если Z-подпоследовательность как X, так и Y.
Zсамая длинная общая подпоследовательность, если она является подпоследовательностью максимальной длины.

Проблема LCS

Учитывая две последовательности X = ⟨ x1, …, xm ⟩ и Y = ⟨ y1, …, yn ⟩, найдите общую для обеих подпоследовательность. Длина которой является самой длинной. Решения этой проблемы имеют приложения к анализу ДНК в биоинформатике. Анализ оптимальной субструктуры элегантен.

Примеры

Алгоритм грубой силы для LCS

Для каждой подпоследовательности X = ⟨ x1, …, xm⟩ проверьте. Является ли она подпоследовательностью Y = ⟨ y1, …, yn ⟩, и запишите ее. Если она длиннее самой длинной из ранее найденных.

  • Существует 2m подпоследовательностей X для проверки.
  • Для каждой подпоследовательности сканируйте Y на первую букву. Оттуда сканируйте вторую букву и т. Д., Вплоть до n букв Y.
  • Следовательно, Θ(n2m).

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

  • Если подпоследовательность Z из X не совпадает с Y, то любая подпоследовательность, имеющая Z в качестве префикса. Также потерпит неудачу.
  • Если подпоследовательность Z из X совпадает с Y, то нет необходимости проверять префиксы Z.

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

Шаг 1. Оптимальная субструктура ЛКС

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

Часто при решении проблемы мы начинаем с того, что известно, а затем выясняем, как построить решение. Оптимальный анализ субструктуры использует обратную стратегию: предположим, вы нашли дополнительное решение (Z ниже) и выяснили. Что вы должны были сделать. Чтобы получить его!

Обозначение:

  • Xi = префикс ⟨ x1, …, xi
  • Yi = префикс ⟨ y1, …, yi

Теорема: пусть Z и = ⟨ з1, …, ЗК ⟩ быть любой НОП Х = ⟨ Х1, …, хм ⟩ и г = ⟨ г1, …, гп ⟩. Затем

  1. Если ХМ = мн, затем ЗК = ХМ = МНИ ЗК-1 является НОП хм-1 и ГП-1.
    (Если последние символы х и М совпадают. То эти знаки также являются последним символом из LCS з, поэтому мы можем отбросить последние характер всех трех и продолжить рекурсивно по префиксу.)
  2. Если xmyn, то zkxmZ-LCS Xm-1 и Y.
  3. Если ХМY ин, затем Зи кгнз является НОП х и ГП-1.
    (Если последние символы х и Г не совпадают друг с другом. Затем префиксом Z не должно быть в подстрок. Не связанных с этими персонажами. Ироме того. Мы можем использовать последний знак Z и определить. Какой из них она находится.)

Эскиз доказательств:

(1) может быть доказано противоречием: если последние символы X и Y не включены в Z, то более длинная LCS может быть построена путем добавления этого символа к Z, противоречию.

(2) и (3) имеют симметричные доказательства: Предположим, что существует подпоследовательность W из Xm-1 и Y (или из X и Yn-1k. Тогда W-это общая подпоследовательность X и Y, противоречащая тому. Что Z является LCS.

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

Теперь мы можем использовать этот факт, построив рекурсивную формулу для значения LCS (Обратите внимание. Что я сказал: Слишком часто студенты пытаются решить каждый шаг, игнорируя то, что они сделали на предыдущем шаге!)

Шаг 2. Рекурсивная формулировка значения LCS

Пусть c[i, j] — длина LCS префиксов Xi и Yj. Приведенная выше рекурсивная подструктура приводит к определению с:

Прежде чем продолжить, вы должны определить соответствие между частями вышеприведенной теоремы и определением c[i, j], приведенным выше. Так как вам придется делать подобные переводы каждый раз. Когда вы решаете задачу динамического программирования!

Теперь мы готовы написать код для поиска c[m, n].

Шаг 3. Вычислите значение оптимального решения для LCS

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

Динамическое программирование позволяет избежать избыточных вычислений, сохраняя результаты в таблице. Мы используем c[i,j] для длины LCS префиксов Xi и Yj (следовательно, она должна начинаться с 0).

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

Это решение снизу вверх: индексы i и j увеличиваются через циклы, а ссылки на c всегда включают либо i-1, либо j-1, поэтому необходимые подзадачи уже вычислены.

Это явно Θ(mn); гораздо лучше, чем Θ(n2m)!

Шаг 4. Построить оптимальное решение для LCS

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

Таблица b[i, j] обновляется выше, чтобы запомнить, является ли каждая запись

  • общая подстрока Xi-1 и Yj-1 (диагональная стрелка), в этом случае общий символ xi = yj включается в LCS;
  • общая подстрока Xi-1 и Y (↑); или
  • общая подстрока X и Yj-1 (←).

Мы восстанавливаем путь , вызывая Print-LCS(b, X, n, m) и следуя стрелкам, выводя символы X, соответствующие диагональным стрелкам (a Θ(n + m), проходящим от нижнего правого края матрицы к началу координат):

Пример LCS

Что общего между Используйте Print-LCS, чтобы узнать это!


Другие Приложения

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

Оптимизация Матрично-Цепного Умножения

Многие научные и бизнес-приложения включают умножение цепочек матриц ⟨ A1, A2, A3, … An ⟩. Поскольку матричное умножение ассоциативно. Матрицы могут быть умножены на их соседей в этой последовательности в любом порядке. Выбранный порядок может иметь огромную разницу в количестве требуемых умножений. Например, предположим, что у вас есть матрица A, a 2×100, B (100×100) и C (100×20). Чтобы вычислить A*B*C:

(A*B) требует 2*100*100 = 20000 умножений, и получается матрица 2х100. Затем нужно умножить на C: 2*100*20 = 4000 умножений. В общей сложности 24 000 умножений (и результат 2х20).

(B*C) требует умножения 100x100x20 = 200000 и приводит к матрице 100×20. Затем нужно умножить на A: 2*100*20 = 4000 умножений. В общей сложности 204 000 умножений (и тот же результат 2х20).

Поэтому мы определенно должны умножать (A*B)*C, а не A*(B*C)!

Задача умножения матричной цепи состоит в том. Чтобы определить оптимальный порядок умножения (а не в том. Чтобы на самом деле делать умножения!!Для трех матриц мне удалось вычислить наилучшую последовательность вручную, но некоторые проблемы в науке. Бизнесе и других областях включают в себя много матриц. И число комбинаций. Подлежащих проверке. Растет экспоненциально: решение грубой силы равно Ω(2n ). Учебник CLRS разрабатывает решение динамического программирования. Которое выполняется за время Θ(n3) и использует пространство Θ(n2).

Планирование матричного умножения-это, пожалуй, самый Вместо этого я решил представить LCS. Потому что оптимизация матричного умножения будет встроена в готовое программное обеспечение. А нынешние студенты. Скорее всего. Будут заинтересованы в приложениях биоинформатики

Оптимальное Бинарное Дерево Поиска

В разделе 8 мы видели, что неправильный порядок вставок ключей в двоичное дерево поиска (BST) может привести к низкой производительности (например. Линейной по n). Если мы заранее знаем все ключи а также вероятность того что их будут искать, мы можем оптимизировать конструкцию BST. Чтобы минимизировать время поиска в совокупности по ряду запросов. Пример приложения-это когда мы хотим построить словарь из набора терминов. Которые известны заранее вместе с их частотой в языке. (Обратите внимание. Что это отличается от построения сбалансированного BST. Который является оптимальным только в том случае. Если все ключи с одинаковой вероятностью будут найдены.)

Существуют бинарные деревья Ω(4n / n3/2) с n узлами. Каждый из которых может получить законное назначение ключей узлам. Поэтому очевидно. Что подход грубой силы будет экспоненциальным во времени. Учебник CLRS разрабатывает решение динамического программирования. Которое является Θ(n3). Студенту достаточно попробовать задачу 15.5-2 из текста Cormen et al. (ручное моделирование алгоритма), чтобы понять. Почему мы хотим оставить эту скуку компьютерам!


Дальнейшие Наблюдения Относительно Оптимальной Субструктуры

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

Оптимальный выбор не известен до решения подзадач

Мы можем не знать, что это за первый выбор. Следовательно:

  • Чтобы показать. Что существует оптимальная подструктура, мы предполагаем, что выбор был сделан, и показываем. Что подзадачи. Которые в результате должны быть решены оптимально. Этот аргумент часто делается с использованием доказательства вырезания и вставки противоречием.
  • Затем при написании кода мы должны убедиться, что достаточно потенциальных вариантов и, следовательно. Их суперпроблемы рассматриваются. Чтобы мы нашли оптимальный первый выбор. Это обычно проявляется как итерация. В которой мы находим максимум или минимум в соответствии с некоторой целевой функцией во всех вариантах.

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

Количество подзадач. Используемых в оптимальном решении, может варьироваться:

  • Резка стержня: 1 подзадача (размер ni)
  • LCS: 1 подзадача (LCS префиксной последовательности(ов).)
  • Оптимальный BST: 2 подзадачи (учитывая, что kr был выбран в качестве корня, ki …, kr-1 и kr+1 …, kj)

Сколько вариантов выбора при определении того, какую подзадачу(ы) использовать, может варьироваться:

  • Резка стержня: n вариантов (для каждого значения i)
  • LCS: Либо 1 выбор (если xi = yj, возьмите LCS Xi-1 и Yj-1), либо 2 варианта (если xiyj, проверьте оба LCS Xi-1 и Y, а также LCS X и Yj-1)
  • Оптимальный BST: ji + 1 выбор для корня kr в ki …, kj: см. текст.

Неофициально время выполнения зависит от (# подпроблем в целом) x (# вариантов).

  • Резка стержня: Θ(n) подпроблемы в целом, ≤ n вариантов для каждого ⇒ O(n2) времени выполнения.
  • LCS: Θ(mn) подпроблемы в целом; ≤ 2 выбора для каждого ⇒ O(mn) времени выполнения.
  • Оптимальное BST: Θ(n2) подзадачи в целом; O(n) выбор для каждого ⇒ O(n3) время выполнения.

(У нас будет лучшее понимание

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

Не все задачи оптимизации имеют оптимальную подструктуру

Когда мы изучаем графики, мы увидим. Что нахождение кратчайшего пути между двумя вершинами в графе имеет оптимальную подструктуру: если p = p1 + p2 является кратчайшим путем между u и v, то p1 должен быть кратчайшим путем между u и w (и т. Д.). Доказательство вырезанием и вставкой.

Но нахождение самого длинного простого пути (самого длинного пути. Не повторяющего никаких ребер) между двумя вершинами вряд ли будет иметь оптимальную подструктуру. (Самый длинный простой путь-NP-полный, тема. Которую мы рассмотрим в конце семестра. Поэтому вряд ли у нас будет какое-либо эффективное решение.)

Например, qstr-самый длинный простой путь от q до r, но qs не является самым длинным простым путем для подзадачи от q до s (qrts), поэтому она не демонстрирует оптимальную подструктуру. Кроме того, если мы попытаемся составить оптимальные решения qstr и rqst , чтобы получить самый длинный простой путь от r до t, составленный путь даже не является законным: критерий простоты нарушается.

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

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

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


Краткие сведения

Динамическое программирование применяется тогда. Когда задача имеет следующие характеристики:

Рекурсивная декомпозиция
Задача имеет рекурсивную структуру: она распадается на более мелкие задачи того же типа. Эта характеристика является общей для divide and conquer. Но динамическое программирование отличается от divide and conquer следующим пунктом.

Перекрывающиеся Подзадачи
Подзадачи, решаемые рекурсивным решением. Перекрываются (одни и те же подзадачи пересматриваются несколько раз). Это означает. Что мы можем сэкономить время, предотвращая избыточные вычисления.

Оптимальная Субструктура
Любое оптимальное решение включает в себя выбор. Который оставляет одну или несколько подзадач для решения. И решения подзадач. Используемые в рамках оптимального решения. Сами должны быть оптимальными. Это означает. Что оптимизированные рекурсивные решения могут быть использованы для построения оптимизированных больших решений.

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

К динамическому программированию можно подходить сверху вниз или снизу вверх:

Сверху вниз с мемуаризацией:
Напишите рекурсивную процедуру для решения задачи. Вычисляя подзадачи по мере необходимости. Каждый раз. Когда возникает подзадача, посмотрите, сохранили ли вы ее в таблице, и если нет. Решите ее и сохраните решение.

Снизу Вверх:
Расположите подзадачи так. Чтобы (Этот порядок не должен основываться на литеральном размере.)

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

Мы решаем эту проблему с помощью динамического программирования в четыре этапа:

  1. Охарактеризуйте структуру оптимального решения:

    • Как оптимальные решения складываются из оптимальных решений подзадач?

  2. Рекурсивно определите значение оптимального решения:

    • Напишите рекурсивную функцию затрат. Которая отражает приведенную выше структуру

  3. Вычислите значение оптимального решения:

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

  4. Построить оптимальное решение из вычисленной информации:

    • Дополните код по мере необходимости для записи структуры решения


Обертка

Существует онлайн-презентация, посвященная LCS на http://www.csanimated.com/animation.php?t=Dynamic_programming

В следующем разделе 13 мы рассмотрим соответствующую стратегию оптимизации: жадные алгоритмы.


Dan Suthers

Последнее изменение: Ср. 11 ноября 03:32:54 HST 2020
Изображения взяты из материала инструктора для Cormen et al. Введение в алгоритмы. Третье издание.