Modellierung und Simulation (interdisziplinär) – Optimierungsaufgaben
Ein weiteres einfaches Beispiel, wo mathematische Modelle häufig eingesetzt werden und auch deren Nutzen hinterher unmittelbar einleuchtet, sind Optimierungsaufgaben. Das Problem des Handlungsreisenden (Englisch: Traveling Salesman Problem (TSP)) zählt dabei zu den berühmtesten Optimierungsaufgaben und kommt in den unterschiedlichsten Problemfeldern vor.
In seiner einfachsten Form beschreibt es die Suche nach der optimalen Route durch eine gegebene Anzahl von Städten. Man stelle sich also beispielsweise vor, man plane einen Australien-Urlaub. Weil dieser Kontinent so weit weg liegt und die Reise ohnehin teuer ist, möchte man schon beim ersten Mal möglichst viele Städte bzw. Sehenswürdigkeiten besuchen – wer weiß schon, ob man je wieder nach Australien kommt? Also stellt man eine Liste der gewünschten Sehenswürdigkeiten auf und trachtet dann danach, die Reise durch Australien derart zu planen, dass sich entlang der Route alle Sehenswürdigkeiten befinden. Auf der Suche nach einer optimalen Route reicht es dabei jedenfalls aus, jede Sehenswürdigkeit genau einmal zu besuchen.
Ansonsten ist die Frage nach der Optimalität einer Route nicht immer ganz klar. So könnte z.B. die kürzeste Route bezogen auf die Distanz gemeint sein, oder die kürzeste Route bezüglich der Reisezeit, oder beispielsweise auch die günstigste Route was die Reisekosten betrifft.
Angenommen, wir wollen möglichst kostengünstig durch Australien reisen, dann werden somit jeder direkten Verbindung zwischen zwei Sehenswürdigkeiten die jeweiligen Reisekosten zugewiesen. Je nachdem, ob die Reisekosten unabhängig von der Reiserichtung sind, unterscheidet man das sogenannte symmetrische (d.h. es spielt keine Rolle ob man etwa von Sydney nach Brisbane reist oder in die umgekehrte Richtung) bzw. das asymmetrische Handlungsreisendenproblem (bei letzterem würde es preislich sehr wohl einen Unterschied machen, ob man etwa von Sydney nach Brisbane reist oder von Brisbane nach Sydney).
Die Einfachheit der Aufgabe würde eigentlich nahelegen, dass es dafür auch eine einfache Lösung gibt. Tatsächlich ist die optimale Route bei einer geringen Anzahl an Städten noch durch ein primitives Ausprobieren und Vergleichen aller Möglichkeiten (Brute-Force-Methode) möglich. Aber mit wachsender Anzahl der Städte stößt diese Methode schon sehr bald an ihre Grenzen, wie das folgende Beispiel zeigt.
Das Quellen- und Literaturverzeichnis zu dieser Seite finden Sie hier.
Aufgabe 1 von 3
Sie planen Ihren ersten Australienaufenthalt und suchen eine möglichst kostengünstige Tour durch verschiedene Städte. Überlegen Sie sich, wie viele mögliche Routen es gibt, bei denen Sie jede Stadt genau einmal besuchen. Dabei wollen wir voraussetzen, dass die Kosten unabhängig von der Reiserichtung sind, es also preislich keinen Unterschied macht wo die Reise beginnt und wo sie endet. Zudem soll jede Stadt von jeder Stadt aus erreichbar sein. Wie viele Routen müssten Sie – je nach Anzahl der Städte – miteinander vergleichen?
Wie viele Routen müssen Sie bei 4 Städten miteinander vergleichen?
Hinweis: Versuchen Sie zunächst für wenige Städte alle Möglichkeiten tatsächlich abzuzählen. Vielleicht entdecken Sie so ein allgemeines Bildungsgesetz um die nachfolgenden Fragen zu beantworten?
Kreuzen Sie die richtige Antwort an.
