Co to jest programowanie dynamiczne?

Programowanie dynamiczne, odnosząc się do dziedziny informatyki, opisuje grupę podobnych algorytmów komputerowych przeznaczonych do rozwiązywania złożonych problemów poprzez rozbicie problemu na zestawy mniejszych problemów. Programowanie dynamiczne, stworzone po raz pierwszy przez Richarda Bellmana w latach 50. XX wieku, działa z problemami, które pokrywają się z podproblemami lub optymalnymi podkonstrukcjami. Aby zrozumieć, jak działa programowanie dynamiczne, najlepiej zrozumieć koncepcję tych dwóch terminów.

Nakładające się na siebie podproblemy opisują skomplikowane równania, które po rozbiciu na mniejsze zestawy równań ponownie wykorzystują części mniejszych równań, aby uzyskać odpowiedź. Na przykład równanie matematyczne, które ma obliczyć wszystkie możliwe wyniki przy użyciu zestawu liczb, może obliczyć ten sam wynik wiele razy, a inne wyniki tylko raz. Programowanie dynamiczne powiedziałoby temu problemowi, że po obliczeniu wyniku po raz pierwszy powinien zapisać ten wynik i podłączyć odpowiedź do równania później, zamiast obliczać go ponownie. W przypadku długich skomplikowanych procesów i równań oszczędza to czas i tworzy szybsze rozwiązanie przy użyciu znacznie mniejszej liczby kroków.

Optymalne podbudowy tworzą rozwiązanie, znajdując najlepszą odpowiedź na wszystkie podproblemy, a następnie tworząc najlepszą ogólną odpowiedź. Po podzieleniu złożonego problemu na mniejsze problemy, komputer używa systemu matematycznego, aby ustalić najlepszą odpowiedź na każdy problem. Oblicza odpowiedź na pierwotny problem na podstawie mniejszych odpowiedzi. W tym procesie istnieją wady. Chociaż daje rozwiązanie, które działa najlepiej matematycznie, może być, ale nie musi być najlepszym rozwiązaniem w prawdziwym życiu, w zależności od rodzaju problemu i tego, jak odnosi się do realnego świata.

Podczas każdej z tych operacji algorytm programowania dynamicznego próbuje znaleźć najkrótszą ścieżkę do rozwiązania. W tym celu może być zastosowane jedno z dwóch podejść. Podejście odgórne dzieli równanie na mniejsze i w razie potrzeby ponownie wykorzystuje odpowiedzi na te równania. Podejście oddolne próbuje rozwiązać najmniejszą wartość matematyczną po rozbiciu równania, a następnie zmierza w kierunku największej stamtąd. Oba podejścia oszczędzają czas, ale programowanie dynamiczne działa tylko wtedy, gdy pierwotny problem można rozbić na mniejsze równania, które w pewnym momencie są ponownie wykorzystywane do rozwiązania równania.