Co to jest programowanie dynamiczne?

Dynamiczne programowanie, odnosząc się do dziedziny informatyki, opisuje grupę podobnych algorytmów komputerowych, które mają rozwiązywać złożone problemy poprzez rozkładanie 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 wykorzystują części mniejszych równań, 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ź do równania 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 świata rzeczywistego.

Podczas każdej z tych operacji, dynamiczne programowanieAlgorytm próbuje znaleźć najkrótszą ścieżkę do rozwiązania.Może to zrobić jedno z dwóch podejść.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 oryginalny problem może podzielić się na mniejsze równania, które w pewnym momencie są ponownie wykorzystywane w celu rozwiązania równania.