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

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), которое экспоненциально быстрее, чем раньше. Используя более продвинутую математику, мы можем добиться даже большего, чем это, но это действительно показывает, почему динамическое программирование может принимать неосуществимые проблемы и делать их внезапно выполнимыми.

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