Algorytmy zachłanne

[wiskitki]

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]

jedno i drugie służy do szukania najkrótszej drogi pomiędzy czymś

Niekoniecznie.

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.