Informatik · Klasse 10 · Algorithmen und Komplexität · 2. Halbjahr

Heuristiken und Optimierung

Die Schülerinnen und Schüler entwickeln Lösungsansätze für Probleme, die nicht exakt berechenbar sind.

• KMK Bildungsstandards
• KMK: STD.03
• KMK: STD.17

Über dieses Thema

Heuristiken und Optimierung behandeln Probleme, die nicht exakt in sinnvoller Zeit lösbar sind, wie das klassische Problem des Handlungsreisenden. Hier müssen Schülerinnen und Schüler verstehen, warum exakte Algorithmen bei großen Instanzen scheitern und wie heuristische Verfahren schnelle, aber nicht immer optimale Lösungen liefern. Die Lernenden entwickeln eigene Ansätze, bewerten deren Güte und verknüpfen dies mit den KMK-Standards STD.03 zur Algorithmusentwicklung und STD.17 zur Komplexitätsanalyse. Die Leitfragen erklären, warum Computer für manche Rätsel keine perfekte Lösung finden und wie „gute genug“-Strategien im Alltag funktionieren.

Im Rahmen der Einheit Algorithmen und Komplexität vertieft dieses Thema das Verständnis für NP-harte Probleme und fördert Kompetenzen in der praktischen Informatik. Schülerinnen und Schüler lernen, Trade-offs zwischen Rechenzeit und Lösungsqualität abzuwägen, was für reale Anwendungen wie Logistik oder KI essenziell ist. Sie üben, heuristische Regeln wie Nearest Neighbor zu implementieren und mit exakten Methoden zu vergleichen.

Aktives Lernen eignet sich hervorragend, da abstrakte Konzepte durch Simulationen und Gruppenexperimente konkret werden. Wenn Lernende TSP-Instanzen manuell oder programmierend lösen, internalisieren sie die Grenzen exakter Berechnung und schätzen heuristische Vorteile. Solche hands-on-Aktivitäten stärken Problemlösungsfähigkeiten und machen Komplexität erlebbar.

Leitfragen

1. Warum finden Computer für manche Rätsel keine perfekte Lösung in sinnvoller Zeit?
2. Wie funktionieren „gute genug" Lösungen im Alltag?
3. Was ist das Problem des Handlungsreisenden?

Lernziele

• Analysieren Sie die Zeitkomplexität von Algorithmen für das Problem des Handlungsreisenden (TSP) und erklären Sie, warum exakte Lösungen für große Instanzen unpraktikabel sind.
• Entwerfen Sie eine heuristische Strategie (z. B. Nearest Neighbor) zur Annäherung an eine optimale Lösung für das TSP und implementieren Sie diese in einer Programmiersprache.
• Vergleichen und bewerten Sie die Qualität der Lösungen, die durch eine heuristische Methode im Vergleich zu einer exakten Methode (falls verfügbar) für gegebene TSP-Instanzen erzielt werden.
• Erklären Sie die Trade-offs zwischen Rechenzeit und Lösungsqualität bei der Anwendung von Heuristiken in realen Optimierungsproblemen.

Bevor es losgeht

Grundlagen von Algorithmen und Programmierung

Warum: Schülerinnen und Schüler müssen grundlegende Programmierkonzepte wie Schleifen und Datenstrukturen (z. B. Listen, Arrays) verstehen, um Heuristiken implementieren zu können.

Einführung in die Algorithmenanalyse (z. B. Laufzeitkomplexität)

Warum: Ein Verständnis dafür, wie die Laufzeit von Algorithmen mit der Eingabegröße skaliert (z. B. O(n), O(n^2)), ist notwendig, um die Komplexität von TSP-Lösungsansätzen zu begreifen.

Schlüsselvokabular

Heuristik	Eine Faustregel oder ein Lösungsansatz, der darauf abzielt, eine gute, aber nicht unbedingt optimale Lösung für ein Problem schnell zu finden.
Problem des Handlungsreisenden (TSP)	Ein Optimierungsproblem, bei dem es darum geht, die kürzeste mögliche Route zu finden, die eine gegebene Liste von Städten besucht und zu jeder Stadt genau einmal zurückkehrt.
NP-hart	Eine Klasse von Problemen, für die kein bekannter Algorithmus existiert, der die optimale Lösung in polynomieller Zeit finden kann. Das TSP ist ein Beispiel für ein NP-hartes Problem.
Nearest Neighbor Algorithmus	Ein einfacher heuristischer Algorithmus für das TSP, der schrittweise die nächstgelegene, noch nicht besuchte Stadt auswählt, bis alle Städte besucht sind.
Näherungslösung	Eine Lösung für ein Optimierungsproblem, die nahe an der optimalen Lösung liegt, aber nicht garantiert die beste mögliche Lösung ist.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Computer finden für jedes Problem immer die beste Lösung.

Was Sie stattdessen lehren sollten

Viele Probleme wie TSP sind exponentiell komplex, exakte Lösungen dauern ewig bei großen Datenmengen. Aktive Simulationen lassen Schüler die Explosion der Möglichkeiten erleben und schätzen heuristische Alternateniven. Peer-Diskussionen klären, dass 'optimal' oft unnötig ist.

Häufige Fehlvorstellung

Heuristiken liefern immer falsche Ergebnisse.

Was Sie stattdessen lehren sollten

Heuristiken finden gute, oft nahe-optimale Lösungen schnell. Durch Gruppenvergleiche von Heuristik-Varianten sehen Lernende, wie sie im Alltag überlegen sind. Hands-on-Tests mit realen Distanzen widerlegen den Mythos und fördern nuanciertes Denken.

Häufige Fehlvorstellung

Optimierung ist nur für Profis relevant.

Was Sie stattdessen lehren sollten

Alltagsapps wie Google Maps nutzen Heuristiken. Schüler basteln eigene Routen und vergleichen mit Apps, was die Relevanz zeigt. Aktive Anwendungen verbinden Theorie mit Praxis und motivieren.

Ideen für aktives Lernen

Stationenrotation: Heuristiken testen

Richten Sie vier Stationen ein: Nearest Neighbor, Greedy, 2-Opt und Zufallsheuristik für ein TSP mit 10 Städten. Gruppen lösen jede Instanz in 7 Minuten, notieren Tourenlänge und Zeit. Abschließend vergleichen sie Ergebnisse im Plenum.

45 Min.·Kleingruppen

Paararbeit: Routenplaner bauen

Paare zeichnen 8 Städte auf Papier, wenden Nearest-Neighbor-Heuristik an und messen die Tourenlänge. Sie variieren Startpunkte und diskutieren, warum keine perfekte Lösung entsteht. Erweitern Sie auf digitale Tools wie GeoGebra.

30 Min.·Partnerarbeit

Klassenexperiment: Exakt vs. Heuristik

Die Klasse testet ein TSP mit 12 Städten: Eine Gruppe sucht exhaustiv (kleine Instanz), andere heuristisch. Gemeinsam plotten sie Ergebnisse und diskutieren Skalierbarkeit. Nutzen Sie Python-Skripte für Visualisierung.

50 Min.·Ganze Klasse

Individuell: Heuristik programmieren

Jede Schülerin oder jeder Schüler implementiert Nearest Neighbor in Python für variable Städteanzahlen. Testen Sie Laufzeit und Güte, vergleichen Sie mit Bibliotheken. Teilen Sie Code im Klassenchat.

60 Min.·Einzelarbeit

Bezüge zur Lebenswelt

• Logistikunternehmen wie DHL oder UPS nutzen heuristische Algorithmen, um die effizientesten Routen für ihre Lieferfahrzeuge zu planen und so Treibstoffkosten und Lieferzeiten zu minimieren. Dies ist entscheidend für die tägliche Zustellung von Millionen von Paketen.
• Fluggesellschaften setzen Optimierungsalgorithmen ein, um die Routenplanung für ihre Flugzeuge zu gestalten. Dabei werden Faktoren wie Treibstoffverbrauch, Wetterbedingungen und Flugzeit berücksichtigt, um sowohl Kosten zu senken als auch die Pünktlichkeit zu gewährleisten.
• Stadtplaner und Verkehrsingenieure verwenden Optimierungstechniken, um den Verkehrsfluss zu verbessern und Staus zu reduzieren. Sie analysieren Daten, um die besten Standorte für neue Straßen oder Ampelschaltungen zu finden, was die Mobilität in Metropolen wie Berlin oder München beeinflusst.

Ideen zur Lernstandserhebung

Kurze Überprüfung

Stellen Sie den Lernenden eine kleine TSP-Instanz (z. B. 4-5 Städte) auf einem Arbeitsblatt zur Verfügung. Bitten Sie sie, die Route zu finden, die sie mit dem Nearest Neighbor Algorithmus berechnen würden, und die Gesamtdistanz anzugeben. Vergleichen Sie die Ergebnisse im Plenum.

Diskussionsfrage

Leiten Sie eine Diskussion mit der Frage: 'Stellen Sie sich vor, Sie sind ein Projektmanager für die Planung einer mehrtägigen Fahrradtour durch die Alpen. Welche Art von Problemen würden Sie bei der Routenplanung erwarten, und warum wäre eine exakte Lösung möglicherweise nicht die beste Wahl?'

Lernstandskontrolle

Lassen Sie die Schülerinnen und Schüler auf einem Zettel erklären, warum ein Computer für das Problem des Handlungsreisenden mit 100 Städten wahrscheinlich keine perfekte Lösung findet, und nennen Sie eine Situation, in der eine 'gute genug'-Lösung ausreicht.

Häufig gestellte Fragen

Was ist das Problem des Handlungsreisenden?

Das TSP fordert die kürzeste Rundreise durch alle Städte. Exakte Lösung ist für viele Städte unmöglich in akzeptabler Zeit wegen exponentieller Komplexität. Heuristiken wie Nearest Neighbor approximieren schnell gute Touren, was in Logistik üblich ist. Schüler modellieren es mit Karten und lernen Kompromisse zwischen Zeit und Qualität.

Wie hilft aktives Lernen beim Verständnis von Heuristiken?

Aktives Lernen macht Komplexität greifbar: Schüler simulieren TSP manuell oder programmieren Heuristiken, messen Laufzeiten und vergleichen Lösungen. Gruppenrotationen fördern Diskussionen über Trade-offs. Solche Erfahrungen vertiefen das Bewusstsein für 'gute genug'-Lösungen und stärken algorithmisches Denken nachhaltig.

Beispiele für Heuristiken im Alltag?

Navigationssysteme wenden Nearest-Neighbor-ähnliche Regeln an, um Staus zu umfahren. Suchmaschinen sortieren mit heuristischen Scores. Spiele wie Schach-Engines schätzen Positionen. Schüler erkunden dies durch App-Analysen und eigene Implementierungen, was die Brücke zur Praxis schlägt.

Unterschied zwischen exakten Algorithmen und Heuristiken?

Exakte Algorithmen garantieren die beste Lösung, skalieren aber schlecht. Heuristiken priorisieren Geschwindigkeit mit akzeptabler Qualität. In der Klasse testen Lernende beide an TSP-Instanzen: Exhaustives Suchen bei 10 Städten vs. heuristische Approximation bei 50. Dies verdeutlicht praktische Grenzen.