TSP-Spiel

• Beschreibung
• Spiel starten
• Aufgabenstellung
• Dokumentation

Beschreibung

Ziel dieses Spiels ist es, die kürzeste Rundreise durch die vorgegebenen Städte zu finden. Jede Stadt muss also genau einmal besucht werden und die Reise endet dort, wo sie begonnen hat.

Im Konfigurationsdialog können Sie die Karte, die Anzahl der Städte und - bei der Gitternetzkarte - die Metrik auswählen. Die Metrik beschreibt, wie der Abstand zwischen zwei Städten berechnet wird:

• Euklidsche Metrik
  Dies ist die "übliche" Abstandsmessung: Der Abstand zwischen zwei Städten entspricht der Länge der geraden Strecke zwischen den Städten.
  Wenn also etwa Stadt A die Koordinaten (1|5) und Stadt B die Koordinaten (4|1) hat, so ist der Abstand der zwei Städte gleich 5.
• 1 - Metrik
  Hier wird der Abstand zwischen zwei Städten als Summe des horizontalen und des vertikalen Abstands berechnet.
  Für unsere zwei Beispielstädte ergibt sich als horizontaler Abstand 3, als vertikaler Abstand 4 und deshalb ein Gesamtabstand von 7.
• Maximum - Norm
  Dies ist die derzeit kniffligste Metrik. Ist der vertikale Abstand zwischen zwei Städten größer als der horizontale, so entspricht der Abstand der zwei Städte dem vertikalen Abstand, anderenfalls dem horizontalen.
  In unserem Beispiel mit horizontalem Abstand 3 und vertikalem Abstand 4 wäre der Abstand zwischen den zwei Städten also gleich 4.

Um eine Verbindung zu zeichnen, reicht es, nacheinander auf die beiden entsprechenden Städte zu klicken. Falls man eine Kante wieder entfernen will, so kann der Zeichenmodus durch einen Rechtsklick irgendwo in die Spielfläche verlassen werden. Anschließend löscht ein Rechtsklick auf eine Kante diese.

Jeder Knoten auf der Karte muss zweimal besucht werden. Ist das der Fall, wird der Knoten schwarz. Erst wenn alle Knoten zweimal besucht wurden, ist die Tour vollständig. Durch einen Klick auf "fertig" erhalten Sie die Auswertung Ihrer Tour.

---