Witam,
Bardzo prosiłbym o wytłumaczenie czym różni się technika programowania dynamicznego od techniki z nawrotami, np. na przykładzie dyskretnego problemu plecakowego.
Dyskretny problem plecakowy
- DEXiu
- Użytkownik
- Posty: 1174
- Rejestracja: 17 lut 2005, o 17:22
- Płeć: Mężczyzna
- Lokalizacja: Jaworzno
- Pomógł: 69 razy
Dyskretny problem plecakowy
Hm. Nie wiem jakiego dokładnie tłumaczenia oczekujesz. Najprościej rzecz ujmując to programowanie z nawrotami to takie.. szukanie rozwiązań poprzez sprawdzanie "na pałę" wszystkich możliwości i w razie zabrnięcia sprawdzania w "ślepy zaułek" (tzn. braku rozwiązania dla już ustalonych warunków lub rozwiązania będącego nieoptymalnym) cofnięcia się i zmiany którejś z wcześniej wybranych opcji. W przypadku problemu plecakowego polegałoby to na "wrzucaniu do plecaka" po kolei każdego przedmiotu aż nie będzie można wrzucać więcej, pamiętaniu maksymalnej uzyskanej do tej pory wartości (i ewentualnie przedmiotów które dawały to rozwiązanie) i sprawdzeniu czy istnieje lepsze rozwiązanie poprzez "wyjęcie" ostatnio wrzuconych przedmiotów i próbę wrzucenia innych.
Natomiast programowanie dynamiczne prowadzi od razu do rozwiązania optymalnego poprzez konstruowanie go "od podstaw" na podstawie zapamiętywania optymalnych rozwiązań pomniejszych problemów i konstruowaniu z nich optymalnych rozwiązań problemów większych. W przypadku problemu plecakowego dyskretnego to będzie uzupełnianie tabelki której kolumny będą odpowiadały różnym pojemnościom plecaka, a wiersze wkładaniu kolejnych przedmiotów - zaczynamy od pierwszego przedmiotu wkładanego do plecaka o najmniejszej pojemności i uzupełniając kolejne komórki tabelki (na podstawie uprzednio uzupełnionych) szukamy wartości komórki odpowiadającej wszystkim przedmiotom w plecaku o zadanej pojemności.
Natomiast programowanie dynamiczne prowadzi od razu do rozwiązania optymalnego poprzez konstruowanie go "od podstaw" na podstawie zapamiętywania optymalnych rozwiązań pomniejszych problemów i konstruowaniu z nich optymalnych rozwiązań problemów większych. W przypadku problemu plecakowego dyskretnego to będzie uzupełnianie tabelki której kolumny będą odpowiadały różnym pojemnościom plecaka, a wiersze wkładaniu kolejnych przedmiotów - zaczynamy od pierwszego przedmiotu wkładanego do plecaka o najmniejszej pojemności i uzupełniając kolejne komórki tabelki (na podstawie uprzednio uzupełnionych) szukamy wartości komórki odpowiadającej wszystkim przedmiotom w plecaku o zadanej pojemności.
- qba
- Użytkownik
- Posty: 138
- Rejestracja: 23 sty 2006, o 21:51
- Płeć: Mężczyzna
- Lokalizacja: z zaskoczenia
- Podziękował: 7 razy
Dyskretny problem plecakowy
głównie tej tabelki w programowaniu dynamicznym nie jestem pewien,
wiem że wynik jest w ostatniej komórce np P[m,n] jednak nie wiem jak się go składa,
tzn nie wiem jak uzupełniać tabelkę po wpisaniu tych początkowych zer?
wiem że wynik jest w ostatniej komórce np P[m,n] jednak nie wiem jak się go składa,
tzn nie wiem jak uzupełniać tabelkę po wpisaniu tych początkowych zer?