Der Strip-Algorithmus teilt die Fläche in k gleich breite vertikale Streifen; die Staedte im ersten Streifen werden von oben nach unten (mit aufsteigenden y-Koordinaten) besucht, dann die im zweiten Streifen von unten nach oben, dann im dritten Streifen wieder von oben nach unten usw. Als Anzahl der Streifen waehlt man am besten k=sqrt(N/3), wobei N die Anzahl der Städte ist. Der Strip-Algorithmus liefert schlechtere Lösungen (bei uniformer Verteilung in der Ebene 31% schlechter als das Optimum) als der in der Vorlesung behandelte (16%), ist dafür aber einer der schnellsten.
Da dieser Algorithmus kaum mehr als lineare Komplexität hat und die Zeit zu seiner Ausführung womöglich in der Zeit fuer die Ausgabe der Stadtliste und des .eps-Files untergeht, soll Ihr Programm diese Ausgaben nur auf Wunsch (z.B. per Command-line flag) machen und im Normalfall (der gemessen werden soll) nur die Länge der Tour ausgeben.
Natürlich können Sie, wenn Sie wollen, auch die Implementierung eines anderen Problems oder eines anderen TSP-Algorithmus' optimieren; allerdings hat das einige Nachteile: Sie müssen einen Teil der Zeit Ihrer Präsentation für die Erklärung des Problems und des Algorithmus aufwenden, und die Ergebnisse sind nicht direkt vergleichbar.
Bereiten Sie eine 15-20-minütige Präsentation vor. Da Sie dabei nicht soviel Zeit haben wie ich in der Vorlesung, präesentieren Sie die meisten Schritte nur im Überblick (also eventuell nur, wieviel er gebracht hat), und nur ein paar besonders interessante Schritte mit mehr Details. Besonders interessant sind u.a. die Schritte, die unerwartet viel oder wenig bringen.
Um einen Vergleich zwischen den verschiedenen Lösungen zu
ermöglichen, messen Sie mit perfex auf der b3 die Zyklen
für Ihre verschiedenen Varianten mit 100000 Städten (Erzeugung wie in
tsp1.c). Um zu sehen, ob
Sie tatsächlich den gleichen Algorithmus implementiert haben, wie die
anderen, geben Sie auch noch die Länge der Tour an.