Динамическое программирование в алгоритме Кадане

Question

Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
   (a) max_ending_here = max_ending_here + a[i]
   (b) if(max_ending_here < 0)
         max_ending_here = 0
   (c) if(max_so_far < max_ending_here)
          max_so_far = max_ending_here
 return max_so_far

Может ли кто-нибудь помочь мне в понимании оптимальной подструктуры и перекрывающейся проблемы (хлеб с маслом DP) в вышеупомянутом алгоритме?

Answer 1

Согласно этому определению перекрывающихся подзадач, рекурсивная формулировка алгоритма Кадане (f[i] = max(f[i - 1] + a[i], a[i])) не демонстрирует это свойство. Каждая подзадача будет вычисляться только один раз в простой рекурсивной реализации.

Тем не менее, он демонстрирует оптимальную подструктуру в соответствии с ее определением здесь: мы используем решение для меньших подзадач, чтобы найти решение данной задачи (f[i] использования f[i - 1]).

Рассмотрим определение динамического программирования здесь:

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

Идея динамического программирования довольно проста. В общем, чтобы решить данную проблему, нам нужно решить различные части проблемы (подзадачи), а затем объединить решения подзадач для достижения общего решения. Часто при использовании более наивного метода многие из подзадач генерируются и решаются много раз. Подход динамического программирования стремится решить каждую подзадачу только один раз, тем самым уменьшая количество вычислений.

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

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

Поэтому я бы сказал, что это не алгоритм DP, а жадный и / или рекурсивный, в зависимости от реализации. Я бы назвал его жадным с алгоритмической точки зрения по причинам, перечисленным выше, но объективно я бы посчитал другие интерпретации такими же обоснованными.

Answer 2

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

Выявление подзадач и повторяющихся отношений

Представьте, что у нас есть массив aиз которого мы хотим получить максимальный подмассив. Чтобы определить максимальный подмассив, заканчивающийся индексом i имеет место следующее рекурсивное соотношение:

max_subarray_to(i) = max(max_subarray_to(i - 1) + a[i], a[i])

Чтобы получить максимальный подмассив a нам нужно вычислить max_subarray_to() для каждого индекса i в a а затем возьмите max() от него:

max_subarray = max( for i=1 to n max_subarray_to(i) )

пример

Теперь предположим, что у нас есть массив [10, -12, 11, 9]из которого мы хотим получить максимальный подмассив. Это будет работа, необходимая для запуска алгоритма Кадане:

result = max(max_subarray_to(0), max_subarray_to(1), max_subarray_to(2), max_subarray_to(3))

max_subarray_to(0) = 10  # base case
max_subarray_to(1) = max(max_subarray_to(0) + (-12), -12)
max_subarray_to(2) = max(max_subarray_to(1) + 11, 11)
max_subarray_to(3) = max(max_subarray_to(2) + 9, 49)

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

Алгоритм Кадане обычно реализуется с использованием подхода DP снизу вверх, чтобы воспользоваться преимуществами перекрывающихся подзадач и вычислить каждую подзадачу только один раз, следовательно, превратив ее в O(n).