Что такое динамическое программирование? [закрытый]

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

Хороший пример - решение последовательности Фибоначчи для n = 1 000 002.

Это будет очень долгий процесс, но что, если я дам вам результаты для n = 1 000 000 и n = 1 000 001? Внезапно проблема стала более управляемой.

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

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

В книге Cormen Algorithms есть отличная глава о динамическом программировании. И это бесплатно в Google Книгах! Посмотрите здесь.

Мемоизация - это когда вы сохраняете предыдущие результаты вызова функции (реальная функция всегда возвращает одно и то же, учитывая те же входные данные). Это не имеет значения для алгоритмической сложности до того, как результаты будут сохранены.

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

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

• Алгоритмы DP могут быть реализованы с рекурсией, но у них нет быть.
• Алгоритмы DP не могут быть ускорены с помощью мемоизации, поскольку каждая подзадача решается (или вызывается функция "решения") только один раз.

Ключевыми элементами динамического программирования являются «перекрывающиеся подзадачи» и «оптимальная подструктура». Эти свойства проблемы означают, что оптимальное решение состоит из оптимальных решений его подзадач. Например, задачи кратчайшего пути демонстрируют оптимальную подструктуру. Кратчайший путь от A к C - это кратчайший путь от A к некоторому узлу B, за которым следует кратчайший путь от этого узла B к C.

Более подробно, чтобы решить задачу кратчайшего пути, вы:

• find расстояния от начального узла до каждого соприкасающегося с ним узла (скажем, от A до B и C)
• найдите расстояния от этих узлов до узлов, соприкасающихся с ними (от B до D и E, и от C до E и F)
• теперь мы знаем кратчайший путь от A до E: это кратчайшая сумма Ax и xE для некоторого узла x, который мы посетили (либо B, либо C)
• повторяем этот процесс, пока не достигнем конечного узла назначения

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

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

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

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

Это оптимизация вашего алгоритма, которая сокращает время выполнения.

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

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

Вот пример задачи, которая подходит для динамического программирования, от онлайн-судьи UVA: Edit Steps Ladder.

Я собираюсь сделать краткий брифинг по важной части анализа этой проблемы, взято из книги «Проблемы программирования», я предлагаю вам проверить это.

Внимательно посмотрите на эту проблему: если мы определим функцию стоимости, сообщающую нам, насколько далеко находятся две строки, у нас есть две, которые рассмотрят три естественных типа изменений :

Замена - изменение одного символа из шаблона «s» на другой символ в тексте «t», например изменение «выстрел» на «пятно».

Вставка - вставьте один символ в шаблон «s», чтобы он соответствовал тексту «t», например, измените «назад» на «agog».

Удаление - удалите один символ из шаблона «s», чтобы помочь он соответствует тексту «t», например, изменяет «час» на «наш».

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

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

 #define MATCH 0 / * символ перечислимого типа для совпадения * /
#define INSERT 1 / * символ перечислимого типа для вставки * /
#define DELETE 2 / * символ перечислимого типа для удаления * /


int string_compare (char * s, char * t, int i, int j)

{

int k; / * счетчик * /
int opt ​​[3]; / * стоимость трех вариантов * /
int low_cost; / * самая низкая стоимость * /
 если (я == 0) возврат (j * indel (''));
 если (j == 0) return (i * indel (''));
 opt [MATCH] = string_compare (s, t, i-1, j-1) +
 совпадение (s [i], t [j]);
 opt [INSERT] = string_compare (s, t, i, j-1) +
 indel (t [j]);
 opt [DELETE] = string_compare (s, t, i-1, j) +
 indel (s [i]);
 low_cost = opt [MATCH];
 для (k = INSERT; k <= DELETE; k ++)
 если (opt [k] 

Этот алгоритм правильный, но он также невероятно медленный.

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

Почему алгоритм такой медленный? Это занимает экспоненциальное время, потому что вычисляет значения снова и снова. В каждой позиции в строке рекурсия разветвляется по трем направлениям, что означает, что она растет со скоростью не менее 3 ^ n - на самом деле, даже быстрее, поскольку большинство вызовов сокращают только один из двух индексов, а не оба из них.

Так как же сделать алгоритм практичным? Важное наблюдение состоит в том, что большинство этих рекурсивных вызовов вычисляют вещи, которые уже были вычислены ранее. Откуда нам знать? Что ж, может быть только | s | · | T | возможные уникальные рекурсивные вызовы, избегайте их пересчета и просто посмотрите их вверх по мере необходимости.

Таблица представляет собой двумерную матрицу m, где каждое из | s | · | t | cell содержит стоимость оптимального решения этой подзадачи, а также родительский указатель, объясняющий, как мы попали в это место:

 typedef struct {
int стоимость; / * стоимость достижения этой ячейки * /
int parent; / * родительская ячейка * /
} ячейка;

ячейка m [MAXLEN + 1] [MAXLEN + 1]; / * таблица динамического программирования * /

Версия динамического программирования имеет три отличия от рекурсивной версии.

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

** Во-вторых, ** он обновляет родительское поле каждой ячейки, что позволит нам реконструировать последовательность редактирования позже.

** В-третьих, ** В-третьих, это оснащено функцией более общей цели cell () вместо простого возврата m [ | s |] [| t |]. стоимость. Это позволит нам применить эту процедуру к более широкому классу проблем.