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:

Einzelne Teile aus dem Dossier zum Download:

Links zum Thema

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

Interaktive Applets

Minimal aufspannende Bäume

Finden optimaler Touren mithilfe heuristischer Verfahren