English
عربى
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng ViệtGraphen und NetzwerkeProblem des Handlungsreisenden
Wir wollen uns noch einmal über Netzwerke und Karten Gedanken machen. Stelle dir vor, ein Lieferservice muss
Der Lieferwagen muss alle Städte besuchen, egal in welcher Reihenfolge. Beim Königsberger Brückenproblem wollten wir Wege finden, die jede Kante genau einmal entlangfahren. Jetzt wollen wir Pfade finden, die jeden Knoten genau einmal passieren. Diese Pfade werden Hamiltonkreise genannt.
Es gibt unzählige verschiedene Möglichkeiten für Hamiltonkreise in vollständigen Graphen. Tatsächlich können wir jeden beliebigen Knoten als Startpunkt wählen und dann eine der übrigen Städte in beliebiger Reihenfolge auswählen:
Diagramm kommt bald…
Diagramm kommt bald…
In einem Graphen mit 8 Städten muss jeder Hamiltonkreis auch 8 Städte enthalten. Somit gilt:
- Es gibt 8 Auswahlmöglichkeiten für die 1. Stadt.
- Nachdem die erste Stadt ausgewählt wurde, gibt es nur noch 7 Auswahlmöglichkeiten für die 2. Stadt.
- Danach gibt es 6 Auswahlmöglichkeiten für die 3. Stadt.
- Weiter geht's mit 5 Auswahlmöglichkeiten für die 4. Stadt.
- Dann gibt es noch 4 Auswahlmöglichkeiten für die 5. Stadt.
- …
- Schließlich bleibt für die 8. Stadt nur noch 1 Wahl übrig.
Dies bedeutet, dass es insgesamt 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40 320 mögliche Pfade gibt. Eine Kurzschreibweise für dieses Produkt ist 8! oder Faktor 8.
Du kannst dir vorstellen, dass es unter Umständen nicht möglich ist, direkt zwischen zwei Städten zu reisen, ohne dabei über eine andere Stadt zu fahren. In diesem Fall haben wir es mit keinem vollständigen Graphen mehr zu tun, und es wird viel schwieriger, die Anzahl der Hamiltonkreise zu finden, falls es überhaupt welche gibt.
Bisher haben wir die Tatsache ignoriert, dass einige Städte weiter voneinander entfernt sein könnten als andere. Im wirklichen Leben ist dies jedoch eine sehr wichtige Überlegung: Wir wollen nicht nur einen Weg finden, sondern den kürzesten. Man nennt dies das Problem des Handlungsreisenden. Es muss nicht nur im Transport- und Logistikbereich gelöst werden, sondern auch bei der Positionierung von Transistoren auf Mikrochips, um immer schnellere Computer herzustellen, oder bei der Analyse der Struktur der
Eine einfache Methode wäre es, alle möglichen Wege auszuprobieren, die Länge jedes Weges zu ermitteln und dann den kürzesten zu wählen. Wie auch immer, wir haben gerade gezeigt, dass es selbst mit nur
Leider gibt es keinen effizienteren Algorithmus, um das Problem des Handlungsreisenden zu lösen. Stattdessen haben Mathematiker und Informatiker verschiedene Algorithmen entwickelt, die gute Lösungen finden, auch wenn sie möglicherweise nicht die besten sind. Solche Algorithmen, die nur Näherungslösungen liefern, werden als Heuristiken bezeichnet.
Versuche, die Städte auf dieser Karte neu anzuordnen, und schau dir an, wie sich der kürzeste Weg zwischen ihnen verändert. Du kannst Städte entfernen, indem du sie anklickst, und du kannst Städte hinzufügen (bis zu 8), indem du irgendwo auf die Karte klickst:
Der Greedy-Algorithmus (oder Nearest-Neighbor-Algorithmus, "Nächster-Nachbar" bzw. "gieriger" Algorithmus) ist sehr einfach: Du beginnst in einer zufälligen Stadt und bewegst dich nacheinander in die jeweils nächstgelegene Stadt, die du noch nicht besucht hast. Wenn du alle Städte besucht hast, hältst du an.
Animation kommt bald…
Man kann zeigen, dass die Wege, die mit dem Greedy-Algorithmus gefunden werden, im Durchschnitt 25% länger sind als der kürzestmögliche Weg.
Der 2-Opt Algorithmus beginnt mit einem zufälligen möglichen Pfad. Dann wählst du wiederholt zwei Kanten aus und vertauschst sie, wenn das die Länge des Pfades verringern würde. Du hörst auf, wenn du die Länge nicht weiter reduzieren kannst, indem du irgendwelche Paare von Kanten vertauschst.
Animation kommt bald…
Es stellt sich heraus, dass die Natur, lange bevor es Computer überhaupt gab, schon einen schlaueren Weg gefunden hatte, um die Wege zwischen verschiedenen Orten zu optimieren: in Ameisenkolonien.
Ameisen wollen möglichst kurze Wege zwischen ihrem Nest und möglichen Nahrungsquellen finden. Sie können miteinander durch Chemikalien kommunizieren, die sie auf ihrem Weg hinterlassen und denen andere Ameisen folgen können.
- Die Ameisenkolonie sendet viele Späher aus, die sich zunächst in zufällige Richtungen bewegen. Sobald sie Nahrung gefunden haben, kehren sie zurück und hinterlassen eine Spur von Pheromon.
- Andere Ameisen neigen dazu, wenn sie eine Spur finden, einer zu folgen die sie zum Essen führt. Auf ihrer Rückreise geben sie mehr Pheromon ab und verstärken so den Weg.
- Mit der Zeit verdunstet das Pheromon. Je länger ein Weg ist, desto länger brauchen Ameisen, um sich auf ihm fortzubewegen, und so hat das Pheromon mehr Zeit, um zu verdampfen. Kurze Wege hingegen können schneller verstärkt werden, sodass ihre Stärke schneller zunimmt.
Diagramm kommt bald…
Ameisenalgorithmen (Ant Colony System - ACS) versuchen, dieses Verhalten auf Computern nachzubilden, indem sie viele "virtuelle" Ameisen zum Einsatz bringen. Sie können schnell sehr gute Lösungen für das Problem des Handlungsreisenden finden.
Eine besonders nützliche Eigenschaft der ACS-Algorithmen ist, dass sie ständig ausgeführt werden und sich in Echtzeit an Änderungen des Graphen anpassen können. Diese Änderungen können in Straßennetzen durch Autounfälle und Straßensperrungen oder auf Webservern durch Überlastungen in Computernetzwerken verursacht werden.
Das Problem des Handlungsreisenden ist
Die Entwicklung eines schnellen und genauen Algorithmus hätte schwerwiegende Auswirkungen auf den Bereich der Informatik: es würde bedeuten, dass es schnelle Algorithmen für alle NP-hard-Probleme gibt. Es würde auch den größten Teil der Sicherheitsmaßnahmen im Internet aushebeln, die sich darauf verlassen, dass bestimmte Probleme sehr schwer für Computer zu lösen sind.
Einen schnellen Algorithmus zu finden, um das Problem des Handlungsreisenden zu lösen, würde auch eines der berühmtesten offenen Probleme in Mathematik und Informatik lösen, das P versus NP Problem. Es ist eines der sieben