Algorytmymedium

Algorytm zachłanny vs programowanie dynamiczne — kluczowa różnica?

Tagi

#greedy#dynamic-programming#optimization

Odpowiedź

Zachłanny wybiera lokalnie najlepszy krok i do niego nie wraca; działa tylko, gdy problem ma własność zachłannego wyboru. DP rozwiązuje nachodzące na siebie podproblemy i reuse’uje wyniki (memoization/tabulation), by zapewnić optimum.

Odpowiedź zaawansowana

Głębiej

Kluczowa różnica to *gwarancja optimum i dowód poprawności*.

Zachłanny:

Wybiera lokalnie najlepszą decyzję teraz.
Działa tylko, gdy zachodzi własność zachłannego wyboru (lokalne optimum da się rozszerzyć do globalnego).

DP:

Definiujesz stany i przejścia.
Opiera się o optimal substructure + overlapping subproblems.
Daje optimum (przy poprawnym modelu), często kosztem czasu/pamięci.

Przykłady

Greedy działa: interval scheduling (najwcześniej kończące), Huffman.
Greedy nie działa: 0/1 knapsack, wiele systemów monet.
DP działa: knapsack, edit distance, LIS (często z optymalizacją).

Typowe pułapki

Użycie greedy „bo działa na przykładach” bez argumentu poprawności.
DP ze zbyt dużym stanem (O(n^2) i więcej) bez analizy ograniczeń.

Powiązane pytania

Algorytmy

Binary search on answer (parametric search): kiedy to ma zastosowanie?

#binary-search#parametric-search#monotonic

Algorytmy

Algorytmy zachłanne: jaka własność sprawia, że wybór zachłanny jest poprawny?

#greedy#correctness#exchange-argument

Algorytmy

Co liczy algorytm Floyda–Warshalla i jaka jest jego złożoność?

#graphs#shortest-path#floyd-warshall

Algorytmy

DP top-down vs bottom-up — jaka jest różnica?

#dynamic-programming#memoization#tabulation

Algorytmy

Co to jest memoization i kiedy pomaga?

#memoization#dynamic-programming#cache

Algorytmy

Jaki problem rozwiązuje algorytm Kadane’a?

#kadane#dynamic-programming#array