Die Klasse Stadt
Quelltext der Klasse Stadt
Autor: Ulrich Helmich 2016, Lizenz: siehe Seitenende.
Den Quelltext der Klasse Stadt finden Sie unter Stadt.java zum Download.
Aufgabe der Klasse Stadt ist es, eine einzelne Stadt zu zeichnen, und zwar als roten Kreis mit 10 Pixeln Durchmesser und einem dünnen schwarzen Rand. Außerdem wird der Name der Stadt ausgegeben sowie der Index der Stadt und der Index der nächsten Stadt.
Attribute
int xPos, yPos; String name; int nummer,next; boolean inTour;
xPos und yPos sind die Koordinaten der Stadt. Allerdings nicht in Pixeln, sondern in Zentimetern. Dazu muss ich sagen, dass ich die "Landkarte" vorher mit einem Zeichenprogramm erstellt habe und dann einfach die Zentimeter-Koordinaten der Städte übernommen habe.
name ist der Name der Stadt.
nummer ist der Index der Stadt in dem Array der Klasse StadtArray.
next ist der Index der nächsten Stadt in der jeweiligen Tour. Dazu muss man wissen, dass in der Klasse StadtArray die Städte zunächst in einem einfachen Array gespeichert werden. Das Attribut nummer entspricht dann dem Index der Stadt in diesem Array. In dem Array sind die Städte so gespeichert, wie sie eingespeist worden sind. Das ist natürlich noch keine kurze Rundreise, diese muss ja erst durch einen Algorithmus gefunden werden. Eine solche Rundreise wird in dem Java-Projekt jetzt als "Tour" bezeichnet. Und das Attribut next spielt hierbei eine wichtige Rolle, zeigt es doch die nächste Stadt in der Tour (nicht im Array, sondern in der berechneten Tour).
inTour ist ebenfalls ein wichtiges Attribut, das dem nearest neighbour-Algorithmus mitteilt, ob die jeweils untersuchte Stadt bereits in der berechneten Tour ist oder nicht.
Methoden
Methoden gibt es nicht viele in dieser Klasse. Der Konstruktor übernimmt von der Klasse StadtArray den Index der Stadt, die Position und den Namen. Die Attribute next und inTour werden auf default-Werte gesetzt. Aus den übergebenen Zentimeter-Daten berechnet der Konstruktor dann die Pixel-Daten, indem er die Zentimeter-Daten mit dem Faktor 30 multipliziert und in int-Zahlen konvertiert.
Die paint()-Methode ist für das Zeichnen der Stadt zuständig. Wenn die Stadt bereits in einer Tour ist, wird der Name der Stadt, die Nummer und der Index der nächsten Stadt blau gezeichnet, ansonsten rot.
Die Klasse StadtArray
Diese Klasse ist recht umfangreich und kann hier nur stückweise als Screenshot gezeigt werden. Schuld an der Länge sind auch die vielen Kommentare, die ich in den Quelltext eingebaut habe.
Quelltext-Auszug der Klasse StadtArray()
Autor: Ulrich Helmich 2016, Lizenz: siehe Seitenende.
Den Quelltext können Sie übrigens als Java-Datei herunter laden.
Attribute
Kernstück der Klasse ist der Array stadt, der 32 Objekte der Klasse Stadt aufnehmen kann (das sollte am Anfang erst mal reichen).
stadt ist ein Array, der Objekte der Klasse Stadt aufnehmen kann.
anzahl speichert, wie viele Städte der Array tatsächlich enthält.
Methoden
erzeuge()
erzeuge ist dafür zuständig, dass überhaupt Städte in den Array eingespeichert werden. Ich habe dazu eine Karte von NRW ausgewertet und die Koordinaten der Städte in Zentimetern übertragen.
Dann wird in den Zeilen 46 - 48 eine default-Tour erzeugt, indem einfach das Attribut next einer jeden Stadt auf die nächste Stadt in dem Array gesetzt wird. Dies ist natürlich noch keine kurze Tour, aber dafür ist dann ja auch der eigentliche Algorithmus zuständig.
entfernung()
entfernung berechnet die Entfernung zwischen zwei gegebenen Städten. Hier der Quelltext als Screenshot:
Als Parameter werden die Indices der beiden Städte in dem Array übergeben. Dann erfolgt die bekannte Berechnung der Entfernung nach der Schul-Methode.
Quelltext-Auszug der Klasse StadtArray()
Autor: Ulrich Helmich 2016, Lizenz: siehe Seitenende.
naechsteStadt()
naechsteStadt ermittelt die am nächsten liegende Stadt zur gegebenen Stadt.
Zunächst wird die lokale Hilfsvariable min auf einen enorm hohen Wert gesetzt, der mit Sicherheit höher ist als alle Entfernungen, die in der Karte vorkommen.
Dann starten wir in Zeile 70 mit der ersten Stadt des Arrays, also mit der Stadt mit dem Index 0.
In der Hauptschleife wird zunächst die erste Stadt des Arrays gesucht, die noch nicht in der Tour enthalten ist. Die Variable start wird auf den entsprechenden Index gesetzt.
Bei der Entwicklung des Programm kam es zu einem fatalen Fehler, den zu beseitigen längere Zeit gedauert hat. Als Ursache stellte sich dann heraus, dass in der while-Schleife die lokale Variable start einen Wert von anzahl oder größer annehmen konnte, was dann zu Laufzeitfehlern führte (Array out of bounds...). Daher habe ich dann die Sicherheitsabfrage in den Zeilen 78 - 81 in den Quelltext eingebaut. Seitdem läuft das Programm fehlerfrei.
Dann wird die Entfernung zwischen der aktuellen Stadt (Index s) und der gefundenen Stadt (Index start) berechnet und mit dem aktuellen Minimum verglichen. Ist die Entfernung kürzer als das Minimum, so wird das Minimum aktualisiert und der Index dieser Stadt in der Hilfsvariable index gespeichert.
Dann wird die nächste Stadt untersucht, die noch nicht in der Tour enthalten ist; die Schleife beginnt von vorn.
nearestneighbour()
nearestneighbour ist die Hauptmethode der Klasse.
Quelltext-Auszug der Klasse StadtArray()
Autor: Ulrich Helmich 2016, Lizenz: siehe Seitenende.
Zunächst wird die erste Stadt des Arrays in die Tour aufgenommen (Index s = 0); das Attribut inTour dieser Stadt wird auf true gesetzt, die nächste Stadt wird berechnet und der Index derselben wird im Attribut next der ersten Stadt gespeichert. Dann wird die Hilfsvariable s auf den Index dieser Nachfolgestadt gesetzt. Anschließend wird die for-Schleife erneut durchlaufen.
Wenn alle Städte in die Tour aufgenommen sind, wird die letzte Stadt (s hat inzwischen den Wert anzahl-1 angenommen) mit der ersten Stadt des Arrays verknüpft, und die Rundreise ist geschlossen.
paint()
Die gesamte Tour wird gezeichnet. Zunächst wird eine Stadt gemalt, durch Aufrufen der paint-Methode der Klasse Stadt. Dann werden die Koordinaten dieser Stadt und die Koordinaten der nächsten Stadt in Hilfsvariablen gespeichert und anschließend durch eine Linie verbunden.
Die Klasse StadtApp
Quelltext der Klasse StadtApp()
Autor: Ulrich Helmich 2016, Lizenz: siehe Seitenende.
Den Quelltext des Applets habe ich recht kurz gehalten. Es wird ein Objekt der Klasse StadtArray deklariert und initialisiert, dann werden die Städte erzeugt und der nearest neighbour-Algorithmus wird aufgerufen. In der paint-Methode wird dann die paint-Methode der Klasse StadtArray aufgerufen. Das war's.
Ausgabe des Applets StadtApp()
Autor: Ulrich Helmich 2016, Lizenz: siehe Seitenende.
Hier ein Screenshot des Applets, der 17 Städte Ostwestfalens miteinander verbindet. Unter dem Stadtnamen wird der Index der Stadt sowie der Index der Nachfolgestadt angezeigt.
Ausgabe des Applets StadtApp()
Autor: Ulrich Helmich 2016, Lizenz: siehe Seitenende.
Hier wurde die Liste der Städte auf 21 Städte erweitert. Auch jetzt funktioniert der Algorithmus ganz gut. Man sieht aber auf den ersten Blick, dass die Route nicht optimal ist. Die Strecken von Bohmte nach Bielefeld sowie von Petershagen nach Bielefeld sind auffällig lang. Aber so arbeitet der nearest neighbour-Algorithmus eben!
Auf der nächsten Seite beschreibe ich eine Optimierung des nearest neighbour-Algorithmus, die wirklich kurze Touren liefert.
Seitenanfang -
weiter mit der Optimierung