Programowanie dynamiczne: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
Przestawiłem parę słów w zdaniu w bardziej logiczny spos |
Zmiana, aby było wiadomo jakim medalem został uhonorowany. |
||
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 ([[język angielski|ang.]] ''
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ą rozłączne, ale musi je cechować [[własność optymalnej podstruktury]]. Zagadnienia odpowiednie dla programowania dynamicznego cechuje również to, że zastosowanie do nich [[Atak brute force|metody siłowej]] (ang. ''brute force'') prowadzi do ponadwielomianowej liczby rozwiązań podproblemów, podczas gdy sama liczba różnych podproblemów jest wielomianowa.
| |||