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

Question

Я читал заметки по динамическому программированию , и я столкнулся со следующим комментарием.

Если подзадачи не являются независимыми, то есть подзадачи имеют общие подзадачи, то поделить-завоеватьАлгоритм многократно решает общие подзадачи.Таким образом, он выполняет больше работы, чем необходимо

Что это значит?Можете ли вы привести примеры, чтобы прояснить вышесказанное?

Answer 1

Автор ссылается на тот факт, что многие алгоритмы «разделяй и властвуй» имеют подзадачи, которые пересекаются друг с другом.Рассмотрим, к примеру, эту очень простую реализацию Фибоначчи:

int Fibonacci(int n) {
    if (n <= 1) return n;

    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Если вы проследите вызовы, сделанные для вычисления Фибоначчи (4), мы получим

• вызовов Фибоначчи (4)Фибоначчи (3) и Фибоначчи (2)
• Фибоначчи (3) называют Фибоначчи (2), а Фибоначчи (1)
• Фибоначчи (2) - Фибоначчи (1) и Фибоначчи (0)
• Фибоначчи (2) (другой) вызывает Фибоначчи (1), а Фибоначчи (0)
• Фибоначчи (1) завершается.
• Фибоначчи (1) завершается.
• Завершение Фибоначчи (1).
• Завершение Фибоначчи (0).
• Завершение Фибоначчи (0).

Другими словами, всего 9 функцийзвонки сделаны, но здесь только пять уникальных звонков (число Фибоначчи от 0 до 4 включительно).Этот алгоритм можно было бы сделать намного более эффективным, если бы рекурсивные вызовы распределялись между подзадачами, а не пересчитывались с нуля каждый раз.Это одна из ключевых идей динамического программирования.

Чтобы вычислить F _n (n-е число Фибоначчи), приведенный выше код составит в общей сложности 2F _{n + 1} - 1 рекурсивный вызов.Поскольку числа Фибоначчи экспоненциально быстро растут, это требует экспоненциально большой работы.Однако можно использовать тот факт, что многие рекурсивные вызовы идентичны, чтобы значительно упростить это.Вместо того, чтобы начинать с Фибоначчи (4) и работать вниз, давайте начнем с Фибоначчи (0) и продолжим работу.В частности, мы построим таблицу (назовем ее FTable) длиной 5 и заполним ее следующим образом:

• FTable [0] = 0
• FTable [1]= 1

Теперь предположим, что мы хотим вычислить FTable [2].Это требует, чтобы мы знали FTable [0] и FTable [1], но мы уже знаем это, потому что они в таблице.Таким образом, мы можем установить

• FTable [2] = 1

Используя аналогичную логику, мы можем вычислить FTable [3] из FTable [2] и FTable [1]:

• FTable [3] = 2

И FTable [4] из FTable [2] и FTable [3]:

• FTable[4] = 3

Обратите внимание на то, что мы избежали множества рекурсивных вызовов, просто создав их в обратном порядке!Теперь он вычисляет числа Фибоначчи за время O (n), которое экспоненциально быстрее, чем раньше.Используя более продвинутую математику, мы можем добиться даже большего, чем это, но это наглядно показывает, почему динамическое программирование может принять неосуществимые проблемы и сделать их внезапно выполнимыми.

Надеюсь, это поможет!