Zur Idee der ZIP-Methode ein paar Beispiele aus dem täglichen Leben:

1. Beim Lotto "6 aus 49" werden in jeder Woche 6 aus 49 möglichen Zahlen gezogen. Dabei können dieselben Zahlen in verschiedener Reihenfolge gezogen werden; bei 6 Zahlen sind es genau 720 Möglichkeiten. Dem Gewinner ist die Reihenfolge aber gleichgültig, ihm kommt es nur auf die richtigen Zahlen an. Im übrigen werden am Ende alle Zahlen in ihrer "natürlichen" Reihenfolge angezeigt und nicht in der Reihenfolge, wie sie gezogen wurden.

2. Der Preis für alle Waren eines Warenkorbes ist (hoffentlich) immer gleich, unabhängig davon, in welcher Reihenfolge die Kassiererin die Preise der einzelnen Waren eintippt. 

3. Nehmen Sie drei Farbstifte und legen Sie diese in einer Reihe auf den Tisch. Wie viele verschiedene Möglichkeiten haben Sie? Genau 48! Wollen Sie die Länge der Stifte wissen, reicht es aber aus, die Stifte nur einmal zu messen.

4. Gleiches gilt für ein Domino-Spiel. Haben Sie drei Steine, ist es für die Augenzahl der Steine unerheblich, wie Sie diese Steine vor sich aufbauen. Und in welcher Reihenfoge Sie Ihre Steine dann beim Spiel einsetzen, hängt außerdem vom Gegenspieler ab.   

Oft spielt gerade die Reihenfolge bzw. die Richtung für die eigentliche Fragestellung keine Rolle, obwohl wir bei der Ermittlung des Ergebnisses immer in irgendeiner Reihenfolge - Schritt für Schritt - vorgehen. Bei einer Rundreise wird zwar jeder Ort in einer bestimmten Reihenfolge berührt, gesucht wird beim TSP jedoch nicht die Reihenfolge der besuchten Orte sondern eine minimale Entfernung zwischen allen Orten. Dabei kommt es für das Ergebnis nicht darauf an, auf welche Art und Weise dieses ermittelt wird. Der Autor nutzt in seinen Beispielen für die ZIP-Methode die Aufzählung (Enumeration), die für kleine Bereiche völlig ausreichend ist. Als generelle Lösung für das allgemeine TSP ist die Enumeration in der Tat eine absurde Idee, wie auch M. Grötschel in einer unveröffentlichen e-mail schreibt. Um die Enumeration geht es bei der ZIP-Methode aber nicht. Durch die Zerlegung jeder Rundreise in zwei gleichstrukturierte Teile und ihre Zusammenführung "wie ein Reißverschluss (ZIP)" gelingt es dem Autor, mehrfache Berechnungen derselben Teile zu vermeiden und so die Anzahl der notwendigen Berechnungen zu minimieren.

(23.07.2005)