разница между обратным отслеживанием и динамическим программированием

Question

Я слышал, что единственное различие между динамическим программированием и обратным отслеживанием - это DP, позволяющий перекрывать вспомогательные проблемы. (fib (n) = fib (n-1) + fib (n-2)). Это правильно ? Есть ли другие отличия? Также я хотел бы знать некоторые общие проблемы, решаемые с использованием этих методов.

Answer 1

Есть два типичных реализаций динамического программирования: снизу-вверх и сверху донизу.

Top-вниз динамического программирования не что иное, как обычный рекурсии, с расширенной запоминании решения для промежуточных подзадач. Когда данная подзадача возникает во втором (третьем, четвертом ...) времени, она не решается с нуля, но вместо этого ранее запомненное решение используется сразу же. Этот метод известен под названием memoization (no 'r' before 'i').

Это на самом деле то, что ваш пример с последовательностью Фибоначчи должен иллюстрировать.Просто используйте рекурсивную формулу для последовательности Фибоначчи, но постройте таблицу значений fib(i) на этом пути, и вы получите алгоритм Top-to-bottom DP для этой проблемы (так что, например, если вам нужно рассчитать fib(5) второй раз, вы получите его из таблицы, а не вычисляете его снова).

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

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

Answer 2

Динамические проблемы также требуют «оптимальной подструктуры».

Согласно Википедии:

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

возвратом общий алгоритм для нахождения всех (или некоторых) решения некоторые вычислительные задачи, которые последовательно строит кандидатов в решений, и отказывается от каждого частичного кандидата с («откатывается»), как только как , он определяет, что c не может быть завершен до действительного решения.

Для детального обсуждения «оптимальной подструктуры», пожалуйста, прочитайте the CLRS book.

Общие проблемы для возвратов я могу думать, являются:

1. Eight queen puzzle
2. Map coloring
3. Sodoku?

DP проблемы:

1. Это website в MIT имеет хорошую коллекцию проблем DP с хорошими анимированными пояснениями.
2. A chapter from a book от профессора в Беркли.

Answer 3

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

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

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

Answer 4

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

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