Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Erklärung
Wenn exakte Verfahren zu langsam sind, helfen Heuristiken weiter. Sie liefern oft in Sekunden gute (aber nicht garantiert optimale) Lösungen für NP-schwere Probleme. Klausurpflicht in 5/8 OR-Programmen.
Die Idee in einem Satz
Heuristik: Ein Algorithmus, der ohne Optimalitäts-Garantie schnell eine gute Lösung findet, durch problem-spezifisches "Daumenwissen".
Heuristik vs. Algorithmus vs. Meta-Heuristik
| Begriff | Eigenschaft |
|---|---|
| Exakter Algorithmus | Findet IMMER optimale Lösung. Worst-Case oft exponentiell (Branch & Bound, Simplex). |
| Heuristik | Schnell, gut, aber keine Optimalitäts-Garantie. Problem-spezifisch. |
| Approximations-Algorithmus | Heuristik mit beweisbarer Güte-Garantie (z.B. ≤ 1.5 · OPT). |
| Meta-Heuristik | Allgemeine Suchstrategie, anwendbar auf viele Probleme (Genetic, Tabu, Simulated Annealing). |
Konstruktions- vs. Verbesserungs-Heuristiken
Konstruktions-Heuristiken, bauen Lösung von Grund auf
Greedy (gierig): In jedem Schritt: nimm die lokal beste Wahl.
Klassische Anwendungen:
- Nearest-Neighbor für TSP: Gehe immer zur nächst-gelegenen unbesuchten Stadt.
- Greedy für Knapsack: Sortiere nach Wert/Gewicht, packe in dieser Reihenfolge.
- Greedy für Set-Cover: Wähle Menge mit maximaler ungeworbener Abdeckung.
Vorteil: Sehr schnell (O(n log n) bis O(n²)).
Nachteil: Kann weit vom Optimum entfernt sein.
Verbesserungs-Heuristiken, verbessern bestehende Lösung
Lokale Suche / Hill Climbing:
- Starte mit einer gültigen Lösung.
- Definiere Nachbarschaft (z.B. "Touren, die durch eine Vertauschung erreicht werden").
- Suche besten Nachbarn. Wenn besser → übernehmen.
- Wiederhole bis kein besserer Nachbar.
Klassiker für TSP:
- 2-Opt (Croes 1958): Umkehren eines Tour-Stücks zwischen zwei Kanten.
- 3-Opt: Trennen + neue Verbindung dreier Kanten.
- Lin-Kernighan (1973): variable
k-Opt, Praxis-Standard.
Vorteil: Findet oft fast-optimale Lösungen. Nachteil: Bleibt in lokalen Optima stecken.
Meta-Heuristiken, entkommen lokalen Optima
Simulated Annealing (Kirkpatrick 1983)
Idee: Inspired von Metallkühlung. Akzeptiere SCHLECHTERE Lösungen mit gewisser Wahrscheinlichkeit.
P(accept) = e^(-Δ z / T)
mit Temperatur T die langsam sinkt.
Vorteil: Theoretisch konvergent zum globalen Optimum (bei richtiger Abkühlung).
Tabu Search (Glover 1986)
Idee: Verbiete kürzlich besuchte Lösungen (Tabu-Liste), zwingt Suche aus lokalen Optima.
Tabu-Liste: Letzte L Züge sind "tabu" (nicht wiederholbar).
Genetic Algorithms (Holland 1975)
Idee: Evolution simulieren, Populationen von Lösungen, Selektion, Crossover, Mutation.
Schritte:
- Initial: zufällige Population
P₀. - Fitness-Bewertung für jede Lösung.
- Selektion: wähle Eltern (z.B. Roulette).
- Crossover: kombiniere zwei Eltern.
- Mutation: zufällige Veränderung.
- Neue Generation. Wiederhole.
Stark bei: Multi-Objective-Problemen, kombinatorischen Problemen.
Ant Colony Optimization (Dorigo 1992)
Idee: Ameisen-Schwärme legen Pheromon-Spuren, gute Pfade werden verstärkt.
Stark bei: TSP, Routing-Problemen.
Particle Swarm Optimization (Kennedy 1995)
Idee: Schwarm von Partikeln durchsucht Lösungsraum, beeinflusst durch eigenes + globales Best.
Stark bei: kontinuierlichen Optimierungs-Problemen.
Greedy für klassische Probleme
Knapsack-Greedy
Sortiere Gegenstände nach Wert/Gewicht-Verhältnis absteigend. Packe in dieser Reihenfolge solange Kapazität reicht.
Garantie: 1/2-Approximation für 0-1-Knapsack (mind. halb so gut wie Optimum).
TSP-Nearest-Neighbor
Start in einer Stadt. Gehe immer zur nächst-gelegenen unbesuchten Stadt. Schließe Tour ab.
Garantie: Keine konstante Approximations-Schranke, kann beliebig schlecht sein.
Set-Cover-Greedy
Wähle Menge, die maximal viele ungeworbene Elemente abdeckt.
Garantie: ln n-Approximation (Chvátal 1979).
Scheduling-Greedy
EDD (Earliest Due Date) für 1-Maschinen-Scheduling: minimiert maximale Verspätung. SPT (Shortest Processing Time): minimiert mittlere Wartezeit.
Approximations-Verhältnis
Approximations-Algorithmus mit Faktor
α: liefert Lösung mit Wert≤ α · z_(OPT)(bei min) oder≥ 1/(α) · z_(OPT)(bei max).
Beispiele:
- Christofides-Algorithmus für metrisches TSP:
α = 1.5 - 2-Approximation für Vertex-Cover:
α = 2 - PTAS (Polynomial Time Approximation Scheme):
α = 1 + εfür jedesε > 0 - FPTAS (Fully PTAS): Laufzeit polynomial in
1/ε, z.B. für Knapsack
Klausur-Faustregeln
1. Greedy ist schnell aber oft nicht optimal. Klausur-Aufgabe: "Konstruieren Sie ein Gegenbeispiel."
2. Lokale Suche bleibt in lokalen Optima stecken. Meta-Heuristiken (Tabu, SA, GA) helfen entkommen.
3. Nearest-Neighbor TSP keine Approximations-Garantie. Christofides ist 1.5-Approximation für metrisches TSP.
4. Knapsack-Greedy nach Wert/Gewicht ist 1/2-Approximation. Klausur-Klassiker.
5. Simulated Annealing konvergiert (theoretisch) zum globalen Optimum. Bei langsamer Abkühlung.
6. Heuristik ≠ Approximation. Approximation hat beweisbare Schranke, Heuristik nicht zwingend.
Häufige Stolpersteine
1. Heuristik als 'falsche' Lösung sehen. Heuristiken sind WICHTIG in der Praxis, viele NP-schwere Probleme sind nur so lösbar. Optimum ist oft nicht nötig (90 % Optimum ist gut genug).
2. Greedy ist nicht immer suboptimal. Manche Probleme haben optimale Greedy-Lösung (Matroide, Kruskal MST, Huffman-Codes).
3. Lokale Suche → globales Optimum erwarten. Falsch. Lokale Suche findet nur lokales Optimum. Global braucht Meta-Heuristik oder Restart.
4. Approximation-Verhältnis falsch interpretieren. Bei min-Problem: α ≥ 1, Algorithmus liefert ≤ α · OPT. Bei max-Problem: α ≤ 1, Algorithmus liefert ≥ α · OPT.
5. Genetic Algorithm = beste Heuristik. Falsch, kein "bester" Algorithmus für alle Probleme (No Free Lunch Theorem). Problemspezifisch wählen.
6. NP-schwer = nicht lösbar. Falsch. NP-schwer = exakt im Worst-Case exponentiell. Heuristiken lösen in Praxis.
Interaktiv verstehen
TSP-Heuristiken: Greedy vs. 2-Opt
6 Städte (deutsche Großstädte) als TSP-Instanz. Toggle zwischen Nearest-Neighbor (Greedy) und 2-Opt-Verbesserung.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Bei "Lösen Sie das TSP" IMMER zuerst Greedy (Nearest-Neighbor) als Startlösung berechnen, dann 2-Opt zur Verbesserung. So zeigst du beide Heuristik-Arten + bekommst Punkte für strukturierten Ansatz, auch ohne Optimum zu erreichen.
Praxis-Übung
Heuristiken, Praxis-Übung
6 Aufgaben zu Greedy, lokaler Suche und Meta-Heuristiken.
Klausurfragen mit Lösungen (6)
- F1.Was unterscheidet eine Heuristik von einem exakten Algorithmus?
Antwort: Heuristik gibt keine Optimalitäts-Garantie, ist aber meist schneller
Erklärung: Heuristik: schnell, gute Lösung, aber KEINE Garantie für Optimalität. Exakter Algorithmus: garantiert optimal, aber meist viel länger (Branch & Bound exponentiell). Praxis-Compromise: Heuristik findet 90-99 % der optimalen Lösung in 1 % der Zeit, meist ausreichend.
- F2.Welche Heuristik gehört zu den Konstruktions-Heuristiken (baut Lösung von Grund auf)?
Antwort: Nearest-Neighbor (Greedy)
Erklärung: Nearest-Neighbor = Konstruktions-Heuristik (Greedy: baut Tour Stück-für-Stück auf). 2-Opt, Tabu Search, Simulated Annealing sind VERBESSERUNGS-Heuristiken (starten mit bestehender Lösung und verbessern). Üblicher Workflow: 1) Greedy für Start, 2) Lokale Suche oder Meta-Heuristik für Verbesserung.
- F3.Ordne Meta-Heuristik der Inspirations-Quelle zu.
Zuordnungen:
- Simulated Annealing → Metallkühlung in der Physik
- Genetic Algorithms → Biologische Evolution (Crossover, Mutation)
- Ant Colony Optimization → Ameisen-Schwärme + Pheromon-Spuren
- Tabu Search → Gedächtnis: verbietet kürzlich besuchte Lösungen
Erklärung: Meta-Heuristiken inspirieren sich aus Natur/Physik: SA (Kirkpatrick 1983, Metallkühlung), GA (Holland 1975, Darwin), ACO (Dorigo 1992, Ameisen), PSO (Kennedy 1995, Schwärme). Tabu Search (Glover 1986) ist anders: nutzt Gedächtnis um Cycle-Detection, NICHT natur-inspiriert.
Typ: Zuordnung
- F4.Was ist die Approximations-Garantie des Greedy-Algorithmus für 0-1-Knapsack (sortiert nach Wert/Gewicht-Verhältnis)?
Antwort: 1/2-Approximation (mindestens halb so gut wie Optimum)
Erklärung: Knapsack-Greedy (sortiert nach v_i/w_i absteigend + greedy packen) ist 1/2-Approximation: garantiert mind. 1/2 · OPT. Beispiel-Worst-Case: 2 Gegenstände, 1 mit hohem Wert/Gewicht-Verhältnis aber zu schwer + Rest passt nicht. Im Fractional-Knapsack ist Greedy sogar OPTIMAL, aber das ist ein anderes Problem.
- F5.Lokale Suche bleibt in lokalen Optima stecken, Meta-Heuristiken wie Simulated Annealing können das überwinden, weil sie auch schlechtere Lösungen akzeptieren.
Antwort: Wahr
Erklärung: RICHTIG. Lokale Suche / Hill Climbing nimmt NUR Verbesserungen, bleibt in lokalen Optima. Simulated Annealing akzeptiert schlechtere Lösungen mit Wahrscheinlichkeit e^(−Δz/T), wobei T (Temperatur) langsam sinkt. So kann Algorithmus aus lokalen Optima entkommen. Bei richtigem Cooling-Schedule theoretisch konvergent zum globalen Optimum (Markov-Chain-Argument).
Typ: Wahr/Falsch
- F6.Welche Approximations-Garantie hat der Christofides-Algorithmus für metrisches TSP?
Antwort: 1.5 (mind. 1.5 × OPT)
Erklärung: Christofides-Algorithmus (1976) für metrisches TSP (Dreiecksungleichung): 1.5-Approximation. Tour-Länge ≤ 1.5 · OPT. Schritte: 1) Minimum Spanning Tree (MST), 2) Perfektes Matching auf Knoten mit ungerader Grad, 3) Euler-Tour. Lange Zeit beste bekannte Approximation für TSP, erst 2020 verbesserte Karlin/Klein/Gharan auf 1.5 − ε.
Klausur-Quiz
Heuristiken, Klausur-Quiz
6 typische Klausurfragen zu Algorithmen, Approximation und Meta-Heuristiken.
Klausurfragen mit Lösungen (6)
- F1.Wer entwickelte den Simulated-Annealing-Algorithmus?
Antwort: Kirkpatrick (1983)
Erklärung: Simulated Annealing: Scott Kirkpatrick et al., 1983 ('Optimization by Simulated Annealing', Science). Inspired von Annealing in Metallurgie. Holland = Genetic Algorithms (1975). Glover = Tabu Search (1986). Dorigo = Ant Colony Optimization (1992). Diese Erfinder + Jahre sind Klausur-Standard.
- F2.Welche Aussage zum Greedy-Algorithmus ist KORREKT?
Antwort: Greedy ist für manche Probleme (z.B. MST mit Kruskal) optimal, für andere suboptimal
Erklärung: Greedy ist OPTIMAL für Probleme mit Matroid-Struktur: MST mit Kruskal/Prim, Huffman-Codes, Activity Selection, Fractional Knapsack. Für andere Probleme nur Heuristik: 0-1-Knapsack, TSP, Set Cover. Klausur-Klassiker: 'Wo ist Greedy optimal, wo nicht?', Matroid-Argument ist Theoretische Begründung.
- F3.Lokale Suche bleibt in {{1}} Optima stecken. Simulated Annealing akzeptiert {{2}} Lösungen mit Wahrscheinlichkeit e^(−Δz/T), wobei T die {{3}} ist. Genetic Algorithms nutzen biologische Konzepte wie {{4}} und {{5}}.
Lösungen pro Lücke:
- {{1}}: lokalen / lokal
- {{2}}: schlechtere / schlechte
- {{3}}: Temperatur
- {{4}}: Crossover / Selektion / Mutation
- {{5}}: Mutation / Selektion / Crossover
Erklärung: Lokale Suche → lokales Optimum (stuck). SA-Akzeptanzwahrscheinlichkeit P = e^(−Δz/T). Bei T hoch werden schlechtere Lösungen häufig akzeptiert (Exploration). Bei T niedrig fast nie (Konvergenz). GA-Konzepte: Selektion (Fittest Survives) + Crossover (Eltern→Kind) + Mutation (zufällige Änderung). Diese 3 Operatoren machen GA aus.
Typ: Lückentext
- F4.Bringe die Schritte eines Genetic Algorithm in die richtige Reihenfolge.
Richtige Reihenfolge:
- Initiale Population erzeugen
- Fitness-Bewertung jeder Lösung
- Selektion (Eltern wählen, z.B. via Roulette)
- Crossover (Kombination zweier Eltern → Kind)
- Mutation (zufällige Änderung)
Erklärung: Genetic-Algorithm-Iteration: 1) Population initialisieren (zufällig). 2) Fitness berechnen (Zielfunktions-Wert). 3) Selektion (wähle Eltern proportional zur Fitness). 4) Crossover (kombiniere 2 Eltern → 2 Kinder). 5) Mutation (zufällig kleine Änderungen). Schleife: 2→5 für jede neue Generation. Terminierung: max Generationen oder Konvergenz.
Typ: Reihenfolge
- F5.Was bedeutet 'NP-schwer' für einen Praxis-Anwender?
Antwort: Problem braucht im Worst-Case exponentielle Zeit für EXAKTE Lösung, Heuristiken liefern in Praxis schnelle gute Lösungen
Erklärung: NP-schwer = Worst-Case-Aussage, KEIN Praxis-Verbot. Beispiele: TSP, Knapsack, SAT, alle NP-schwer, alle in Praxis lösbar via Heuristiken + moderne Solver. Industrieller Standard: kombiniere Heuristiken (schnell, gut) + B&B (Optimum-Bound) + Pre-Processing (Problem-Reduktion). Real-world MIPs mit Mio Variablen werden täglich gelöst.
- F6.Das 'No Free Lunch Theorem' (Wolpert & Macready 1997) besagt, dass es keinen Optimierungs-Algorithmus gibt, der für ALLE Probleme besser ist als alle anderen.
Antwort: Wahr
Erklärung: RICHTIG. No Free Lunch: gemittelt über alle möglichen Optimierungs-Probleme schneiden alle Algorithmen gleich gut ab. Konsequenz: kein 'bester' Algorithmus für alle Probleme, Algorithmus muss zur Problem-Struktur passen. In Praxis: Greedy gut wenn Matroid-Struktur, Tabu/SA gut bei kombinatorisch, GA gut bei multi-objektiv. Klausur-Implikation: 'Welche Heuristik?' braucht IMMER Problem-Analyse.
Typ: Wahr/Falsch
