Aspekt programowania dynamicznego w algorytmie Kadane

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 

Czy ktoś może mi pomóc w zrozumieniu optymalnej podstruktury i problemu zachodzenia na siebie (chleb i masło DP) i powyższego?

Answer 1

Według this definicji nakładających podproblemów, rekurencyjne preparat algorytmu Kadaně'S (f[i] = max(f[i - 1] + a[i], a[i])) nie wykazują tę właściwość. Każdy podproblem zostanie obliczony tylko raz w naiwnej rekurencyjnej implementacji.

Uważa jednak wykazują optymalną podbudowę zgodnie z jego definicją here: używamy rozwiązanie mniejszych podproblemów aby znaleźć rozwiązanie danego problemu naszego (f[i] wykorzystuje f[i - 1]).

Rozważmy definicję dynamicznego programowania here:

z matematyki, informatyki i ekonomii, programowanie dynamiczne, jest sposobem rozwiązywania złożonych problemów, łamiąc je na prostsze podproblemów. Ma zastosowanie do problemów wykazujących właściwości nakładających się podproblemów 1 i optymalnej podstruktury (opisanej poniżej). Jeśli ma to zastosowanie, metoda zajmuje znacznie mniej czasu niż metody naiwne, które nie wykorzystują nakładania się podpoziomów (jak na przykład wyszukiwanie w pierwszej kolejności).

Idea programowania dynamicznego jest dość prosta. Ogólnie rzecz biorąc, aby rozwiązać dany problem, musimy rozwiązać różne części problemu (podproblemy), a następnie połączyć rozwiązania podproblemów, aby osiągnąć ogólne rozwiązanie. Często przy użyciu bardziej naiwnej metody wiele podproblemów jest generowanych i rozwiązywanych wiele razy. Podejście dynamiczne programowanie stara się rozwiązać każdy subproblem tylko raz, co zmniejsza liczbę obliczeń

To pozostawia pole do interpretacji co do tego, czy algorytm Kadaně może być uważany za algorytm DP: to nie rozwiązuje problemu, łamiąc to w łatwiejsze podproblemy, ale jego podstawowe podejście rekursywne nie generuje nakładających się podproblemów, co jest tym, co DP ma sprawnie obsługiwać - a więc byłoby to poza specjalnością DP.

Z drugiej strony można powiedzieć, że nie jest konieczne, aby podstawowe podejście rekursywne prowadziło do nakładania się podproblemów, ale spowodowałoby to, że każdy algorytm rekursywny byłby algorytmem DP, który dałby DP zbyt szeroki zakres w moim opinia. Nie znam się na literaturze, która by to definitywnie rozstrzygała, więc nie wyznaczyłbym ucznia ani nie zastanawiałabym się nad książką lub artykułem w żaden sposób, jak to określił.

Powiedziałbym więc, że nie jest to algorytm DP, tylko chciwy i/lub rekursywny, w zależności od implementacji. Nazwałbym to chciwie z algorytmicznego punktu widzenia z powodów wymienionych powyżej, ale obiektywnie uważam inne interpretacje za równie ważne.