Programowanie dynamiczne #1


Kolejny wpis z kategorii programowanie dynamiczne:  Longest Common Subsequence

Zadanie – Longest Increasing Sequence

W podanym ciągu liczb znajdź najdłuższy podciąg rosnący.

Przykład:
Wejście: 5 1 4 2 3 1 2 9 1
Wynik:  1 2 3 9

Rozwiązanie – programowanie dynamiczne

Algorytm

Zamiast naiwnego podejścia chcemy zastosować programowanie dynamiczne.

Główna idea kryjąca się za określeniem programowania dynamicznego to rozwiązanie skomplikowanego problemu poprzez rozbicie go na kilka mniejszych problemów i wykorzystanie rozwiązań problemów składowych do obliczenia wyniku naszego głównego problemu.

Jak moglibyśmy rozbić ten problem na mniejsze problemy? Czy jeśli mamy ciąg A, gdzie znamy wartość dla każdego jego elementu oraz wiemy, ile wynosi najdłuższy podciąg kończący się na danym elemencie L, to możemy tą wiedzę jakoś wykorzystać do obliczenia najdłuższego podciągu po dodaniu dodatkowego znaku do A?
Rozważmy następującą sytuację:

Programowanie dynamiczne

Mamy ciąg A = {5,1,4,2 } oraz wiemy, ile wynosi najdłuższy możliwy podciąg kończący się na danej pozycji L = {1, 1, 2, 2 }. Jak możemy wykorzystać tę wiedzę do obliczenia, ile będzie wynosił najdłuższy możliwy podciąg po dodaniu do naszego ciągu liczby 3?  Rozważmy wszystkie możliwości:

  • {5,3} najdłuższy możliwy podciąg ma długość 1. Ponieważ liczba 3 jest mniejsza niż ostatni element naszego ciągu o  dotychczasowej długości 1, więc nie może być wykorzystana do jego przedłużenia.
  • {1, 3} mieliśmy ciąg o długości 1 kończący się liczbą 1. Jeśli dodamy do niego na koniec liczbę 3, to ponieważ 3>1, możemy wydłużyć nasz podciąg o 1.
  • {X,4,3} – mamy dwuelementowy ciąg, gdzie ostatni jego element to 4, a ponieważ 3 jest mniejsze niż 4, nie możemy przedłużyć tego ciągu.
  • {X,2,3} – ostatni element ciągu o długości 2 jest mniejszy od nowego elementu, więc razem z nowym elementem możemy utworzyć podciąg o długości trzy.

Po dodaniu na koniec liczby 3, możemy przedłużyć dwa istniejące podciągi (istnieje warunek, aby nowa wartość była większa niż ostatnia w istniejącym podciągu). Najdłuższy możliwy podciąg, jaki możemy uzyskać, ma długość 3.

Analogicznie możemy postąpić w poniższej sytuacji:

Programowanie dynamiczne

Widzimy, że mamy ciąg o długości 3, zakończony wartością 3, ostania wartość jest mniejsza niż nowa wartość 9. Możemy przedłużyć ten ciąg i uzyskamy {X, X, 3, 9}.

Wzór na nową maksymalną długość podciągu rosnącego wynosi:  L(i) = MAX(L(j) | j<i, A[j] < A[i]) + 1

Jeśli chcemy łatwo odtworzyć cały ciąg, a nie tylko znać jego długość, to musimy dla każdego podciągu przechowywać również index elementu poprzedniego:

Programowanie dynamiczne

Kod Python 3

Kod c++

Dyskusja złożoności

Musimy za-alokować pamięć dla naszej tablicy najdłuższych podciągów. Alokujemy dwa elementy dla każdego elementu ciągu, wiec mamy liniową złożoność pamięciową.

Zaczynamy od ciągu długości 0 i kolejno dodajemy nowe elementy. Elementów jest N i dla każdego musimy dokonać sprawdzenia z każdym istniejącym elementem, więc mamy kwadratową złożoność obliczeniową O(N^2).

Wytłumaczenie Video [EN]

Odnośniki z zakresu – Programowanie dynamiczne

Dodaj komentarz

Twój adres email nie zostanie opublikowany.