Algorytmy zachłanne
- wiskitki
- Użytkownik
- Posty: 503
- Rejestracja: 29 kwie 2011, o 21:39
- Płeć: Mężczyzna
- Lokalizacja: Gdańsk
- Podziękował: 176 razy
- Pomógł: 29 razy
Algorytmy zachłanne
Czym się różnią algorytmy zachłanne od planowania dynamicznego? Wiem że jedno i drugie służy do szukania najkrótszej drogi pomiędzy czymś, ale nie mogę załapać jaka jest różnica.
- Errichto
- Użytkownik
- Posty: 1629
- Rejestracja: 17 mar 2011, o 18:55
- Płeć: Mężczyzna
- Lokalizacja: Suwałki
- Podziękował: 28 razy
- Pomógł: 272 razy
Algorytmy zachłanne
Niekoniecznie.jedno i drugie służy do szukania najkrótszej drogi pomiędzy czymś
Zachłan:
Nie patrzymy na to, co będzie. Ważna jest tylko chwila obecna. W danym momencie wybieramy chwilowo najlepsze rozwiązanie, licząc na to, że nasz wybór okaże się najlepszy. Algorytmy zachłanne nie zawsze dają poprawny wynik, jednak są szybsze.
Dynamik:
Jak najbardziej interesuje nas to, co będzie. Gdy mamy dokonać wyboru, wybieramy tę opcję, która da nam najlepszy wynik ostateczny. Raczej wolniejsze, lecz zawsze poprawne.
Przykład:
Jest kilka miast, niektóre połączone drogami. W miastach są monety. Masz przejść z A do B (bez zawracania) i zebrać jak najwięcej monet.
Jesteś w A i masz 2 drogi do wyboru. Pierwsza prowadzi do miasta z 3 monetami. Druga do miasta z 5 monetami. Zachłan wybierze drugą drogę. Decyzja dynamika zależy od tego, jakich wyborów można dokonać później. Np. gdy po wyborze drugiej drogi możemy uzbierać łącznie kilkanaście monet, a po wyborze pierwszej mamy możliwość dojść do wioski ze 100 monetami, to jednak lepsza jest pierwsza droga.