dynamic-programming Samouczek
Rozpoczęcie programowania dynamicznego

Uwagi

Wprowadzenie do programowania dynamicznego

Programowanie dynamiczne rozwiązuje problemy, łącząc rozwiązania podproblemów. Może być analogiczny do metody „dziel i rządź”, w której problem dzieli się na rozłączne podproblemy, podproblemy są rekurencyjnie rozwiązywane, a następnie łączone w celu znalezienia rozwiązania pierwotnego problemu. Natomiast programowanie dynamiczne ma zastosowanie, gdy podproblemy się pokrywają - to znaczy, gdy podproblemy współużytkują podproblemy. W tym kontekście algorytm dziel i zwyciężaj działa więcej niż to konieczne, wielokrotnie rozwiązując typowe problemy podrzędne. Algorytm programowania dynamicznego rozwiązuje każdy podproblem tylko raz, a następnie zapisuje swoją odpowiedź w tabeli, unikając w ten sposób pracy polegającej na ponownym obliczaniu odpowiedzi za każdym razem, gdy rozwiązuje każdy podproblem.

Spójrzmy na przykład. Włoski matematyk Leonardo Pisano Bigollo , którego powszechnie znamy jako Fibonacciego, odkrył szereg liczb, biorąc pod uwagę wyidealizowany wzrost populacji królików . Seria jest:

1, 1, 2, 3, 5, 8, 13, 21, ......

Możemy zauważyć, że każda liczba po pierwszych dwóch jest sumą dwóch poprzednich liczb. Teraz sformułujmy funkcję F (n) , która zwróci nam n-tą liczbę Fibonacciego, co oznacza:

F(n) = nth Fibonacci Number

Do tej pory wiemy, że

F(1) = 1
F(2) = 1
F(3) = F(2) + F(1) = 2
F(4) = F(3) + F(2) = 3

Możemy to uogólnić poprzez:

F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2)

Teraz, jeśli chcemy zapisać go jako funkcję rekurencyjną, mamy F(1) i F(2) jako nasz podstawowy przypadek. Zatem naszą funkcją Fibonacciego byłoby:

Procedure F(n):                //A function to return nth Fibonacci Number
if n is equal to 1
    Return 1
else if n is equal to 2
    Return 1
end if
Return F(n-1) + F(n-2)

Teraz, jeśli wywołamy F(6) , zadzwoni do F(5) i F(4) , co wywoła jeszcze trochę. Przedstawmy to graficznie:

Na zdjęciu widać, że F(6) wywoła F(5) i F(4) . Teraz F(5) wywoła F(4) i F(3) . Po obliczeniu F(5) możemy z pewnością powiedzieć, że wszystkie funkcje, które zostały wywołane przez F(5) , zostały już obliczone. Oznacza to, że obliczyliśmy już F(4) . Ale ponownie obliczamy F(4) jak wskazuje prawe dziecko F(6) . Czy naprawdę musimy przeliczyć? Co możemy zrobić, to po obliczeniu wartości F(4) , zapiszemy ją w tablicy o nazwie dp i użyjemy ponownie, gdy zajdzie taka potrzeba. Zainicjujemy naszą tablicę dp wartością -1 (lub dowolną wartością, która nie pojawi się w naszych obliczeniach). Następnie wywołamy F (6), gdzie nasz zmodyfikowany F (n) będzie wyglądał:

Procedure F(n):
if n is equal to 1
    Return 1
else if n is equal to 2
    Return 1
else if dp[n] is not equal to -1            //That means we have already calculated dp[n]
    Return dp[n]
else
    dp[n] = F(n-1) + F(n-2)
    Return dp[n]
end if

Wykonaliśmy to samo zadanie jak poprzednio, ale z prostą optymalizacją. Oznacza to, że zastosowaliśmy technikę zapamiętywania . Na początku wszystkie wartości tablicy dp będą wynosić -1 . Po wywołaniu F(4) sprawdzamy, czy jest pusty, czy nie. Jeśli zapisze -1 , obliczymy jego wartość i zapiszemy w dp [4] . Jeśli przechowuje cokolwiek poza -1 , oznacza to, że już obliczyliśmy jego wartość. Więc po prostu zwrócimy wartość.

Ta prosta optymalizacja z wykorzystaniem zapamiętywania nazywa się programowaniem dynamicznym .

Problem można rozwiązać za pomocą programowania dynamicznego, jeśli ma on pewne cechy. To są:

• Podproblemy:
  Problem DP można podzielić na jeden lub więcej podproblemów. Na przykład: F(4) można podzielić na mniejsze podproblemy F(3) i F(2) . Ponieważ podproblemy są podobne do naszego głównego problemu, można je rozwiązać za pomocą tej samej techniki.
• Nakładające się podproblemy:
  Problem DP musi mieć nakładające się podproblemy. Oznacza to, że musi istnieć wspólna część, dla której ta sama funkcja jest wywoływana więcej niż jeden raz. Na przykład: F(5) i F(6) mają wspólne F(3) i F(4) . To jest powód, dla którego zapisaliśmy wartości w naszej tablicy.

• Optymalna podbudowa:
  Powiedzmy, że jesteś proszony o zminimalizowanie funkcji g(x) . Wiesz, że wartość g(x) zależy od g(y) g(z) . Jeśli teraz możemy zminimalizować g(x) , minimalizując zarówno g(y) i g(z) , tylko wtedy możemy powiedzieć, że problem ma optymalną podbudowę. Jeśli g(x) jest zminimalizowane tylko poprzez minimalizację g(y) i jeśli minimalizacja lub maksymalizacja g(z) nie ma żadnego wpływu na g(x) , to problem ten nie ma optymalnej podbudowy. Krótko mówiąc, jeśli można znaleźć optymalne rozwiązanie problemu z optymalnego rozwiązania jego podproblemu, możemy powiedzieć, że problem ma optymalne właściwości podkonstrukcji.

Zrozumienie stanu w programowaniu dynamicznym

Omówmy z przykładem. Z N elementów, na ile sposobów można wybrać elementy R? Wiesz, że jest to oznaczone przez . Pomyśl teraz o jednym elemencie.

• Jeśli nie wybierzesz przedmiotu, musisz wziąć r przedmiotów z pozostałych n-1 przedmiotów, co daje .
• Jeśli wybierzesz przedmiot, musisz wziąć r-1 przedmiotów z pozostałych n-1 przedmiotów, co daje .

Podsumowanie tych dwóch daje nam całkowitą liczbę sposobów. To jest:

Jeśli uważamy nCr(n,r) jako funkcja, która bierze n i r jako parametr i określa , możemy napisać wyżej wspomnianą relację jako:

nCr(n,r) = nCr(n-1,r) + nCr(n-1,r-1)

To jest relacja rekurencyjna. Aby to zakończyć, musimy określić przypadki podstawowe. Wiemy to, i . Wykorzystując te dwa jako przypadki podstawowe, nasz algorytm do ustalenia będzie:

Procedure nCr(n, r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
end if
Return nCr(n-1,r) + nCr(n-1,r-1)

Jeśli spojrzymy na procedurę graficznie, zobaczymy, że niektóre rekurencje są wywoływane więcej niż raz. Na przykład: jeśli weźmiemy n = 8 i r = 5 , otrzymamy:

Możemy uniknąć tego powtarzającego się wywołania za pomocą tablicy dp . Ponieważ są 2 parametry, potrzebujemy tablicy 2D. Zainicjujemy tablicę dp wartością -1 , gdzie -1 oznacza, że wartość nie została jeszcze obliczona. Nasza procedura będzie:

Procedure nCr(n,r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
else if dp[n][r] is not equal to -1        //The value has been calculated
    Return dp[n][r]
end if
dp[n][r] := nCr(n-1,r) + nCr(n-1,r-1)
Return dp[n][r]

Określić , potrzebowaliśmy dwóch parametrów n i r . Parametry te nazywane są stanem . Możemy po prostu wywnioskować, że liczba stanów determinuje liczbę wymiarów tablicy dp . Rozmiar tablicy zmieni się zgodnie z naszymi potrzebami. Nasze algorytmy programowania dynamicznego zachowają następujący ogólny wzorzec:

Procedure DP-Function(state_1, state_2, ...., state_n)
Return if reached any base case
Check array and Return if the value is already calculated.
Calculate the value recursively for this state
Save the value in the table and Return

Określanie stanu jest jedną z najważniejszych części programowania dynamicznego. Składa się z liczby parametrów, które definiują nasz problem i optymalizując ich obliczenia, możemy zoptymalizować cały problem.

Konstruowanie rozwiązania DP

Bez względu na to, ile problemów rozwiążesz za pomocą programowania dynamicznego (DP), nadal Cię zaskoczy. Ale jak wszystko inne w życiu, praktyka czyni cię lepszym. Mając to na uwadze, przyjrzymy się procesowi budowania rozwiązania problemów DP. Inne przykłady na ten temat pomogą ci zrozumieć, czym jest DP i jak działa. W tym przykładzie postaramy się zrozumieć, jak wymyślić od początku rozwiązanie DP.

Iteracyjny VS rekurencyjny:
Istnieją dwie techniki konstruowania rozwiązania DP. Oni są:

• Iteracyjny (przy użyciu cykli pomocniczych)
• Rekurencyjne (przy użyciu rekurencji)

Na przykład algorytm obliczania długości najdłuższej wspólnej podsekwencji dwóch łańcuchów s1 i s2 wyglądałby następująco:

Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
    Table[0][i] = 0
endfor
for i from 1 to s2.length
    Table[i][0] = 0
endfor
for i from 1 to s2.length
    for j from 1 to s1.length
        if s2[i] equals to s1[j]
            Table[i][j] = Table[i-1][j-1] + 1
        else
            Table[i][j] = max(Table[i-1][j], Table[i][j-1])
        endif
    endfor
endfor
Return Table[s2.length][s1.length]

To jest iteracyjne rozwiązanie. Istnieje kilka powodów, dla których kodowany jest w ten sposób:

• Iteracja jest szybsza niż rekurencja.
• Określenie złożoności czasu i przestrzeni jest łatwiejsze.
• Kod źródłowy jest krótki i czysty

Patrząc na kod źródłowy, możesz łatwo zrozumieć, jak i dlaczego to działa, ale trudno jest zrozumieć, jak wymyślić takie rozwiązanie. Jednak dwa wyżej wymienione podejścia przekładają się na dwa różne pseudokody. Jeden używa iteracji (od dołu do góry), a drugi stosuje podejście rekurencyjne (od góry do dołu). Ten ostatni jest również znany jako technika zapamiętywania. Jednak oba rozwiązania są mniej więcej równoważne i jedno można łatwo przekształcić w drugie. W tym przykładzie pokażemy, jak znaleźć rekurencyjne rozwiązanie problemu.

Przykładowy problem:
Powiedzmy, że masz półki N ( 1, 2, 3, ...., N ) umieszczone obok siebie na półce. Cena i tego wina wynosi p [i] . Ceny win rosną z każdym rokiem. Załóżmy, że jest to rok 1 , w roku y cena i tego wina wyniesie: rok * cena wina = y * p [i] . Chcesz sprzedawać wina, które masz, ale musisz sprzedać dokładnie jedno wino rocznie, począwszy od tego roku. Ponownie, każdego roku możesz sprzedawać tylko wino po lewej lub po prawej stronie i nie możesz zmieniać kolejności win, co oznacza, że muszą pozostać w tej samej kolejności, jak na początku.

Na przykład: załóżmy, że masz 4 wina na półce, a ich ceny wynoszą (od lewej do prawej):

+---+---+---+---+
| 1 | 4 | 2 | 3 |
+---+---+---+---+

Optymalnym rozwiązaniem byłaby sprzedaż win w kolejności 1 -> 4 -> 3 -> 2 , co da nam całkowity zysk w wysokości:

Chciwe podejście:
Po burzy mózgów przez jakiś czas możesz wymyślić rozwiązanie, aby sprzedać drogie wino tak późno, jak to możliwe. Więc twoją chciwą strategią będzie:

Every year, sell the cheaper of the two (leftmost and rightmost) available wines.

Chociaż strategia nie wspomina, co zrobić, gdy oba wina kosztują tyle samo, strategia wydaje się słuszna. Ale niestety tak nie jest. Jeżeli ceny win wynoszą:

+---+---+---+---+---+
| 2 | 3 | 5 | 1 | 4 |
+---+---+---+---+---+

Chciwa strategia sprzedawałaby je w kolejności 1 -> 2 -> 5 -> 4 -> 3, uzyskując całkowity zysk:

Ale możemy to zrobić lepiej, jeśli sprzedajemy wina w kolejności 1 -> 5 -> 4 -> 2 -> 3, uzyskując całkowity zysk:

Ten przykład powinien cię przekonać, że problem nie jest tak łatwy, jak na pierwszy rzut oka. Ale można to rozwiązać za pomocą programowania dynamicznego.

Cofanie:
Przydaje się wymyślenie rozwiązania do zapamiętywania dla problemu ze znalezieniem rozwiązania cofania. Rozwiązanie cofania ocenia wszystkie poprawne odpowiedzi dla problemu i wybiera najlepszą. W przypadku większości problemów łatwiej jest znaleźć takie rozwiązanie. Przy podejściu do rozwiązania wstecznego można zastosować trzy strategie:

1. powinna to być funkcja obliczająca odpowiedź za pomocą rekurencji.
2. powinien zwrócić odpowiedź z instrukcją return .
3. wszystkie zmienne nielokalne powinny być używane tylko do odczytu, tj. funkcja może modyfikować tylko zmienne lokalne i ich argumenty.

Dla naszego przykładowego problemu spróbujemy sprzedać wino znajdujące się skrajnie po lewej lub po prawej stronie i rekurencyjnie obliczymy odpowiedź i zwrócimy lepszą. Rozwiązanie cofania wyglądałoby następująco:

// year represents the current year
// [begin, end] represents the interval of the unsold wines on the shelf
Procedure profitDetermination(year, begin, end):
if begin > end                  //there are no more wines left on the shelf
    Return 0
Return max(profitDetermination(year+1, begin+1, end) + year * p[begin], //selling the leftmost item
           profitDetermination(year+1, begin, end+1) + year * p[end])   //selling the rightmost item

Jeśli profitDetermination(1, 0, n-1) procedurę za pomocą profitDetermination(1, 0, n-1) , gdzie n jest całkowitą liczbą win, zwróci odpowiedź.

To rozwiązanie po prostu wypróbowuje wszystkie możliwe prawidłowe kombinacje sprzedaży win. Jeśli na początku jest n win, to sprawdzi możliwości. Mimo że otrzymujemy teraz prawidłową odpowiedź, złożoność algorytmu rośnie wykładniczo.

Prawidłowo napisana funkcja cofania powinna zawsze stanowić odpowiedź na dobrze zadane pytanie. W naszym przykładzie procedura profitDetermination stanowi odpowiedź na pytanie: jaki jest najlepszy zysk ze sprzedaży win z cenami zapisanymi w tablicy p, gdy bieżącym rokiem jest rok, a przedział niesprzedanych win sięga [początek , koniec] włącznie? Zawsze powinieneś próbować utworzyć takie pytanie dla funkcji cofania, aby sprawdzić, czy masz rację i dokładnie zrozumieć, co robi.

Ustalanie stanu:
Stan to liczba parametrów używanych w rozwiązaniu DP. Na tym etapie musimy zastanowić się, które argumenty przekazane do funkcji są zbędne, tzn. Możemy je skonstruować na podstawie innych argumentów lub w ogóle ich nie potrzebujemy. Jeśli są takie argumenty, nie musimy przekazywać ich do funkcji, obliczymy je wewnątrz funkcji.

W powyższej przykładowej funkcji profitDetermination argument year jest zbędny. Jest to równoważne liczbie win, które już sprzedaliśmy plus jedno. Można to ustalić na podstawie łącznej liczby win od początku minus liczba win, których nie sprzedaliśmy plus jeden. Jeśli przechowujemy całkowitą liczbę win n jako zmienną globalną, możemy przepisać funkcję jako:

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
year := n - (end-begin+1) + 1        //as described above
Return max(profitDetermination(begin+1, end) + year * p[begin],
           profitDetermination(begin, end+1) + year * p[end])

Musimy także pomyśleć o zakresie możliwych wartości parametrów, które można uzyskać z prawidłowego wejścia. W naszym przykładzie każdy z parametrów begin i end może zawierać wartości od 0 do n-1 . Przy prawidłowym wprowadzeniu spodziewamy się również begin <= end + 1 . Mogą istnieć różne argumenty O(n²) można wywoływać naszą funkcję.

Zapamiętywanie:
Jesteśmy już prawie skończeni. Aby przekształcić rozwiązanie cofania ze złożonością czasową w rozwiązanie do zapamiętywania ze złożonością czasową , użyjemy małej sztuczki, która nie wymaga dużego wysiłku.

Jak wspomniano powyżej, są tylko różne parametry, za pomocą których można wywoływać naszą funkcję. Innymi słowy, są tylko różne rzeczy, które możemy obliczyć. Więc gdzie to robi złożoność czasu pochodzi i co to oblicza !!

Odpowiedź brzmi: wykładnicza złożoność czasu pochodzi z powtarzającej się rekurencji i dlatego oblicza te same wartości raz po raz. Jeśli uruchomisz powyższy kod dla dowolnej tablicy n = 20 win i obliczysz, ile razy funkcja była wywoływana dla argumentów: początek = 10 i koniec = 10 , otrzymasz liczbę 92378 . To ogromna strata czasu, aby obliczyć tę samą odpowiedź wiele razy. Co możemy zrobić, aby to poprawić, to przechowywać wartości po ich obliczeniu i za każdym razem, gdy funkcja prosi o już obliczoną wartość, nie musimy ponownie uruchamiać całej rekurencji. Będziemy mieli tablicę dp [N] [N] , zainicjalizujemy ją wartością -1 (lub dowolną wartością, która nie pojawi się w naszych obliczeniach), gdzie -1 oznacza, że wartość nie została jeszcze obliczona. Rozmiar tablicy zależy od maksymalnej możliwej wartości początku i końca, ponieważ będziemy przechowywać odpowiednie wartości niektórych wartości początkowych i końcowych w naszej tablicy. Nasza procedura wyglądałaby następująco:

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
if dp[begin][end] is not equal to -1                //Already calculated
    Return dp[begin][end]
year := n - (end-begin+1) + 1
dp[begin][end] := max(profitDetermination(year+1, begin+1, end) + year * p[begin],
           profitDetermination(year+1, begin, end+1) + year * p[end])
Return dp[begin][end]

To jest nasze wymagane rozwiązanie DP. Dzięki naszej bardzo prostej sztuczce rozwiązanie działa czas, bo są różne parametry nasza funkcja może być wywołana za pomocą i dla każdego z nich funkcja działa tylko raz za pomocą złożoność.

Letni:
Jeśli możesz zidentyfikować problem, który można rozwiązać za pomocą DP, wykonaj następujące kroki, aby zbudować rozwiązanie DP:

• Utwórz funkcję cofania, aby podać poprawną odpowiedź.
• Usuń zbędne argumenty.
• Oszacuj i zminimalizuj maksymalny zakres możliwych wartości parametrów funkcji.
• Spróbuj zoptymalizować złożoność czasową jednego wywołania funkcji.
• Zapisz wartości, aby nie trzeba było ich dwukrotnie obliczać.

Złożoność rozwiązania DP to: zakres możliwych wartości, które można wywołać z * złożonością czasową każdego wywołania .