Я не могу понять принципы динамического программирования, и я действительно этого хочу. DP очень мощный, он может решить такие проблемы:
Получение минимально возможной суммы из разницы чисел
Итак, можете ли вы предложить мне хорошие книги или статьи (желательно с примерами с реальным кодом), которые объяснят мне, что такое динамическое программирование? В первую очередь мне нужны простые примеры, затем я перейду.
Динамическое программирование - полезный тип алгоритма, который можно использовать для оптимизации жестких задач, разбивая их на более мелкие подзадачи. Сохраняя и повторно используя частичные решения, ему удается избежать ловушек использования жадного алгоритма. Существует два типа динамического программирования: снизу вверх и сверху вниз.
Для решения проблемы с помощью динамического программирования проблема должна обладать свойством того, что называется оптимальной подструктурой. Это означает, что если проблема была разбита на ряд подзадач и было найдено оптимальное решение для каждой подзадачи, то полученное решение будет реализовано через решение этих подзадач. Проблема, которая не имеет такой структуры, не может быть решена с помощью динамического программирования.
Сверху вниз более известный как memoization. Это идея хранения прошлых вычислений, чтобы избежать повторного вычисления их каждый раз.
Учитывая рекурсивную функцию, скажем:
fib(n) = 0 if n = 0
1 if n = 1
fib(n - 1) + fib(n - 2) if n >= 2
Мы можем легко записать это рекурсивно из его математической формы как:
function fib(n)
if(n == 0 || n == 1)
n
else
fib(n-1) + fib(n-2)
Теперь, любой, кто программировал какое-то время или что-то знает об эффективности алгоритма, скажет вам, что это ужасная идея. Причина в том, что на каждом шаге вы должны пере рассчитать значение fib (i), где я равно 2..n-2.
Более эффективным примером этого является сохранение этих значений, создание алгоритма динамического программирования сверху вниз.
m = map(int, int)
m[0] = 0
m[1] = 1
function fib(n)
if(m[n] does not exist)
m[n] = fib(n-1) + fib(n-2)
Таким образом, мы вычисляем fib (i) не более одного раза.
Внизу вверх используется тот же метод memoization, который используется в нисходящем порядке. Разница, однако, заключается в том, что снизу-вверх использует сравнительные под-проблемы, известные как повторяющиеся, для оптимизации вашего конечного результата.
В большинстве проблем с восходящим динамическим программированием вы часто пытаетесь либо минимизировать, либо максимизировать решение. Вам предоставляется два (или более) варианта в любой момент, и вам нужно решить, что более оптимально для проблемы, которую вы пытаетесь решить. Однако эти решения основаны на предыдущих вариантах, которые вы сделали.
Принимая наиболее оптимальное решение в каждой точке (каждая подзадача), вы убедитесь, что ваш общий результат является наиболее оптимальным.
Наиболее сложной частью этих проблем является поиск повторяющихся отношений для решения вашей проблемы.
Чтобы заплатить за кучу учебников алгоритмов, вы планируете ограбить магазин, в котором есть n предметов. Проблема в том, что ваш крошечный рюкзак может содержать не более W кг. Зная вес (w [i]) и значение (v [i]) каждого элемента, вы хотите максимизировать ценность своих похищенных товаров, которые вместе весит не более W. Для каждого элемента вы должны сделать двоичный выбор - возьмите его или оставьте.
Теперь вам нужно найти, что такое подзадача. Вы являетесь очень ярким вором, вы понимаете, что максимальное значение данного элемента я с максимальным весом w может быть представлено m [i, w]. Кроме того, m [0, w] (0 элементов с наибольшим весом w) и m [i, 0] (i элементов с максимальным весом 0) всегда будет равным 0.
поэтому
m[i, w] = 0 if i = 0 or w = 0
С вашей мыслящей маской на лицевой стороне вы заметите, что если вы наполнили свою сумку с таким же весом, как можете, новый предмет нельзя рассматривать, если его вес меньше или равен разнице между вашим максимальный вес и текущий вес мешка. Другим случаем, когда вы можете рассмотреть элемент, является то, что он имеет меньше или равно вес предмета в сумке, но больше значения.
m[i, w] = 0 if i = 0 or w = 0
m[i - 1, w] if w[i] > w
max(m[i - 1, w], m[i - 1, w - w[i]] + v[i]) if w[i] <= w
Это рекуррентные соотношения, описанные выше. Когда у вас есть эти отношения, писать алгоритм очень легко (и коротко!).
v = values from item1..itemn
w = weights from item1..itemn
n = number of items
W = maximum weight of knapsack
m[n, n] = array(int, int)
function knapsack
for w=0..W
m[0, w] = 0
for i=1 to n
m[i, 0] = 0
for w=1..W
if w[i] <= w
if v[i] + m[i-1, w - w[i]] > m[i-1, w]
m[i, w] = v[i] + m[i-1, w - w[i]]
else
m[i, w] = m[i-1, w]
else
m[i, w] = c[i-1, w]
return m[n, n]
К счастью, динамическое программирование стало действительно актуальным, когда речь заходит о конкурентном программировании. Ознакомьтесь с Динамическое программирование на UVAJudge для некоторых практических проблем, которые будут проверять вашу способность реализовывать и находить рецидивы для задач динамического программирования.
Короче говоря, динамическое программирование - это метод решения сложных задач, разбивая их на более простые этапы, т.е. путем решения проблемы шаг за шагом.
Я надеюсь, что эти ссылки помогут хотя бы немного.
Начните с
Если вы хотите проверить себя, мои выборы в онлайн-судьях
и, конечно,
Вы также можете проверить курсы курсов университетов хорошего качества
В конце концов, если вы не можете решить проблемы, спросите, что существует много аддикторов алгоритмов здесь
См. ниже
и слишком много примеров и статей ссылаются на статью выше.
После изучения динамического программирования вы можете улучшить свои навыки, решив проблемы UVA. Есть списки некоторые проблемы динамического программирования UVA в разделе из UVA
Также Wiki имеет хорошие простые образцы для него.
Edit: для алгоритма книги об этом вы можете использовать:
Также вы должны взглянуть на Memoization в динамическом программировании.
Я думаю Алгебраическое динамическое программирование Стоит отметить. Это довольно вдохновляющее представление технологии DP и широко используется в сообществе биоинформатики. Кроме того, принцип оптимальности Беллмана изложен очень понятным образом.
Традиционно DP преподается на примере: алгоритмы приведены в терминах повторений между табличными записями, которые хранят решения промежуточных проблем, из этой таблицы общее решение построено с помощью некоторого анализа случаев.
ADP организует алгоритм DP, так что разложение проблемы на подзадачи и анализ случаев полностью отделен от предполагаемой оптимизации задача. Это позволяет повторно использовать и комбинировать различные части алгоритмов DP для подобных проблем.
В алгоритме ADP имеется три слабо связанных элемента:
Все эти части затем автоматически соединяются вместе, обеспечивая эффективный алгоритм.
Эта статья USACO является хорошей отправной точкой для понимания основ DP и того, как она может дать огромные ускорения. Затем просмотрите эту статью Topcoder, которая также охватывает основы, но не написана так хорошо. Этот учебник из CMU также очень хорош. Как только вы это поймете, вам нужно будет совершить прыжок в 2D DP, чтобы решить проблему, о которой вы говорите. Прочитайте эту статью Topcoder до и включив вопрос о яблоках (помеченный как промежуточный).
Вы также можете найти эту лекцию видео MIT, в зависимости от того, насколько хорошо вы выбираете вещи из видео.
Также имейте в виду, что вам нужно будет полностью понять рекурсию, прежде чем вы сможете успешно получить DP. DP трудно! Но реальная трудная часть видит решение. После того, как вы поймете концепцию DP (к которой вы должны привести это выше), вы даете эскиз решения (например, мой ответ на ваш вопрос, то это действительно не так сложно применять, поскольку решения DP, как правило, очень кратки и не слишком далеки от итеративных версий более понятного рекурсивного решения.
Вы также должны взглянуть на memoization, которые некоторые люди считают более понятными, но часто так же эффективны, как и DP, Чтобы кратко объяснить, memoization принимает рекурсивную функцию и кэширует ее результаты, чтобы сохранить повторное вычисление результатов для тех же аргументов в будущем.
Поскольку никто еще не упомянул об этом, необходимы свойства, необходимые для применения динамического программирования:
В качестве типичного примера алгоритма DP рассмотрим проблему нахождения длин кратчайших путей между всеми парами вершин в графе, используя Floyd- Warshall.
Предположим, что существуют n вершины с номером 1 до n. Хотя нам интересно рассчитать функцию d(a, b), длину кратчайшего пути между вершинами a и b, трудно найти способ эффективного вычисления этого значения из других значений функции d().
Введем третий параметр c и определим d(a, b, c) как длину кратчайшего пути между a и b, который посещает только вершины в диапазоне от 1 до c. (Не нужно посещать все эти вершины.) Хотя это кажется бессмысленным ограничением для добавления, обратите внимание, что теперь мы имеем следующее соотношение:
d(a, b, c) = min(d(a, b, c-1), d(a, c, c-1) + d(c, b, c-1))
2 аргумента в min() выше показывают два возможных случая. Самый короткий способ получить от a до b, используя только вершины 1 до c:
c (в этом случае он совпадает с самым коротким путем, используя только первые c-1 вершины) илиc. В этом случае этот путь должен быть самым коротким путем от a до c, за которым следует кратчайший путь от c до b, причем оба пути ограничены для посещения только вершин в диапазоне от 1 до c-1 в между. Мы знаем, что если этот случай (проходящий через c) короче, то эти 2 пути не могут посещать какие-либо из одних и тех же вершин, потому что если бы они сделали это, было бы еще короче пропустить все вершины (включая c) между ними, поэтому случай 1 был бы выбран вместо.Эта формулировка удовлетворяет свойству оптимальной субструктуры - нужно только знать оптимальные решения подзадач, чтобы найти оптимальное решение для более крупной задачи. ( Не все проблемы имеют это важное свойство - например, если мы хотим найти самый длинный путь между всеми парами вершин, этот подход разрушается, поскольку самый длинный путь от a до c может посещать вершины, которые также посещаются самым длинным путем от c до b.)
Зная вышеуказанное функциональное соотношение и граничное условие, что d(a, b, 0) равно длине ребра между a и b (или бесконечностью, если такое ребро не существует), можно вычислить каждое значение d(a, b, c), начиная с c=1 и работая до c=n. d(a, b, n) - кратчайшее расстояние между a и b, которое может посещать любую вершину между ними - ответ, который мы ищем.
Почти во всех вводных книгах алгоритмов есть глава для динамического программирования. Я бы рекомендовал:
Если вы хотите узнать об алгоритмах, я обнаружил, что MIT имеет несколько отличных видеороликов доступных лекций.
Например, 6.046J/18.410J Введение в алгоритмы (SMA 5503) выглядит неплохо.
Курс охватывает динамическое программирование, среди множества других полезных алгоритмических методов. Используемая книга также, по моему личному мнению, вполне превосходна и очень достойна покупки для любого серьезного в изучении алгоритмов.
Кроме того, курс содержит список назначений и т.д., поэтому вы также получите возможность практиковать теорию на практике.
Как часть соответствия Математика MSc Я сделал курс, основанный на книге http://www.amazon.co.uk/Introduction-Programming-International -mathematics-computer/dp/0080250645/ref = sr_1_4? ie = UTF8 & qid = 1290713580 & sr = 8-4 Это действительно более математический угол, чем угол программирования, но если вы можете сэкономить время и усилия, это очень подробное введение, которое, казалось, работало для меня как курс, который в значительной степени выполнялся из книги.
У меня также есть ранняя версия книги "Алгоритмы" от Sedgewick, и там есть очень читаемая короткая глава о динамическом программировании. Сейчас он, похоже, продает изумительное разнообразие дорогих книг. Глядя на амазонку, похоже, есть глава с тем же именем на http://www.amazon.co.uk/gp/product/toc/0201361205/исх = dp_toc т.е. = UTF-8 &? п = 266239
Алгоритмы планирования, Стивен ЛаВалле имеет раздел о динамическом программировании:
См. раздел 2.3.1 примера.
MIT Open CourseWare 6.00 Введение в информатику и программирование
Если вы попробуете динамическое программирование, чтобы решить проблему, я думаю, вы поймете концепцию, лежащую в ее основе. В кодедже Google, когда участникам была предоставлена программа под названием "" Добро пожаловать в CodeJam", она отлично показала использование динамического программирования.