Ist der Weg wirklich optimal ?
Hätte es aber besser gehen können ? Beim vorherigen Beispiel sicherlich nicht. Wir wandeln den Graphen aber einmal nur an einer Stelle ab:
Bleiben wir wieder bei der ersten Entscheidung, dem Weg 1 - 2 - 7 - 3 - 4 - 5 - 6 - 1. Dann hat der Rundweg nun eine Länge von 53. Wir hätten uns aber statt des "Umweges" bei 2 über 7 auch für den direkten Weg zu 3 entacheiden können. Das hat nun andererseits den Vorteil, dass wir unten die langen Kante 5 - 6 vermeiden können und statt dessen hier den Weg über den Knoten 7 nehmen. In diesem Fall ist der Weg dann nur 49 lang, also deutlich kürzer als der andere ! |
|
Wie aber hätten wir das am Knoten 1 ahnen können ? Das Problem ist doch, dass wir am Knoten 1 allein die lokale Information: die kürzeste Kante von hier aus ist die Kante 1-2 verwendet haben und auch nur verwenden konnten.
Nun ist in diesem einfachen Graphen die Zahl der überhaupt möglichen Rundwege nicht so groß, dass man nicht alle Lösungen untersuchen könnte. Für das Beispiel hier gibt es nämlich nur die folgenden Wege:
Weg |
Länge |
1 - 2 - 7 - 3 - 4 - 5 - 6 - 1 |
53 |
1 - 2 - 3 - 4 - 5 - 7 - 6 - 1 |
49 |
1 - 2 - 3 - 4 - 5 - 6 - 7 - 1 |
56 |
1 - 7 - 2 - 3 - 4 - 5 - 6 - 1 |
55 |
Ebenso zeigt die Tabelle für das Original - Beispiel, dass der zunächstgefundene Weg optimal war.
Weg |
Länge |
1 - 2 - 7 - 3 - 4 - 5 - 6 - 1 |
36 |
1 - 2 - 3 - 4 - 5 - 7 - 6 - 1 |
49 |
1 - 2 - 3 - 4 - 5 - 6 - 7 - 1 |
42 |
1 - 7 - 2 - 3 - 4 - 5 - 6 - 1 |
43 |
|
|