Я слышал, что единственное различие между динамическим программированием и обратным отслеживанием - это то, что DP позволяет перекрывать вспомогательные проблемы. (fib (n) = fib (n-1) + fib (n-2)). Это правильно? Есть ли другие отличия? Также я хотел бы знать некоторые общие проблемы, решаемые с помощью этих методов.
Разница между обратным отслеживанием и динамическим программированием
Ответ 1
Существуют две типичные реализации подхода с динамическим программированием: снизу-вверх и сверху вниз.
Динамическое программирование "сверху вниз" - это не что иное, как обычная рекурсия, дополненная запоминанием решений промежуточных проблем. Когда данная подзадача возникает во втором (третьем, четвертом...) времени, она не решается с нуля, но вместо этого ранее запомненное решение используется сразу же. Этот метод известен под названием memoization (no 'r' до 'i').
На самом деле это пример вашего примера с последовательностью Фибоначчи. Просто используйте рекурсивную формулу для последовательности Фибоначчи, но постройте таблицу значений fib(i) на этом пути, и вы получите алгоритм Top-to-bottom DP для этой проблемы (так, например, если вам нужно вычислить fib(5) второй раз, вы получите его из таблицы, а не вычисляете его снова).
В нижнем динамическом программировании подход также основан на хранении подрешений в памяти, но они решаются в другом порядке (от меньшего к большему), а результирующая общая структура алгоритма не рекурсивна, Алгоритм LCS - это классический пример DPD сверху.
Дробные алгоритмы DP обычно более эффективны, но обычно они сложнее (а иногда и невозможно), так как не всегда легко предсказать, какие примитивные подзадачи вам понадобится для решения целого оригинальную проблему и какой путь вы должны взять из небольших подзадач, чтобы максимально эффективно перейти к окончательному решению.
Ответ 2
Динамические проблемы также требуют "оптимальной подструктуры".
Согласно Википедии:
Динамическое программирование - это метод решение сложных задач путем взлома их вниз на более простые шаги. это применимые к проблемам, которые демонстрируют свойства перекрытия подпроблемы, которые только немного меньшая и оптимальная субструктура.
Backtracking - общий алгоритм для нахождения всех (или некоторых) решений для некоторой вычислительной проблемой, постепенно наращивает кандидатов на решений и отказывается от каждой частичной кандидата c ( "backtracks" ), как только он определяет, что c не может будет завершено до действительного решения.
Подробное обсуждение "оптимальной субструктуры", пожалуйста, прочитайте книгу CLRS.
Общие проблемы для обратного отслеживания, о которых я могу думать, следующие:
Проблемы с DP:
- Этот сайт в MIT имеет хорошую коллекцию проблем DP с приятными анимированными объяснениями.
- Глава из книги от профессора в Беркли.
Ответ 3
Еще одно отличие может заключаться в том, что проблемы динамического программирования обычно опираются на принцип оптимальности . Принцип оптимальности утверждает, что оптимальная последовательность решений или вариантов выбора каждой подпоследовательности также должна быть оптимальной.
Проблемы с обратным трассированием обычно не оптимальны на своем пути! Они могут применяться только к проблемам, допускающим концепцию частичного решения кандидата.
Ответ 4
DP позволяет решить большую, вычислительно интенсивную задачу, разбив ее на подзадачи, решение которых требует только знания о немедленном решении. Вы получите очень хорошую идею, подобрав Needleman-Wunsch и решив образец, потому что так легко увидеть приложение.
Backtracking кажется более сложным, когда дерево решений обрезается. Известно, что определенный путь не даст оптимального результата.
Поэтому можно сказать, что Backtracking оптимизируется для памяти, поскольку DP предполагает, что все вычисления выполняются, а затем алгоритм возвращается через узлы с наименьшими затратами.