Dlaczego mergesort nie jest dynamiczne programowanie

Question

Czytałem te słowa:

Istnieją dwa główne atrybuty, że problem musi posiadać w celu programowanie dynamiczne być stosowane: optymalna podbudowa i nakładających podproblemów. Jeśli problem można rozwiązać, łącząc optymalne rozwiązania z nie nakładającymi się podpoziomami, strategia nazywa się "dziel i rządź". Dlatego mergesort i quicksort nie są klasyfikowane jako problemy z programowaniem dynamicznym.

mam 3 pytania:

1. Dlaczego mergesort i quicksort nie jest programowanie dynamiczne myślę mergesort również można podzielić małe problemy i małe problemy następnie zrobić to samo i tak dalej.
2. Czy algorytm Dijkstry korzysta z dynamicznego algorytmu?
3. Czy są stosowane przykłady zastosowania programowania dynamicznego?

Answer 1

1. Słowa kluczowe są tu „nakładające podproblemów” oraz „Optymalny podbudowa”. Po uruchomieniu quicksort lub mergesort, rekursywnie dzielisz tablicę na mniejsze fragmenty, które się nie nakładają. Nigdy nie działasz na tych samych elementach oryginalnej tablicy dwa razy podczas danego poziomu rekursji. Oznacza to, że nie ma możliwości ponownego wykorzystania poprzednich obliczeń. Z drugiej strony, wiele problemów wymaga wykonywania tych samych obliczeń w stosunku do zachodzących na siebie podzbiorów i ma przydatną cechę, że optymalne rozwiązanie podproblemu może być ponownie wykorzystane przy obliczaniu optymalnego rozwiązania dla większego problemu.

2. Algorytm Dijkstry jest klasycznym przykładem programowania dynamicznego, ponieważ ponownie wykorzystuje wcześniejszych obliczeń, aby dowiedzieć się najkrótsza droga pomiędzy dwoma węzłami A i Z. Powiedzmy, że natychmiastowe sąsiadom są B i C. Możemy znaleźć najkrótszą drogę od A do Z, sumując odległość między A i B z naszą obliczoną najkrótszą ścieżką od B do Z; i wykonaj to samo dla znalezienia najkrótszej ścieżki od C do Z. Wtedy najkrótsza ścieżka od A do Z będzie krótsza z tych dwóch ścieżek. Kluczowym wnioskiem jest to, że możemy ponownie użyć najkrótszych obliczeń ścieżek dla ścieżek o długości 2 podczas obliczania najkrótszych ścieżek o długości 3 i tak dalej. Powoduje to znacznie skuteczniejszy algorytm.

3. Programowanie dynamiczne może być używane do rozwiązywania wielu rodzajów problemów - patrz http://en.wikipedia.org/wiki/Dynamic_programming#Examples:_Computer_algorithms dla niektórych przykładów.

Answer 2

1. Dla programowanie dynamiczne może być stosowane do problemu, nie powinno być

   ja. Optymalna struktura w podproblemów:

Oznacza to, że jeśli rozbić swój problem na mniejsze jednostki, te mniejsze jednostki muszą być również podzielone na jeszcze mniejsze jednostki do optymalnego rozwiązania. Na przykład w sortowaniu scalonym tablica liczb może zostać posortowana, jeśli podzielimy ją na dwie podmary, posortujemy i połączymy. Podczas sortowania tych dwóch podbarw, powtórz ten sam proces, który zastosowano w poprzednim zdaniu. Optymalne rozwiązanie (sortowana tablica) pojawia się wtedy, gdy znajdziemy optymalne rozwiązanie dla jego podproblemów (sortujemy podbarwniki i łączymy je). To wymaganie jest spełnione dla sortowania scalonego. Podproblemy muszą również być niezależne, aby mogły podążać za optymalną strukturą.Jest to również spełnione przez sortowanie scalone, ponieważ rozwiązania podproblemów nie mają wpływu na rozwiązania innych firm. Na przykład, rozwiązania dwóch części tablicy nie mają wpływu na ich sortowanie.

ii. Nakładające się na siebie podproblemy:

Oznacza to, że podczas rozwiązywania problemu podrobów, które formułujesz, powtarza się, a więc trzeba je rozwiązać tylko raz. W przypadku sortowania scalonego wymaganie to będzie spełniane rzadko w normalnych przypadkach. Tablica liczb, takich jak 2 1 3 4 9 4 2 1 3 1 9 4, może być dobrym kandydatem do nakładania się pod-problemów na sortowanie scalone. W takim przypadku rozwiązanie sortowania podproblemów (2 1 3) można zapisać w tabeli do ponownego wykorzystania, ponieważ zostanie ono wywołane dwukrotnie podczas obliczeń. Ale jak widać, istnieje bardzo nikła szansa, że ​​losowa tablica liczb będzie miała tego rodzaju powtarzające się sztuczki. Tak więc byłoby to nieefektywne, gdybyśmy użyli dynamicznej techniki programowania, takiej jak zapamiętywanie, dla algorytmu typu sortowanie scalone.

2. Nie. Algorytm Dijkstry wykorzystuje chciwą strategię.

3. Tak. Jeśli mogę zacytować Wikipedia tutaj, "Programowanie dynamiczne jest szeroko stosowane w bioinformatyce do zadań, takich jak dopasowanie sekwencji, składanie białka, przewidywanie struktury RNA i wiązanie białka z DNA." ^[1]

[1] https://en.wikipedia.org/wiki/Dynamic_programming