Jeśli tu jesteś, to są szanse, że próbowałeś rozwiązać „maksymalny problem Subarray” i natknąłeś się na algorytm Kadane, ale nie mogłeś dowiedzieć się, jak coś takiego działa. A może byłeś zmęczony używaniem algorytmu Kadane jako”czarnej skrzynki”. A może chciałeś zrozumieć dynamiczny aspekt programowania. A może po prostu chcesz dowiedzieć się o nowej koncepcji, która może uczynić cię lepszym w programowaniu. Bez względu na powód, jesteś we właściwym miejscu.,
aby lepiej zrozumieć algorytm Kadane, najpierw przejdziemy przez krótkie wprowadzenie do programowania dynamicznego. Następnie przyjrzymy się dość popularnemu problemowi programistycznemu, maksymalnemu problemowi Podprzestrzennemu. Zobaczylibyśmy, jak ten problem można rozwiązać za pomocą podejścia brute force, a następnie spróbowalibyśmy poprawić nasze podejście i wymyślić lepszy algorytm, aka, algorytm Kadane ' a.
więc przejdźmy do rzeczy.,
Programowanie dynamiczne
Programowanie dynamiczne jest metodą rozwiązywania złożonego problemu poprzez rozbicie go na zbiór prostszych podproblemów, rozwiązanie każdego z tych podproblemów tylko raz i przechowywanie ich rozwiązań za pomocą struktury danych opartej na pamięci (tablica, Mapa itp.). Więc następnym razem, gdy pojawia się ten sam pod-problem, zamiast rekomputerować swoje rozwiązanie, po prostu wyszukuje się wcześniej obliczone rozwiązanie, oszczędzając w ten sposób czas obliczeń.
ci, którzy nie pamiętają przeszłości, są skazani na jej powtórzenie., – Programowanie dynamiczne
oto genialne wyjaśnienie pojęcia programowania dynamicznego na Quora – odpowiedź Jonathana Paulsona, jak powinienem wyjaśnić programowanie dynamiczne 4-latkowi?
chociaż programowanie dynamiczne to coś więcej, to jednak chcemy zrozumieć maksymalny problem Subarray ' u.
Maximum Subarray Problem
maximum subarray problem jest zadaniem znalezienia największej możliwej sumy sąsiednich subarray, w obrębie danej jednowymiarowej tablicy a liczb.,
na przykład, dla tablicy podanej powyżej, ciągłą podpunktą z największą sumą jest suma 6. Użyjemy tej tablicy jako naszego przykładu w dalszej części tego artykułu. Zakładamy również, że tablica jest indeksowana zerem, tzn. -2 będzie wywoływany jako' 0-ty ' element tablicy i tak dalej. Również A reprezentuje wartość w indeksie I.,
teraz przyjrzymy się bardzo oczywistemu rozwiązaniu danego problemu.
podejście Brute Force
jednym bardzo oczywistym, ale nie tak dobrym rozwiązaniem jest obliczenie sumy każdego możliwego podzapytania i maksimum z nich byłoby rozwiązaniem. Możemy zacząć od indeksu 0 i obliczyć sumę wszystkich możliwych podzbiorów zaczynających się od elementu A, jak pokazano na rysunku poniżej. Następnie obliczymy sumę wszystkich możliwych podzbiorów zaczynających się od A, A i tak dalej aż do A, gdzie n oznacza rozmiar tablicy (n = 9 w naszym przypadku)., Zauważ, że każdy pojedynczy element jest podzbiorem.
będziemy wołać maksymalną sumę subararayów zaczynających się od elementu a, czyli local_maximum na indeksie i. tak więc po przejrzeniu wszystkich indeksów, pozostaniemy z local_maximum dla wszystkich indeksów. W końcu możemy znaleźć maksimum tych local_maximum i otrzymamy ostateczne rozwiązanie, tzn., maksymalna możliwa suma. Nazwalibyśmy to global_maximum.
ale możesz zauważyć, że nie jest to bardzo dobra metoda, ponieważ wraz ze wzrostem rozmiaru tablicy, liczba możliwych podprzestrzeni wzrasta szybko, zwiększając w ten sposób złożoność obliczeniową. A dokładniej, jeśli wielkość tablicy wynosi n, to złożoność czasowa tego rozwiązania wynosi O (n2), co nie jest zbyt dobre.
Jak możemy to poprawić? Czy jest jakiś sposób na wykorzystanie koncepcji programowania dynamicznego? Przekonajmy się.,
algorytm Kadane ' a
w tej sekcji ponownie użyjemy podejścia brute force omówionego powyżej, ale tym razem zaczniemy od tyłu. Jak to by pomogło? Zobaczmy.
zaczniemy od ostatniego elementu i obliczymy sumę wszystkich możliwych podzbiorów kończących się elementem A, jak pokazano na poniższym rysunku. Następnie obliczymy sumę wszystkich możliwych podzbiorów kończących się na A, A i tak dalej aż do A.,
i iteracja 1 (po prawej)
teraz skupmy się na podpowiedziach kończących się elementem A (=-1) i A (=2) pokazanym na poniższym rysunku.,
z powyższego rysunku widzimy, że local_maximum jest równe 3, co jest sumą podzbioru . Teraz spójrz na podpowiedzi kończące się na A. zauważysz, że te podpowiedzi można podzielić na dwie części, podpowiedzi kończące się na A (podświetlone kolorem żółtym) i pojedynczy element podpowiedzi a (na Zielono).
powiedzmy, że jakoś znam local_maximum., Następnie widzimy, że aby obliczyć local_maximum, nie musimy obliczać sumy wszystkich podparć kończących się na A, ponieważ znamy już wynik z tablic kończących się na A. zauważ, że jeśli tablica ma maksymalną sumę, to musimy tylko sprawdzić tablice podświetlone czerwonymi strzałkami, aby obliczyć local_maximum. I to prowadzi nas do zasady, na której działa algorytm Kadane.
local_maximum w indeksie i jest maksimum A i sumą a oraz local_maximum w indeksie i-1.,
używając powyższej metody, musimy iterować przez tablicę tylko raz, co jest o wiele lepsze niż nasze poprzednie podejście brute force. A dokładniej, złożoność czasowa algorytmu Kadane ' a to O (n).
na koniec zobaczmy, jak to wszystko będzie działać w kodzie.,
Code Walkthrough
Poniżej znajduje się bardzo zrozumiała implementacja (w C++) funkcji, która pobiera tablicę jako argument i Zwraca sumę maksymalnej podprogramu.
zauważ, że zamiast używać tablicy do przechowywania wartości local_maximum, po prostu przechowujemy ostatnią wartość local_maximum w zmiennej typu int 'local_max', ponieważ to jest to, czego potrzebujemy do obliczenia następnej wartości local_maximum., Ponadto, ponieważ używamy zmiennej 'global_max' do śledzenia maksymalnej wartości local_maximum, która w końcu wychodzi jako wymagane wyjście.
podsumowanie
ze względu na sposób, w jaki algorytm ten wykorzystuje optymalne podprogramy (maksymalna podprogram kończący się na każdej pozycji jest obliczana w prosty sposób z powiązanego, ale mniejszego i nakładającego się podprogramu: maksymalna podprogram kończący się na poprzedniej pozycji) algorytm ten może być postrzegany jako prosty przykład programowania dynamicznego., Algorytm Kadane ' a jest w stanie znaleźć maksymalną sumę sąsiednich podzbiorów w tablicy O(n).