Das Institut für Rechnergestützte  Wissensverarbeitung (KBS) der Universität Hannover hat 1996 als „Weihnachtsrätsel“ die Aufgabe gestellt, für 26 europäische Hauptstädte die kürzeste Rundreise zu finden. Die Aufgabe mit Lösungen wurden in das Internet gestellt. Die Entfernungsmatrix ist hier abgedruckt, weil inzwischen die Internet-Seiten entfernt wurden. Heuristisch wurde als kleinste Rundreise eine Rundreise von 16.189 km ermittelt, ohne den Nachweis, ob es sich hierbei um die optimal kürzeste Rundreise handelt. Mit der neuen algebraischen Lösungsmethode kann nachgewiesen werden, dass diese heuristisch gefundene kleinste Rundreise von 16189 km auch die optimale Rundreise ist.

Neuer algebraischer Lösungsweg:
Vor der Berechnung wurden die Daten manuell nach 3.2.2. optimal aufbereitet. Ziel ist es, bei der begrenzten Enumeration möglichst frühzeitig irrelevante Teilgraphen ausscheiden zu können. Folgende Einsparungseffekte werden durch einen Abbruch nach der entsprechenden Kante erzielt:

Tabelle 4.9. Einsparungen bei Abbruch

Es lohnt sich also,  möglichst frühzeitig die Berechnung abbrechen zu können.

Drei Größen beeinflussen günstig das Backtracking:

1. ein vorher heuristisch gefundener möglichst kleiner Ausgangswert,

2. eine für das Verfahren sinnvolle Nummerierung der Knoten und

3. die noch ausstehenden Kantenlängen je Kantenplatz. 

Zu 1 (Ausgangswert)
Der kleinste heuristisch gefundene Gesamtgraph betrug 16.189 km und setzte sich aus den beiden Teilgraphen von 7331 km und 8858 km zusammen. Wie sich später herausgestellt hat, war diese Vorgabe sehr günstig, jedoch nicht zwingend notwendig. Bereits der kleinste Teilgraph (6845 km) mit seinem kleinsten Komplement-Teilgraphen (9912 km) ergeben schon einen Gesamtgraphen von nur 16.757 km. 

Zu 2 (Knotennummerierungsregel)
Gerade in diesem Beispiel ist eine Knoten-Nummerierung in alphabetischer Reihenfolge der Städtenamen schon wegen der zentralen Lage von Amsterdam als ersten Knoten ungünstig, weil die Abweichungen der Kanten dieses Knoten im Vergleich zu den Abweichungen der Kanten anderer Knoten relativ gering sind. Es wurde deshalb eine Knoten-Umnummerierung absteigend nach der Größe der Abweichung aller Kantenlängen je Knoten vorgenommen. Diese Umnummerierung erzielt gute Ergebnisse, ist aber nicht zwingend. Es können auch andere Methoden angewandt werden.

Tabelle 4.10. Knoten-Umnummerierung

Für die minimalen Kantenlängen der einzelnen Knoten ergibt sich von der kleinsten bis zur größten Länge diese Sortierung: 220, 256, 280, 297, 305, 312, 337, 367, 371, 383, 407, 409 ....

Die Kanten der jeweiligen Anfangsknoten (s.o.) verteilen sich auf die einzelnen Kantenplätze im Teilgraphen wie folgt:

Tabelle 4.11. Beziehung zwischen Kanten und Kantenplatz

Bemerkung:
Umnummerierung und die Berechnung der ausstehenden Mindestkanten-längen sind abhängige Verfahren. Erst aufgrund der Festlegung der Knoten-Nummer kann die Mindestlänge der noch ausstehenden Kanten für jeden einzelnen Kantenplatz bestimmt werden.

Zu 3. (Mindestkantenregel)
Für jeden Kantenplatz ist die Gesamt-Mindestlänge aller noch ausstehenden Kanten zu berechnen. Die exakten Mindestlängen lassen sich in diesem Beispiel nur maschinell bestimmen. Gute Näherungswerte erhält man aber auch manuell unter Berücksichtigung der Minimalkanten.

Tabelle 4.12. Mindestkanten je Kantenplatz

Programmierte Berechnungen beim Beispiel mit 26 Kanten:

Der heuristisch gefundene kleinste Gesamtgraph mit einer Kantenlänge von 16189 km setzt sich aus den beiden Teilgraphen mit einer Länge von 7331 km und 8858 km zusammen. Mittelwert der Kantenlängen ist 8094 km. Des weiteren wurde durch ein Programm der kleinste Teilgraph mit einer Kantenlänge von 6845 km berechnet. Die Länge des zugehörigen kleinsten Komplement-Teilgraphen beträgt 9912 km.

Zu ermitteln war jetzt, ob es einen kleineren Gesamtgraphen von weniger als 16189 km gibt. Bei diesem Gesamtgraph muss der  kleinere Teilgraph zwingend eine Kantenlänge zwischen 6845 km und 8094 km haben. Hat keiner der Teilgraphen mit einer Kantenlänge bis zu 8094 km einen entsprechenden Komplement-Teilgraph, der mit diesem eine kleinere Gesamtkantenlänge von 16189 km bildet, so ist damit der optimale kleinste Gesamtgraph bereits gefunden.

Dazu wurden  die Teilgraphen mit folgenden Kantenlängen gezählt

Tabelle 4.13. Ergebnisse des Beispiels 4.3

Zu berechnen waren also nur 2725 Teilgraphen. Aus der Menge der 293.380 Komplement-Teilgraphen bis zu einer Kantenlänge von 9344 km war dazu jeweils der zugehörige kleinste Komplement-Teilgraph zu ermitteln. Bereits nach 40 Durchläufen verringerte sich die Anzahl der Komplement-Teilgraphen auf 57200. Es wurde kein kleinerer Gesamtgraph gefunden. Damit ist bewiesen, dass der Gesamtgraph mit einer Kantenlänge von 16189 km der optimale kleinste Graph ist.

Abb. 4.1 geografische Darstellung des optimalen Graphen

Aus den beiden Teilgraphen wird der Gesamtgraph bzw. sein Spiegelbild gebildet:

Tabelle 4.14 Optimaler Teilgraph und zugehöriger min. Komplement-Teilgraph

 

Tabelle 4.15. Optimaler Gesamtgraph und Spiegelbild des optimalen Gesamtgraphen

Nr.	Kante	Länge		Nr.	Kante	Länge
1-3	Lissabon-Madrid	639		1-23	Lissabon-Barcelona	1276
3-13	Madrid-Rom	952		23-24	Barcelona-Genf	772
13-21	Rom-Mailand	565		24-26	Genf-Paris	517
21-22	Mailand-Zürich	305		26-18	Paris-London	449
22-25	Zürich-Frankfurt / M.	415		18-19	London-Brüssel	371
25-20	Frankfurt / M. -Prag	504		19-17	Brüssel-Amsterdam	220
20-15	Prag-Wien	312		17-16	Amsterdam-Berlin	669
15-11	Wien-Budapest	256		16-12	Berlin-Kopenhagen	367
11-10	Budapest-Belgrad	428		12-9	Kopenhagen-Oslo	588
10-7	Belgrad-Sofia	409		9-8	Oslo-Stockholm	549
7-5	Sofia-Athen	847		8-2	Stockholm-Helsinki	383
5-4	Athen-Istanbul	1141		2-14	Helsinki-Warschau	1130
4-6	Istanbul-Bucarest	638		14-6	Warschau-Bucarest	1487
6-14	Bucarest-Warschau	1487		6-4	Bucarest-Istanbul	638
14-2	Warschau-Helsinki	1130		4-5	Istanbul-Athen	1141
2-8	Helsinki-Stockholm	383		5-7	Athen-Sofia	847
8-9	Stockholm--Oslo	549		7-10	Sofia-Belgrad	409
9-12	Oslo-Kopenhagen	588		10-11	Belgrad-Budapest	428
12-16	Kopenhagen-Berlin	367		11-15	Budapest-Wien	256
16-17	Berlin-Amsterdam	669		15-20	Wien-Prag	312
17-19	Amsterdam-Brüssel	220		20-25	Prag-Frankfurt / M.	504
19-18	Brüssel-London	371		25-22	Frankfurt / M.-Zürich	415
18-26	London-Paris	449		22-21	Zürich-Mailand	305
26-24	Paris-Genf	517		21-13	Mailand-Rom	565
24-23	Genf-Barcelona	772		13-3	Rom-Madrid	952
23-1	Barcelona-Lissabon	1276		3-1	Madrid-Lissabon	639
		16189				16189