Ocena brak

Na czym polega metoda algorytmiczna zwana „programowaniem dynamicznym”?

Autor /Barnim7777 Dodano /29.12.2011

Metoda algorytmiczna zwana „programowaniem dynamicznym” opiera się o zasadę optymalności Bellmana, która mówi: „jeśli znamy najlepszą drogę przejścia z punktu początkowego do punktu końcowego prowadzącą przez kolejne punkty, to każdy fragment tej drogi pomiędzy dowolnym punktem a punktem końcowym jest najlepszą drogą przejścia od tego punktu do punktu końcowego”.

Przykładem zastosowania metody „dynamicznej” jest algorytm wyszukiwania najkrótszej ścieżki łączącej dwa wskazane punkty na płaszczyźnie – grafie skierowanym (problem strudzonego wędrowca). W zadaniu tym w przeciwieństwie do metody zachłannej nie chwyta się tych elementów które w danej chwili są najlepsze lecz próbuje się ustalić jakie wyjście da najlepszy efekt końcowy. Analizując poszczególne fragmenty grafu poruszamy się od końca – czyli od punktu oznaczonego flagą „meta”. Badając kolejne ścieżki grafu poznajemy wagę wszystkich możliwych dróg spośród których wybieramy najlepszą.

Podobne prace

Do góry