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).
Teil 1·Erklärung
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
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).
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.
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.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
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.
Heuristik: Ein Algorithmus, der ohne Optimalitäts-Garantie schnell eine gute Lösung findet — durch problem-spezifisches "Daumenwissen".
| 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). |
Greedy (gierig): In jedem Schritt: nimm die lokal beste Wahl.
Klassische Anwendungen:
Vorteil: Sehr schnell (O(n log n) bis O(n²)).
Nachteil: Kann weit vom Optimum entfernt sein.
Lokale Suche / Hill Climbing:
Klassiker für TSP:
k-Opt — Praxis-Standard.Vorteil: Findet oft fast-optimale Lösungen. Nachteil: Bleibt in lokalen Optima stecken.
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).
Idee: Verbiete kürzlich besuchte Lösungen (Tabu-Liste), zwingt Suche aus lokalen Optima.
Tabu-Liste: Letzte L Züge sind "tabu" (nicht wiederholbar).
Idee: Evolution simulieren — Populationen von Lösungen, Selektion, Crossover, Mutation.
Schritte:
P₀.Stark bei: Multi-Objective-Problemen, kombinatorischen Problemen.
Idee: Ameisen-Schwärme legen Pheromon-Spuren — gute Pfade werden verstärkt.
Stark bei: TSP, Routing-Problemen.
Idee: Schwarm von Partikeln durchsucht Lösungsraum, beeinflusst durch eigenes + globales Best.
Stark bei: kontinuierlichen Optimierungs-Problemen.
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).
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.
Wähle Menge, die maximal viele ungeworbene Elemente abdeckt.
Garantie: ln n-Approximation (Chvátal 1979).
EDD (Earliest Due Date) für 1-Maschinen-Scheduling: minimiert maximale Verspätung. SPT (Shortest Processing Time): minimiert mittlere Wartezeit.
Approximations-Algorithmus mit Faktor
α: liefert Lösung mit Wert≤ α · z_(OPT)(bei min) oder≥ 1/(α) · z_(OPT)(bei max).
Beispiele:
α = 1.5α = 2α = 1 + ε für jedes ε > 01/ε — z.B. für Knapsack1. 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.
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.
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.
6 Aufgaben zu Greedy, lokaler Suche und Meta-Heuristiken.
Klausurfragen mit Lösungen (6)
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.
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.
Zuordnungen:
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
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.
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
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 − ε.
6 typische Klausurfragen zu Algorithmen, Approximation und Meta-Heuristiken.
Klausurfragen mit Lösungen (6)
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.
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.
Lösungen pro Lücke:
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
Richtige Reihenfolge:
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
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.
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