Co to jest programowanie dynamiczne?
Programowanie dynamiczne, odnosząc się do dziedziny informatyki, opisuje grupę podobnych algorytmów komputerowych, które mają rozwiązywać złożone problemy poprzez podzielenie problemu na zestawy mniejszych problemów. Po raz pierwszy stworzony przez Richarda Bellmana w latach 50. XX wieku dynamiczne programowanie działa z problemami, które są albo nakładające się podproblemami lub optymalnymi podbudami. Aby zrozumieć, jak działa dynamiczne programowanie, najlepiej zrozumieć koncepcję tych dwóch terminów.
Nakładające się podproblemki opisują skomplikowane równania, które po podziwianiu na mniejsze zestawy równań ponownie wykorzystaj części mniejszych równań więcej niż raz, aby osiągnąć odpowiedź. Na przykład równanie matematyczne kazało obliczyć wszystkie możliwe wyniki przy użyciu zestawu liczb, może obliczyć ten sam wynik wielokrotnie, obliczając inne wyniki tylko raz. Programowanie dynamiczne poinformowałoby ten problem, że po obliczeniu wyniku po raz pierwszy powinien zapisać ten wynik i podłączyć odpowiedź doRównanie później zamiast go ponownie obliczyć. W przypadku długich złożonych procesów i równań, oszczędza to czas i tworzy szybsze rozwiązanie przy użyciu znacznie mniejszej liczby kroków.
Optymalne podstruktury tworzą rozwiązanie, znajdując najlepszą odpowiedź na wszystkie podproblemy, a następnie tworząc najlepszą ogólną odpowiedź. Po rozbiciu złożonego problemu na mniejsze problemy komputer używa następnie systemu matematycznego, aby ustalić, jaka jest najlepsza odpowiedź dla każdego problemu. Oblicza odpowiedź na oryginalny problem z mniejszych odpowiedzi. Wady istnieją z tym procesem. Chociaż daje rozwiązanie, które działa najlepiej matematycznie, może być najlepszym rozwiązaniem w prawdziwym życiu, w zależności od rodzaju problemu i tego, jak odnosi się do prawdziwego świata.
Podczas każdej z tych operacji algorytm programowania dynamicznego próbuje znaleźć najkrótszą ścieżkę do rozwiązania. Może to zająć jeden zDwa podejścia do tego. Podejście odgórne rozkłada równanie na mniejsze równania i w razie potrzeby ponownie wykorzystuje odpowiedzi dla tych równań. Podejście oddolne próbuje rozwiązać najmniejszą wartość matematyczną po rozbiciu równania, a następnie sprawdza się w kierunku największego stamtąd. Oba podejścia oszczędzają czas, ale programowanie dynamiczne działa tylko wtedy, gdy pierwotny problem może podzielić się na mniejsze równania, które w pewnym momencie są ponownie wykorzystywane w celu rozwiązania równania.