Jochen Pleines

Das Traveling-Salesman-Problem (TSP) ist gemeinhin erschöpfend erforscht. Für beliebige Anzahl von Orten (Knoten) gibt es wegen der mit Fakultät wachsenden Anzahl von TSP keine exakte Lösung. Die hier vorgestellte ZIP-Methode ändert zwar nichts daran, ist jedoch ein Quantensprung in den Berechnungen, weil - ohne Qualitätsverlust - die bekannten Berechnungen minimal werden. Das kann man z.B. leicht am Beispiel mit 10 Knoten erkennen. Das durch Zufall gefundene Verfahren ist zwar nicht neu und unter www.jochen-pleines.de eingehend beschrieben, aber bisher nur wenig wissenschaftlich erwähnt (Prof. Dr. Klaus Höher(+) Hochschule der Bundeswehr, München). Nachdem ich jetzt vor kurzem von Herrn Dipl. Ing. Helmut Berning (E-Mail: h.berning@gmx.de) angesprochen wurde, sollte das Verfahren vielleicht auch auf Wikipedia als Ergänzung der exakten TSP-Verfahren eröffentlicht werden. Über eine kurze Rückmeldung würde ich micht freuen.

ZIP-Methode (Reißverschluss-Verfahren): Zerlegt man einen symmetrischen Graphen (1 Komponente, n Kanten, n Knoten mit Knotengrad = 2) in zwei Teilgraphen (n/2 Komponenten, n/2 Kanten, n Knoten mit Knotengrad = 1), dann ist die mögliche Anzahl (=Mächtigkeit) aller Teilgraphen im Vergleich zur Mächtigkeit der Graphen minimal. Bei ungrader Knoten-Anzahl wird ein Pseudo-Knoten ergänzt. Die Ausprägung der Kante zwischen Knoten und Pseudo-Knoten ist hinreichend klein zu wählen; ggf. negativ ! Zwei Teilgraphen bilden dann einen Graphen, wenn der zweite (Komplement-)Teilgraph keine Kante des ersten Teilgraphen enthält. Mächtigkeit der Graphen: ( n-1)! / 2; Mächtigkeit der Teilgraphen: (n-1)! / (n/2-1)! x 2 *(n/2-1) Mächtigkeit des Komplement-Teilgraphen: (n/2-1)! x 2 *(n/2-1). Weiter ist die Summe der Längen (= Ausprägungen) der Kanten des gesuchten kleineren Teilgraphen kleiner/gleich der halben Summe der Ausprägungen der Kanten jedes! beliebigen Graphen. Ist der kleinste Teilgraph gefunden, dann bildet der Komplement-Teilgraph die Obergrenze aller relevanten (kleinen) Teilgraphen. Weil auch die Menge der Teilgraphen normal-verteilt ist, ist die Menge der relevanten Teilgraphen vergleichsweise gering. Ist - nach vorsichtiger Aussage – der kleinste Teilgraph festgestellt, so lässt sich - nach Wahrscheinlichkeit - auch der kleinste Graph berechnen. Dabei ist der kleinste Teilgraph nicht zwingend Teil des gesuchten kleinsten Graphen. Beispiel (10 Knoten): Mächtigkeit der Graphen: 181440; Mächtigkeit der Teilgraphen: 945. Mächtigkeit der Komplement-Teilgraphen: 384 Manuell kann die Berechnung mit einer EXEL-Tabbelle durchgeführt werden. Im Allgemeinen sind nur die kleinsten 20 der insgesamt 945 Teilgraphen relevant.