Programowanie dynamiczne #1

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 podejścia naiwnego, 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 dokonania obliczeń na nich. W późniejszym etapie rezultaty składowe są wykorzystywane do uzyskania wyniku problemu głównego.

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ę:

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 (zgodnie z warunkiem, 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:

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:

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:

Kod Python 3

def LongestIncreasingSequence( dane ):
    L = [ 0 for a in dane]
    Ref = [ -1 for a in dane]
    maxCount=0
    currentMaxIndex = -1


    for i, val_i in enumerate(dane):
        for j in range(0,i):
            val_j = dane[j]
            if val_i <= val_j:
                continue;
            if L[j]+1 > L[i]:
                L[i] = L[j]+1
                Ref[i] = j
        if L[i] > maxCount:
            maxCount = L[i]
            currentMaxIndex = i


    vec = [];
    while currentMaxIndex != -1:
        vec.insert(0,dane[currentMaxIndex])
        currentMaxIndex = Ref[currentMaxIndex]
    return vec

Kod c++

#include <iostream>
#include <algorithm>

using namespace std;

vector<int> LongestIncreasingSequence( vector<int>& dane )
{
    int ilosc = dane.size();
    vector<int> L(ilosc,0);
    vector<int> Ref(ilosc,-1);

    int maxCount=0, currentMaxIndex = -1;

    for ( int i = 0; i < ilosc; ++i )
    {
        for ( int j = 0; j < i; ++j )
        {
            if ( dane[i] <= dane[j] ) continue;
            if ( L[j]+1 > L[i] )
            {
                L[i] = L[j]+1;
                Ref[i] = j;
            }
        }
        if ( L[i] > maxCount ) {
            maxCount = L[i];
            currentMaxIndex = i;
        }
    }

    vector<int> vec;
    while (currentMaxIndex != -1) {
        vec.push_back(dane[currentMaxIndex]);
        currentMaxIndex = Ref[currentMaxIndex];
    }
    std::reverse(vec.begin(),vec.end());

    return vec;
}

Dyskusja złożoności

Musimy dokonać alokacji pamięci dla naszej tablicy najdłuższych podciągów. Czynimy to dla dwóch elementów, wiec mamy liniową złożoność pamięciową.

Zaczynamy od ciągu długości zero 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).