Разница между алгоритмом Divide and Conquer и динамическим программированием

В чем разница между алгоритмами Divide and Conquer и алгоритмами динамического программирования? Чем отличаются эти два термина? Я не понимаю разницы между ними.

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

Разделяй и властвуй

Divide and Conquer работает, разделяя проблему на подзадачи, рекурсивно преодолевая каждую подзадачу и комбинируя эти решения.

Динамическое программирование

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

Вы можете подумать о DP = recursion + re-use

Классическим примером для понимания разницы было бы увидеть оба этих подхода к получению n-го числа Фибоначчи. Проверьте этот материал из MIT.

Разделяй и властвуй подход

Подход к динамическому программированию

Другое различие между «разделяй и властвуй» и динамическим программированием может заключаться в следующем:

Разделяй и властвуй:

1. Больше работает над подзадачами и, следовательно, требует больше времени.
2. В «разделяй и властвуй» подзадачи не зависят друг от друга.

Динамическое программирование:

1. Решает подзадачи только один раз, а затем сохраняет их в таблице.
2. В динамическом программировании подзадачи не являются независимыми.

Динамическое программирование и сходства "разделяй и властвуй"

На данный момент я могу сказать, что динамическое программирование является расширением парадигмы «разделяй и властвуй» .

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

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

Пошагово…

Предпосылки / ограничения динамического программирования

Как мы только что обнаружили, есть два ключевых атрибута, которые должны иметь проблема «разделяй и властвуй», чтобы динамическое программирование было применимо:

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

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

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

Расширение динамического программирования для Divide and Conquer

Подход динамического программирования расширяет подход «разделяй и властвуй» с помощью двух методов ( запоминания и табулирования ), цель которых заключается в сохранении и повторном использовании решений подзадач, которые могут значительно улучшить производительность. Например, наивная рекурсивная реализация функции Фибоначчи имеет временную сложность, в O(2^n)которой решение DP делает то же самое только со O(n)временем.

Мемоизация (заполнение кэша сверху вниз) относится к технике кэширования и повторного использования ранее вычисленных результатов. Таким образом, мемоизированная fibфункция будет выглядеть так:

memFib(n) {
    if (mem[n] is undefined)
        if (n < 2) result = n
        else result = memFib(n-2) + memFib(n-1)

        mem[n] = result
    return mem[n]
}

Табулирование (заполнение кеша снизу вверх) аналогично, но фокусируется на заполнении записей кеша. Вычисление значений в кеше проще всего выполнять итеративно. Версия таблицы fibбудет выглядеть так:

tabFib(n) {
    mem[0] = 0
    mem[1] = 1
    for i = 2...n
        mem[i] = mem[i-2] + mem[i-1]
    return mem[n]
}

Вы можете прочитать больше о запоминании и сравнении таблиц здесь .

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

Так в чем же разница между DP и DC?

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

Если вы хотите увидеть примеры кода, вы можете взглянуть на более подробное объяснение здесь, где вы найдете два примера алгоритмов: двоичный поиск и минимальное расстояние редактирования (расстояние Левенштейна), которые иллюстрируют разницу между DP и DC.

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

Знаменитый пример чисел Фибоначчи:

           index: 1,2,3,4,5,6...
Fibonacci number: 1,1,2,3,5,8...

function F(n) {
    if (n < 3)
        return 1
    else
        return F(n-1) + F(n-2)
}

Запустим F (5):

F(5) = F(4) + F(3)
     = {F(3)+F(2)} + {F(2)+F(1)}
     = {[F(2)+F(1)]+1} + {1+1}
     = 1+1+1+1+1

Итак, мы назвали: 1 раз F (4) 2 раза F (3) 3 раза F (2) 2 раза F (1)

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

if (n==1 || n==2)
    return 1
else
    f1=1, f2=1
    for i=3 to n
         f = f1 + f2
         f1 = f2
         f2 = f

Давайте снова вызовем F (5):

fibo1 = 1
fibo2 = 1 
fibo3 = (fibo1 + fibo2) = 1 + 1 = 2
fibo4 = (fibo2 + fibo3) = 1 + 2 = 3
fibo5 = (fibo3 + fibo4) = 2 + 3 = 5

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

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

// declare and initialize a dictionary
var dict = new Dictionary<int,int>();
for i=1 to n
    dict[i] = -1

function F(n) {
    if (n < 3)
        return 1
    else
    {
        if (dict[n] == -1)
            dict[n] = F(n-1) + F(n-2)

        return dict[n]                
    }
}

Итак, отношение к Divide and Conquer таково, что алгоритмы D&D полагаются на рекурсию. А в некоторых их версиях есть «вызов нескольких функций с одним и тем же параметром». Найдите «умножение цепочки матриц» и «самую длинную общую подпоследовательность» для таких примеров, когда DP необходим для улучшения T (n) алгоритма D&D.

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

Динамическое программирование

Разбивает проблему на отдельные подзадачи. Рекурсивный алгоритм для последовательности Фибоначчи является примером динамического программирования, потому что он решает для fib (n), сначала решая для fib (n-1). Чтобы решить исходную проблему, она решает другую проблему.

Разделяй и властвуй

Эти алгоритмы обычно решают похожие части проблемы, а затем объединяют их в конце. Mergesort - классический пример принципа «разделяй и властвуй». Основное различие между этим примером и примером Фибоначчи заключается в том, что при сортировке слиянием деление может (теоретически) быть произвольным, и независимо от того, как вы его разбиваете, вы все равно объединяете и сортируете. Такой же объем работы необходимо выполнить для сортировки массива слиянием, независимо от того, как вы его разделите. Решение fib (52) требует больше шагов, чем решение fib (2).

Я думаю о Divide & Conquerрекурсивном подходе и Dynamic Programmingо заполнении таблиц.

Например, Merge Sortэто Divide & Conquerалгоритм, так как на каждом шаге вы разбиваете массив на две половины, рекурсивно вызываете Merge Sortдве половины, а затем объединяете их.

Knapsackпредставляет собой Dynamic Programmingалгоритм при заполнении таблицы, представляющей оптимальные решения подзадач общего рюкзака. Каждая запись в таблице соответствует максимальному значению, которое вы можете носить в сумке весом w с учетом пунктов 1-j.

Divide and Conquer включает три шага на каждом уровне рекурсии:

1. Разделите проблему на подзадачи.
2. Преодолевайте подзадачи, решая их рекурсивно.
3. Объедините решение подзадач с решением исходной проблемы.
   
   • Это подход сверху вниз .
     
   • Он выполняет больше работы над подзадачами и, следовательно, требует больше времени.
   • например. n-й член ряда Фибоначчи может быть вычислен с временной сложностью O (2 ^ n).
     
     

Динамическое программирование включает следующие четыре шага:

1. Охарактеризуйте структуру оптимальных решений.
2. Рекурсивно определить значения оптимальных решений.
3. Вычислите значение оптимальных решений.
4. Постройте оптимальное решение на основе вычисленной информации .

• Это подход « снизу вверх» .
• Меньше затрат времени, чем «разделяй и властвуй», поскольку мы используем ранее вычисленные значения, а не вычисляем заново.
• например. n-й член ряда Фибоначчи может быть вычислен за O (n) временную сложность.
  
  

Для облегчения понимания давайте рассмотрим «разделяй и властвуй» как решение грубой силы и его оптимизацию как динамическое программирование.

Обратите внимание: алгоритмы «разделяй и властвуй» с перекрывающимися подзадачами можно оптимизировать только с помощью dp.

• Разделяй и властвуй
  • Они разбились на непересекающиеся подзадачи
  • Пример: факториальные числа, то есть факт (n) = n * факт (n-1)

fact(5) = 5* fact(4) = 5 * (4 * fact(3))= 5 * 4 * (3 *fact(2))= 5 * 4 * 3 * 2 * (fact(1))

Как мы видим выше, факт (x) не повторяется, поэтому у факториала есть неперекрывающиеся проблемы.

• Динамическое программирование
  • Они разбились на перекрывающиеся подзадачи
  • Пример: числа Фибоначчи, т.е. fib (n) = fib (n-1) + fib (n-2)

fib(5) = fib(4) + fib(3) = (fib(3)+fib(2)) + (fib(2)+fib(1))

Как мы видим выше, fib (4) и fib (3) используют fib (2). точно так же повторяется столько же fib (x). вот почему у Фибоначчи есть перекрывающиеся подзадачи.

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

Разделяй и властвуй

• Эта проблема решается в следующие три шага: 1. Разделить - разделить на несколько подзадач 2. Завоевать - победить, рекурсивно решая подзадачи 3. Комбинировать - объединить решения подзадач, чтобы получить исходное решение проблемы.
• Рекурсивный подход
• Техника сверху вниз
• Пример: сортировка слиянием

Динамическое программирование

• При этом задача решается в следующие шаги: 1. Определение структуры оптимального решения 2. Повторное определение значения оптимального решения. 3. Получение значений оптимального решения снизу вверх 4. Получение окончательного оптимального решения из полученных значений.
• Не рекурсивный
• Методика снизу вверх
• Пример: умножение матриц Штрассена