Die Unterrichtseinheit „Verkehr“ befasst sich mit dem Traveling Salesman Problem. Navigationssysteme oder Routenplaner sollen nicht nur irgendeine mögliche Strecke vom Start zum Ziel berechnen, sondern den kürzesten (optimalen) Weg berechnen. Die Suche nach dem kürzesten Weg oder nach einer optimalen Rundreise beschäftigt Informatikerinnen und Informatiker seit Jahrzehnten.

Lernfilm

Der Lernfilm ‚Optimieren: Wie finde ich die beste Rundreise?‘ eignet sich als Einstieg ins Thema.

Unterrichtsmaterialien

Hier finden Sie die Materialien des Moduls zum Download:

• Verkehr Lehrpersonenkommentar Sek I (.pdf)
• Kopiervorlagen (.pdf)

Einzelne Teile aus dem Dossier zum Download:

• Informatik-Biber Aufgaben (.zip)
• Städtekarten Experiment 1 (.zip)
• Schweizerkarte (.pdf)

Links zum Thema

Informationen und Wettbewerb zum Finden der kürzesten Rundreise durch alle Ortschaften der Welt

• http://www.math.uwaterloo.ca/tsp/

Interaktive Applets

• http://www.math.uwaterloo.ca/tsp/games/index.html
• http://mgje.github.io/Interaktive_Experimente/rundreise/

Minimal aufspannende Bäume

• http://csunplugged.org/minimal-spanning-trees

Finden optimaler Touren mithilfe heuristischer Verfahren

• http://www.thi.uni-hannover.de/fileadmin/forschung/arbeiten/noehring-ba.pdf