Programowanie dynamiczne: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
na ogół? |
|||
Linia 1:
'''Programowanie dynamiczne''' jest techniką lub strategią projektowania [[algorytm]]ów, stosowaną przeważnie do rozwiązywania zagadnień [[optymalizacja|optymalizacyjnych]]. Jest alternatywą dla niektórych zagadnień rozwiązywanych za pomocą [[algorytm zachłanny|algorytmów zachłannych]]. Wynalazcą techniki jest amerykański matematyk [[Richard Ernest Bellman|Richard Bellman]], uhonorowany za to odkrycie medalem [[Institute of Electrical and Electronics Engineers|IEEE]] ([[język angielski|ang.]] ''medal of honour'') w [[1979]] roku.
Programowanie dynamiczne opiera się na podziale rozwiązywanego problemu na podproblemy względem kilku parametrów. W odróżnieniu od techniki [[dziel i zwyciężaj]] podproblemy w programowaniu dynamicznym nie są
Zazwyczaj jednym z parametrów definiujących podproblemy jest liczba elementów znajdujących się w rozpatrywanym problemie, drugim jest pewna wartość liczbowa, zmieniająca się w zakresie od 0 do największej stałej występującej w problemie. Możliwe są jednak bardziej skomplikowane dobory parametrów, a także większa ich liczba. Ponieważ jednak uzyskiwany algorytm zazwyczaj wymaga pamięci (i czasu) proporcjonalnego do iloczynu maksymalnych wartości wszystkich parametrów, stosowanie większej ilości parametrów niż 3-4 rzadko bywa praktyczne.
| |||