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

Question

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

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

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

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

1. Пазл «Восемь королев»
2. Раскраска карты
3. Sodoku?

Проблемы с DP:

1. Это веб-сайт *У 1037 * в Массачусетском технологическом институте есть хорошая коллекция проблем DP с хорошими анимированными объяснениями.
2. Глава из книги от профессора из Беркли.

Answer 3

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

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

Answer 4

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

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

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

Answer 5

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

Answer 6

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

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