Home > Informatik > Optimierungsprobleme

Workshop "Nearest neighbour" - 2

Teil 1 - Teil 2 - Teil 3 - Teil 4 - Teil 5

Die Klasse Stadtliste

Zielsetzung

Es soll eine Klasse Stadt geschrieben werden, die für das Zeichnen der einzelnen Städte verantwortlich ist. Jede Stadt soll in einer Java-Anwendung als roter Kreis mit einem schwarzen Rand dargestellt werden.

Die Klassen Stadt, Stadtliste und Anwendung

Attribute

In dieser Version hat die neue Klasse Stadtliste nur ein Attribut, nämlich einen Objektarray, der 16 Objekte der Klasse Stadt speichert. Man hätte diesen Array natürlich auch flexibel anlegen können, in diesem Fall müsste man dann die Länge des Arrays bzw. die Anzahl der tatsächlich vorhandenen Städte in einem eigenen Attribut speichern. In diesem Projekt ist die Zahl der Städte allerdings auf 16 festgelegt, daher ist ein solches Attribut nicht nötig.

Methoden

Der Konstruktor benötigt keine Parameter, da die Stadtliste direkt im Konstruktor festgelegt wird.

Eine paint()-Methode dient zum Zeichnen der Stadtliste in der Java-Anwendung. Dazu werden in einer for-Schleife einfach die paint()-Methoden der Stadt-Objekte aufgerufen.

Quelltext

import java.awt.*;

public class Stadtliste
{
    Stadt[] liste;
    
    public Stadtliste()
    {
       liste = new Stadt[16];
       
       liste[ 0] = new Stadt( 20, 50);
       liste[ 1] = new Stadt( 40,150);
       liste[ 2] = new Stadt( 60, 90);
       liste[ 3] = new Stadt( 80,350);
       liste[ 4] = new Stadt(130,120);
       liste[ 5] = new Stadt(130,235);
       liste[ 6] = new Stadt(200,420);
       liste[ 7] = new Stadt(220,340);
       liste[ 8] = new Stadt(250,130);
       liste[ 9] = new Stadt(280, 60);
       liste[10] = new Stadt(320,180);
       liste[11] = new Stadt(350,290);
       liste[12] = new Stadt(410,250);
       liste[13] = new Stadt(430,350);
       liste[14] = new Stadt(470,190);
       liste[15] = new Stadt(460,420);             
    }
    
    public void paint(Graphics g)
    {
       for (int i=0; i < liste.length; i++)
          liste[i].paint(g);
    }

}
Erläuterung

Die Positionen der 16 Städte werden hier direkt festgelegt. Alternativ könnte man natürlich zufällige Positionen wählen. Allerdings waren diese fixen Positionen sehr hilfreich bei der Entwicklung des eigentlichen Algorithmus. Werden jedes Mal zufällige Positionen generiert, ist das Überprüfen, ob eine kurze Tour gefunden wurde, recht schwierig.

Die Klasse Anwendung

Zielsetzung:

Diese Klasse steht für das Hauptprogramm des Projektes. Hier wird alles verwaltet und am Ende - im Teil 5 - wird die berechnete "optimale" Tour graphisch dargestellt.

import java.awt.*;
import javax.swing.*;

public class Anwendung extends JFrame
{
    Stadtliste land;
    
    public Anwendung()
    {
        land = new Stadtliste();
        setSize(500,500);
        setTitle("TSP: Nearest Neighbour-Methode");
        setResizable(false);
        setVisible(true);
    }

    public void paint(Graphics g)
    {
       land.paint(g);
    }

    public static void main(String[] args) 
    {
        new Anwendung();
    }
}
Erläuterungen

Hier musste nicht viel verändert werden. Statt Objekte der Klasse Stadt wird ein Objekt der Klasse Stadtliste getestet.