7
Einführung in den Algorithmenentwurf (Fach) / Greedy (Lektion)
- Greedy Bedeutung: geizig, gierigVorraussetzungen: Teillösungen Schritte zur Erweiterung der Teillösung Kostenfunktion auf Teillösungen
- Greedy-Wahl-Eigenschaft Erreichung einer optimalen Lösung durch treffen der gierigsten/geizigsten Wahl in jedem Schritt
- Optimalität der Teilprobleme Konstruierte Teillösungen sind optimale Lösungen für Teilprobleme
- Austauschargument Vorraussetzung: optimale Teillösung L & G ist Gesamtlösung die L erweitert L' ist Teillösung, die durch Greedyschritt aus L entstehtResultat: Durch Austausch einer Komponente oder Anpassung aus G lässt sich optimale Gesamtlösung G' konstruieren, die L' erweitert
- Most-Recent-Holder Variable um den letzten Wert einer Reihe von unvorhersehbaren Werten/Eingaben zu speichern
- Stepper Variable, die eine vorab bekannte Sequenz von Werten annimmt (z.B. Zähler in for-Schleife)
- Walker/Iterator Variable, die durch die Datenstruktur travesiert/iteriert
Anzeige