Mam zestaw liczb całkowitych. Chcę znaleźć najdłużej rosnącą podsekwencję tego zestawu za pomocą programowania dynamicznego.
215
Mam zestaw liczb całkowitych. Chcę znaleźć najdłużej rosnącą podsekwencję tego zestawu za pomocą programowania dynamicznego.
Odpowiedzi:
OK, opiszę najpierw najprostsze rozwiązanie, którym jest O (N ^ 2), gdzie N jest rozmiarem kolekcji. Istnieje również rozwiązanie O (N log N), które również opiszę. Zajrzyj tutaj w dziale Wydajne algorytmy.
Zakładam, że wskaźniki tablicy wynoszą od 0 do N - 1. Zdefiniujmy
DP[i]
więc długość LIS (najdłuższego wzrastającego podsekwencji), który kończy się na elemencie z indeksemi
. Aby obliczyćDP[i]
, patrzymy na wszystkie indeksyj < i
i sprawdzamy, czyDP[j] + 1 > DP[i]
iarray[j] < array[i]
(chcemy, aby rosła). Jeśli to prawda, możemy zaktualizować bieżące optimum dlaDP[i]
. Aby znaleźć globalne optimum dla tablicy, możesz wziąć maksymalną wartośćDP[0...N - 1]
.Korzystam z tablicy,
prev
aby móc później znaleźć rzeczywistą sekwencję nie tylko jej długości. Wystarczy wrócić rekurencyjnie zbestEnd
pętli za pomocąprev[bestEnd]
.-1
Wartość jest znak do zatrzymania.OK, teraz do bardziej wydajnego
O(N log N)
rozwiązania:Niech
S[pos]
zostanie zdefiniowana jako najmniejsza liczba całkowita, która kończy rosnącą sekwencję długościpos
. Teraz iteruj przez każdą liczbę całkowitąX
zestawu wejściowego i wykonaj następujące czynności:Jeśli
X
> ostatni element wS
, to dołączX
na końcuS
. Oznacza to, że znaleźliśmy nowy największyLIS
.W przeciwnym razie znajdź najmniejszy element w
S
, który jest>=
niżX
, i zmień go naX
. PonieważS
jest sortowany w dowolnym momencie, element można znaleźć za pomocą wyszukiwania binarnego wlog(N)
.Całkowity czas pracy -
N
liczby całkowite i wyszukiwanie binarne dla każdego z nich - N * log (N) = O (N log N)Zróbmy teraz prawdziwy przykład:
Zbiór liczb całkowitych:
2 6 3 4 1 2 9 5 8
Kroki:
Zatem długość LIS wynosi
5
(rozmiar S).Aby zrekonstruować rzeczywiste
LIS
, ponownie użyjemy tablicy nadrzędnej. Niechparent[i]
będzie poprzednikiem elementu z indeksemi
naLIS
końcu elementu z indeksemi
.Aby uprościć sprawę, możemy przechowywać w tablicy
S
nie rzeczywiste liczby całkowite, ale ich indeksy (pozycje) w zbiorze. Nie trzymamy{1, 2, 4, 5, 8}
, ale trzymamy{4, 5, 3, 7, 8}
.To jest wejście [4] = 1 , wejście [5] = 2 , wejście [3] = 4 , wejście [7] = 5 , wejście [8] = 8 .
Jeśli odpowiednio zaktualizujemy tablicę nadrzędną, faktyczny LIS to:
Teraz ważna rzecz - jak zaktualizować macierz nadrzędną? Istnieją dwie opcje:
Jeśli
X
> ostatni element wS
, toparent[indexX] = indexLastElement
. Oznacza to, że rodzic najnowszego elementu jest ostatnim elementem. Po prostu przygotowujemyX
się do końcaS
.W przeciwnym razie znaleźć indeks najmniejszy element
S
, który jest>=
ponadX
i zmienić goX
. Tutajparent[indexX] = S[index - 1]
.źródło
DP[j] + 1 == DP[i]
toDP[i]
nie poprawi sięDP[i] = DP[j] + 1
. Próbujemy zoptymalizowaćDP[i]
.[1,2,5,8]
: 4 pojawia się przed 1 w tablicy, jak może być LIS[1,2,4,5,8]
?[2,3,4,5,8]
. Przeczytaj uważnie -S
tablicaDOES NOT
reprezentuje rzeczywistą sekwencję.Let S[pos] be defined as the smallest integer that ends an increasing sequence of length pos.
Wyjaśnienie Petara Mincheva pomogło mi to wyjaśnić, ale ciężko mi było przeanalizować, co to wszystko, dlatego stworzyłem implementację Pythona z nazbyt zmiennymi nazwami zmiennych i dużą ilością komentarzy. Zrobiłem naiwne rozwiązanie rekurencyjne, rozwiązanie O (n ^ 2) i rozwiązanie O (n log n).
Mam nadzieję, że pomoże to wyczyścić algorytmy!
Rozwiązanie rekurencyjne
Rozwiązanie do programowania dynamicznego O (n ^ 2)
Rozwiązanie do programowania dynamicznego O (n log n)
źródło
bisect
. Aby zademonstrować działanie algorytmu i jego charakterystykę wydajności, starałem się zachować jak najbardziej prymitywny charakter.Mówiąc o rozwiązaniu DP, zaskoczyło mnie, że nikt nie wspomniał o tym, że LIS można zredukować do LCS . Wszystko, co musisz zrobić, to posortować kopię oryginalnej sekwencji, usunąć wszystkie duplikaty i wykonać LCS z nich. W pseudokodzie jest to:
I pełna implementacja napisana w Go. Nie musisz utrzymywać całej macierzy DP n ^ 2, jeśli nie musisz rekonstruować rozwiązania.
źródło
Następująca implementacja C ++ zawiera również pewien kod, który buduje najdłuższy podciąg rosnący za pomocą tablicy o nazwie
prev
.Implementacja bez stosu po prostu odwraca wektor
źródło
Oto trzy kroki oceny problemu z punktu widzenia dynamicznego programowania:
Jeśli weźmiemy jako przykładową sekwencję {0, 8, 2, 3, 7, 9}, o indeksie:
Oto działający kod C ++ 11:
źródło
Oto implementacja Scala algorytmu O (n ^ 2):
źródło
Oto kolejna implementacja JAVA O (n ^ 2). Brak rekurencji / zapamiętywania w celu wygenerowania faktycznej podsekwencji. Tylko tablica ciągów, która przechowuje rzeczywisty LIS na każdym etapie i tablica do przechowywania długości LIS dla każdego elementu. Cholernie łatwe. Spójrz:
Kod w akcji: http://ideone.com/sBiOQx
źródło
Można to rozwiązać w O (n ^ 2) za pomocą programowania dynamicznego. Kod Pythona dla tego samego wyglądałby tak:
Do wprowadzenia:
5 19 5 81 50 28 29 1 83 23
wyjście byłoby:
[1, 2, 1, 3, 3, 3, 4, 1, 5, 3] 5
List_index listy wyjściowej jest list_index listy wejściowej. Wartość na danym indeksie list_index na liście wyników oznacza Najdłuższą rosnącą długość podsekwencji dla tego indeksu list.
źródło
oto implementacja java O (nlogn)
źródło
To implementacja Java w O (n ^ 2). Po prostu nie użyłem wyszukiwania binarnego, aby znaleźć najmniejszy element w S, który jest> = niż X. Właśnie użyłem pętli for. Korzystanie z wyszukiwania binarnego spowodowałoby złożoność w O (n logn)
źródło
sprawdź kod w Javie, aby uzyskać jak najdłuższy wzrost podsekwencji z elementami tablicy
http://ideone.com/Nd2eba
źródło
Można to rozwiązać w O (n ^ 2) za pomocą programowania dynamicznego.
Przetwarzaj elementy wejściowe w kolejności i prowadź listę krotek dla każdego elementu. Każda krotka (A, B) dla elementu i będzie oznaczać: A = długość najdłuższej rosnącej pod-sekwencji kończącej się na i oraz B = indeks poprzednika z listy [i] w najdłuższej rosnącej podsekwencji kończącej się na liście [i ].
Zacznij od elementu 1, lista krotek dla elementu 1 będzie [(1,0)] dla elementu i, zeskanuj listę 0..i i znajdź listę elementów [k] taką, że lista [k] <lista [i] , wartość A dla elementu i, Ai będzie wynosić Ak + 1, a Bi będzie wynosić k. Jeśli istnieje wiele takich elementów, dodaj je do listy krotek dla elementu i.
Na koniec znajdź wszystkie elementy o maksymalnej wartości A (długość LIS kończącej się na elemencie) i cofnij się, używając krotek, aby uzyskać listę.
Udostępniłem kod dla tego samego na http://www.edufyme.com/code/?id=66f041e16a60928b05a7e228a89c3799
źródło
Wdrożenie O (n ^ 2) Java:
źródło
mimo że istnieje sposób na rozwiązanie tego problemu w czasie O (nlogn) (rozwiązuje się to w czasie O (n ^ 2)), ale i tak daje dynamiczne podejście programistyczne, które jest również dobre.
źródło
Oto moje rozwiązanie Leetcode przy użyciu wyszukiwania binarnego: ->
źródło
Najprostsze rozwiązanie LIS w C ++ ze złożonością czasową O (nlog (n))
WYDAJNOŚĆ:
4
źródło
Najdłuższa rosnąca kolejność (Java)
źródło
Wdrożyłem LIS w java za pomocą dynamicznego programowania i zapamiętywania. Wraz z kodem wykonałem obliczenia złożoności, tj. Dlaczego jest to O (n Log (base2) n). Moim zdaniem teoretyczne lub logiczne wyjaśnienia są dobre, ale praktyczna demonstracja jest zawsze lepsza do zrozumienia.
Podczas gdy uruchomiłem powyższy kod -
źródło
Podejście O (NLog (N)), aby znaleźć najdłuższą rosnącą sekwencję podrzędną Zachowajmy
tablicę, w której i-ty element jest najmniejszą możliwą liczbą, z którą podsekwencja o rozmiarze ai może się zakończyć.
Celowo unikam dalszych szczegółów, ponieważ najlepiej głosowana odpowiedź już to wyjaśnia, ale ta technika ostatecznie prowadzi do zgrabnej implementacji przy użyciu ustawionej struktury danych (przynajmniej w c ++).
Oto implementacja w c ++ (przy założeniu, że wymagany jest ściśle zwiększający się najdłuższy rozmiar podsekwencji)
źródło