Greedy-Algorithmus
Strategie: in jedem Schritt die lokal beste Wahl treffen und hoffen, dass das Ergebnis global optimal wird. Nicht immer der Fall — aber oft genug, um es anzuwenden.
Funktioniert, wenn das Problem die Greedy-Choice-Eigenschaft besitzt (lokales Optimum führt zum globalen) plus optimale Substruktur. Klassische Beispiele: Dijkstra (Greedy + DP), Kruskals MST, Prims MST, Huffman-Codierung, Activity Selection.
Der Gewinn, wenn es funktioniert: schnell (typischerweise O(n log n)), einfach zu implementieren. Die Falle: Probleme, die greedy aussehen, es aber nicht sind (Rucksackproblem, Partitionierung). Alternative: DP (wenn Greedy versagt), Backtracking.