Wprowadzenie do programowania dynamicznego: nakładające się podproblemy i optymalna podstruktura
Opublikowany: 2021-02-08Spis treści
Wstęp
Załóżmy, że mieliśmy pytanie do rozwiązania kwadratu liczby 25. Jeżeli po raz pierwszy stajemy przed tym pytaniem, to możemy je rozwiązać albo z ręki, albo za pomocą kalkulatora. Ale jeśli widzieliśmy już to pytanie lub rozwiązaliśmy je wcześniej, istnieje możliwość, że możemy szybko na nie odpowiedzieć, zapamiętując je.
To prowadzi nas do wniosku, że jeśli możemy to zapamiętać, następnym razem możemy to pominąć. Programowanie dynamiczne działa na podobnej koncepcji, chodzi o to, aby zapamiętać wynik obliczeń i wykorzystać go w przyszłości, jeśli zajdzie taka potrzeba.
Ta prosta procedura programowania dynamicznego sprawia, że jest to silna broń dla programisty do pokonania bitwy o wydajny kod.
Załóżmy na przykład, że mamy złożone pytanie i zawsze myślimy o rozwiązaniu, które dzieli pytanie na podproblemy. Ale możemy utknąć w sytuacji, w której wielokrotnie będziemy obliczać podproblem. Tam używamy programowania dynamicznego dla optymalnego rozwiązania.
Programowanie dynamiczne ma dwie koncepcje:
- Zachodzące na siebie podproblemy
- Optymalna podbudowa
Zachodzące na siebie podproblemy
Klasycznym przykładem zrozumienia pojęcia nakładającego się podproblemu jest program do drukowania serii Fibonacciego.
Logika szeregu Fibonacciego jest dana przez „fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)”. A wykonanie tej funkcji bezproblemowo można wykonać za pomocą rozwiązania rekurencyjnego, z przypadkiem podstawowym fibonacci(0)=0 i fibonacci(1)=1.
| publiczny statyczny int fibonacci(int n){ jeśli (n== 0 || n== 1 ) powrót n; zwróć fibonacciego(n -1 )+fibonacciego(n -2 ); } public static void main(String[] args){ System.out.print( “4ta liczba Fibonacciego to “ +fibonacci( 4 )); } |
Powiedzmy, że musimy wydrukować czwartą cyfrę Fibonacciego, a następnie drzewo rekurencji wygląda następująco
Fibonacciego(4)
/ \
Fibonacci(3) + Fibonacci(2)
/ \ / \
fibonacci(2) + fibonacci(1) fibonacci(1) + fibonacci (0)
/ \
Fibonacciego(1) + Fibonacciego (0)
Zauważ, że fibonacci(4) jest piątą cyfrą w szeregu fibonacciego, ponieważ zaczynamy od fibonacci(0). W powyższym drzewie rekurencji widzimy, że fibonacci(2) powtarza się dwukrotnie. Zaobserwowaliśmy duplikację w drzewie rekurencyjnym o wysokości 4, teraz wyobraź sobie, że mamy wywołanie rekurencyjne o ogromnej liczbie, a następnie będzie drzewo rekurencyjne o dużej wysokości. I będzie wiele takich zduplikowanych obliczeń, które są znane jako nakładające się podproblemy.
Mamy dwie metody radzenia sobie z tą (i)tabelacją, (ii) zapamiętywaniem
Pozwól nam je zrozumieć, przeglądając ich wdrożenia.
Zapamiętywanie
Rozwiązanie problemu Fibonacciego metodą zapamiętywania można wykonać tak, jak pokazano poniżej
| statyczna int[] notatka; publiczny statyczny int fibonacci(int n){ if(memo[n]!=-1) notatka zwrotna[n]; jeśli(n==0 || n==1){ notatka[n]=n; powrót n; } memo[n] = fibonacci(n-1)+fibonacci(n-2); notatka zwrotna[n]; } public static void main(String[] args){ memo=nowy int[5]; for(int i=0;i<=4;i++) nota[i]=-1; System.out.println(„Czwarta liczba Fibonacciego to „+fibonacci(4)); } |
W powyższym kodzie tworzymy utrzymywanie pliku dziennika lub utrzymywanie tabeli przeglądowej i przechowywanie wartości obliczonych wyników. Ponieważ zapamiętaliśmy wszystkie obliczone wartości, możemy ich użyć w przyszłości, jeśli zajdzie taka potrzeba, unikając w ten sposób zduplikowanych obliczeń i nakładających się podproblemów.
Cała logika jest podobna do rozwiązania rekurencyjnego, ale jedyną różnicą, jaką wprowadziliśmy, jest to, że zapisujemy je w tablicy memo, zanim zwrócimy wartość do metody głównej. Jedynym ograniczeniem tego algorytmu jest to, że potrzebujemy dodatkowej przestrzeni o rozmiarze O(n), ale optymalizujemy poprzednie rozwiązanie rekurencyjne.
Tabelacja
Ta metoda jest nieco inna niż powyższe rozwiązanie. Zapamiętywanie odbywa się zgodnie z tym samym rekurencyjnym rozwiązaniem. Ale w tabeli stosujemy rozwiązanie iteracyjne. Nazywa się to również podejściem oddolnym. Przyjrzyjmy się realizacji podejścia oddolnego.
| publiczny statyczny int fibonacci(int n){ int tabela[]=nowy int[n+ 1 ]; dla (int i= 0 ;i<=n;i++){ jeśli (i== 0 || i== 1 ) tabela[i]=i; jeszcze { tabela[i]=tabela[i -1 ]+tabela[i -2 ]; } } zwróć tabelę[n]; } public static void main(String[] args){ System.out.println( “4ta liczba Fibonacciego to “ +fibonacci( 4 )); } |
Ponieważ wiemy, że fibonacci(n)=fibonacci(n-1)+fibonacci(n-2), W zapamiętywaniu zaczęliśmy od wywołania funkcji fibonacci(4), a potem zdaliśmy sobie sprawę, że nie obliczyliśmy jej wartości, więc obliczyłem jego wartości, a następnie go zapisałem.
W podobnej sytuacji znajdą się kolejne wywołania rekurencyjne, takie jak fibonacci(3), fibonacci(2). To sprawia, że wiele wywołań rekurencyjnych czeka na stosie rekurencji, ale i tak pomijamy duplikowanie nakładających się podproblemów.
Mamy również sposób na iteracyjne obliczenie Fibonacciego od 0 do n-tego elementu, a następnie zwrócenie n-tego elementu Fibonacciego. To właśnie zaimplementowaliśmy w powyższym kodzie. Ten kod ma również takie samo zapotrzebowanie na miejsce O(n).
Zamówienie: Umiejętności, aby zostać pełnoprawnym programistą
Optymalna podbudowa
W tej koncepcji możemy uzyskać optymalne rozwiązanie problemu tylko wtedy, gdy optymalnie rozwiązaliśmy odpowiadające mu podproblemy.
Klasycznym przykładem tej koncepcji jest rozważanie przechodzenia między węzłami w grafie.
Załóżmy, że mamy wiele korzeni od Telangany po Delhi. A jeśli mamy najkrótszą trasę, która przechodzi przez Nagpur i Gwalior. Następnie najkrótsza trasa z Nagpur do Delhi Delhi musi przebiegać przez Gwalior. Teraz możemy podzielić nasz problem na podproblemy, które są od Telangana do Nagpur, Nagpur do Gwalior, Gwalior do Delhi.
Klasycznym przykładem tej właściwości jest najdłuższy wspólny podciąg w obu ciągach. Podciąg różni się od podciągu. W podsekwencji znaki nie muszą być następcami w oryginalnym ciągu.
Pomysł polega więc na rozwiązaniu go poprzez optymalne rozwiązywanie jego podproblemów. Niech n będzie długością najdłuższego wspólnego podciągu.
Jeśli n=LCS(ziemniak, tatuaż), to n=LCS(ziemniak,tatto)+1 (jeśli ostatnie znaki są takie same), w przeciwnym razie n=maksimum(LCS(ziemniak,tatuaż), LCS(ziemniak, tatuaż).
| static int lcs(String s1, String s2, int m, int n ){ int dp[][] = nowy int[m+ 1 ][n+ 1 ]; for (int i= 0 ; i<=m; i++){ for (int j= 0 ; j<=n; j++){ jeśli (i == 0 || j == 0 ) dp[i][j] = 0 ; inaczej if (s1.charAt(i -1 ) == s2.charAt(j -1 )) dp[i][j] = dp[i -1 ][j -1 ]+ 1 ; w przeciwnym razie dp[i][j] = Math.max(dp[i -1 ][j], dp[i][j -1 ]); } } zwróć dp[m][n]; } public static void main(String[] args){ System.out.println( “długość najdłuższego wspólnego podciągu to “ +lcs( “ziemniak” , “tatuaż” , 6 , 6 )); } |
W powyższym kodzie zaimplementowaliśmy naszą logikę za pomocą metody tabulacji i obliczyliśmy długość najdłuższego wspólnego podciągu występującego w obu ciągach.
Przeczytaj także: Wynagrodzenie Full Stack Developer w Indiach
Ucz się kursów rozwoju oprogramowania online z najlepszych światowych uniwersytetów. Zdobywaj programy Executive PG, Advanced Certificate Programs lub Masters Programs, aby przyspieszyć swoją karierę.
Wniosek
Teraz, gdy już wiesz, jak używać jednej z potężnych technik, aby pokonać bitwę o wydajny kod, spróbuj zaimplementować programowanie dynamiczne w przypadku innych problemów i zacznij wzmacniać swoją zdolność do kodowania pytań za pomocą programowania dynamicznego.
Podsumowując, kursy dla programistów Full Stack to wysoko wykwalifikowani eksperci, którzy poradzą sobie ze wszystkim, co jest związane z tworzeniem stron internetowych. Te umiejętności Full Stack Developera odróżniają ich od Frontend i Backend Developerów.
Co to jest programowanie dynamiczne?
Program komputerowy zawiera dużo powtarzalnego kodu. Jest to nieefektywne i może mieć wpływ na jego wydajność. W takim przypadku stosuje się programowanie dynamiczne. Programowanie dynamiczne to metoda rozwiązywania złożonego problemu poprzez rozbicie go na prostsze podproblemy, rozwiązywanie każdego z tych podproblemów tylko raz i przechowywanie ich rozwiązań za pomocą tabel, które są następnie sprawdzane za każdym razem, gdy podobny podproblem pojawia się później w rozwiązanie złożonego problemu. Dynamiczne algorytmy programowania wykorzystywane są do rozwiązywania różnego rodzaju problemów optymalizacyjnych z zakresu badań operacyjnych, estymacji statystycznej, rozpoznawania wzorców, sztucznej inteligencji, uczenia maszynowego, biologii obliczeniowej i innych dziedzin.
Co to jest nakładający się podproblem w programowaniu dynamicznym?
Nakładający się podproblem jest pojęciem używanym, gdy podproblemy mają rozwiązania, które są używane również w innych podproblemach. To nakładanie się powoduje, że to samo podzadanie jest rozwiązywane więcej niż raz. Problem polega na tym, aby znaleźć sposób na rozwiązanie podzadania tylko raz i użyć tego rozwiązania, aby uzyskać rozwiązania innych podproblemów. Algorytmy programowania dynamicznego rozwiązują ten problem za pomocą zapamiętywania. Zapamiętywanie to technika, w której przechowujemy rozwiązania podproblemów, abyśmy nie musieli ich ponownie rozwiązywać.
Jaka jest optymalna podstruktura w programowaniu dynamicznym?
Optymalna podstruktura oznacza, że optymalne rozwiązanie problemu jest powiązane z optymalnym rozwiązaniem mniejszego problemu w ramach tej samej definicji problemu. Optymalna podkonstrukcja jest dodatkowym wymogiem potrzebnym do rozwiązania problemów lub udowodnienia, że nie ma rozwiązania. Dzięki optymalnej podbudowie możemy udowodnić wiele problemów NP-trudnych. Ogólne podejście do rozwiązywania problemów DP polega na użyciu macierzy programowania dynamicznego do przechowywania optymalnego rozwiązania podproblemów. Dynamiczna macierz programowania może być użyta do rozwiązania dowolnych niezerowych problemów DP z optymalną podstrukturą.