Traveling Salesman Problem

[JavaPro24]

Hey Leute,
ich habe ein Problem mit meinem TSP. Und zwar weiß ich nicht wie das geht. Hier die Aufgabenstellung:
1.Auf dem Bildschirm sind 10 Orte zu sehen.Ein Algorithmus berechnet einen Weg, der alle Städte besucht.
2.Die Länge des Weges wird ausgegeben.
Vielleicht kann mir ja einer helfen.
Euer JavaPro24

 

[mihe7]

ich habe ein Problem mit meinem TSP. Und zwar weiß ich nicht wie das geht.

LOL. Woran scheitert es denn?

Ansonsten:

Vielleicht kann mir ja einer helfen.

Die Forensuche? Das Thema gibt es hier öfter.

 

[MoxxiManagarm]

Du, niemand wird dir was vorkauen. Zeig zumindest mal deinen Codeansatz. Wie sind die Städte gespeichert? Wie sind vor allem die Verbindungen gespeichert? Haben die Städte Koordinaten oder sind die Verbindungen direkt bekannt?

Ansonsten:
https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden

 

[MoxxiManagarm]

Eventuell hilft dir ein kleiner Denkansatz. Versuche dich an das EVA-Prinzip zu halten. Ich habe die eigentliche Logik (Berechnen der Distanz zwischen den Städten sowie die Routenfidung) bewusst hier nicht mit aufgeführt.

package javaforum.org.javapro;

import java.util.Arrays;
import java.util.List;

public class Salesman {
       
    public static void main(String... args) {
        // Eingabe
        // examplarisch statisch
        List<City> cities = Arrays.asList(
                new City("A", 52.5164, 13.3777),
                new City("B", 49.9917, 8.41321),
                new City("C", 38.692668, -9.177944),
                new City("D", 50.0049, 8.42182)
        );
       
        // Verarbeitung: berechne Route mit der gewünschten Heuristic
        // examplarisch NearestNeighbour
        RoutePlanner planner = new NearestNeighbour();
        Route route = planner.getRoute(cities);
         
        // Ausgabe
        // examplarisch minimal auf Konsole
        System.out.println(route);
    }
}

Dieses Beispiel setzt voraus:
Klasse City mit Namen und Longitude + Latitude (inkl. Distanzberechnung zu einer anderen Stadt)
Interface RoutePlanner mit entsprechender Methode
Klasse NearestNeighbour, welche RoutePlanner implementiert (Logik der Routenfindung hier)
Klasse Route mit Städten und Distanz sowie toString()

 

[Xyz1]

Das Thema gibt es hier öfter

ja

Mit 5 Städten sieht TSP zum Bleistift so aus :

 

[mihe7]

Wusst ich es doch, auf @DerWissende ist halt Verlass

 

[Xyz1]

auf @DerWissende ist halt Verlass

imma

 

[bluejavaprogrammierer]

Hey Leute,
ich habe ein Problem mit meinem TSP. Und zwar weiß ich nicht wie das geht. Hier die Aufgabenstellung:
1.Auf dem Bildschirm sind 10 Orte zu sehen.Ein Algorithmus berechnet einen Weg, der alle Städte besucht.
2.Die Länge des Weges wird ausgegeben.
Vielleicht kann mir ja einer helfen.
Euer JavaPro24

Hallo, ich habe das gleiche Problem und kann garnichts. Kann mir bitte jemand helfen?
mfg

 

[MoxxiManagarm]

Hallo, ich habe das gleiche Problem und kann garnichts. Kann mir bitte jemand helfen?
mfg

Zeig mal was du bisher hast. Andernfalls können wir dir kaum mehr helfen als wikipedia

 

[mihe7]

Hallo, ich habe das gleiche Problem und kann garnichts. Kann mir bitte jemand helfen?

ROFL. Mit "ich kann gar nichts" kommst Du nicht weit.

Du kannst Dir z. B. überlegen, dass beim TSP Start- und Zielpunkt der Route identisch sind. Außerdem hast Du an jedem Punkt der Route bereits eine bestimmte Menge an Städten angefahren, die für die weitere "Reise" nicht mehr zur Verfügung stehen.

Demnach ist an jedem Punkt nur noch eine bestimmte Menge an Städten übrig. Jede dieser Städte stellt also den Startpunkt einer neuen Teilroute dar, die Du alle durchprobierst. Den Vorgang wiederholst Du jeweils(!) so lange, bis die Route vollständig ist, dann ermittelst Du die Kosten. Sind diese geringer als die bisher besten ermittelten, hast Du eine neue beste Route. Das war es schon.

Grafisch hat das @DerWissende oben schön verdeutlicht.

Das ganze "funktioniert" nur für eine kleine Anzahl an Städten, da die Zahl der Möglichkeiten faktoriell wächst. Für reale Anwendungen kommt man um Heuristiken nicht herum (zumindest darf man davon ausgehen, so lange das P-NP-Problem nicht gelöst ist).

 

[bluejavaprogrammierer]

Hallo,
habe jetzt einen guten Ansatz.
Meine Fragen jetzt sind, wie berechne ich den gesamten Weg, in welcher Reihenfolge sollen die Städte am besten gesucht werden und wie kann der Gesamtweg kürzer werden?
mfg

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.awt.Color;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.lang.Object;
import java.util.*;

public class TSP extends JFrame
{
    Graphics g;
    int x;
    int y;
    //int q1 = 0;
    //int q2;
    int anzahlOrte = 10;
    int zufallszahl;
    int kurz;
    ArrayList<Point> punkt = new ArrayList<Point>();
    ArrayList<Stadt> stadtList = new ArrayList<Stadt>();
    public TSP()
    {
        g = getGraphics();
        setBackground(Color.WHITE);
        setSize(800,800);
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        setLocationRelativeTo(null);
        setVisible(true);
        orte();
    }
    public void orte()
    {
        int a = 0;
        while(a<anzahlOrte)
        {
            x = (int) ((Math.random()*500+1)+100);
            y = (int) ((Math.random()*500+1)+100);
            stadtList.add(new Stadt(x,y));
            a++;
        }
        stadtList.get(0).abstand(stadtList.get(1));
    }
    public void paint(Graphics g)
    {
 
        for(Stadt s : stadtList)
        {
            g.setColor(java.awt.Color.red);
            g.fillOval(s.x,s.y, 10, 10);
      
        }
    }
}

*neue Klasse
public class Stadt
{

    public int x;
    public int y;
    int name;
    int id;

    public Stadt()
    {
    }
    public Stadt(int px, int py)
    {
        x = px;
        y = py;
    }
    public void abstand(Stadt s2)
    {

     
        double ergebnis;


        int dx = x-s2.x;
        int dy = y-s2.y;
        ergebnis = (Math.sqrt(dx^2+dy^2));
        System.out.println("Abstand: " + ergebnis);



    }
}


*neue Klasse
public class Hauptprogramm
{
    public static void main(String [] args)
    {

        TSP a = new TSP();

    }
  
}

 

[mihe7]

Schmeiß mal die ganzen Instanzvariablen raus, die nicht benötigt werden: g, x, y, punkt, zufallszahl, kurz. Über anzahlOrte könnte man noch diskutieren.

Für das TSP brauchst Du den euklidischen Abstand nicht, der quadratische reicht - dann sparst Du Dir das Berechnen der Quadratwurzel.

Deine Fragen sollten mit den vorherigen Kommentaren bereits beantwortet worden sein.

 

[MoxxiManagarm]

Unabhängig von dem Algorithmus und den nicht benötigten Algorithmus, ein paar generelle Anmerkungen:

public void paint(Graphics g)

- Es ist nicht empfohlen paint zu überschreiben, überschreibe stattdessen paintComponent.
- Außerdem würde ich nicht paint/paintComponent von JFrame überschreiben. Bitte füge eine Komponente dem JFrame hinzu, auf der du zeichnest. Das kann z.B. so aussehen:

frame.add(new JComponent() {
    @Override
    public void paintComponent(Graphics g) {
       // paint here
    }
});

g.fillOval(s.x,s.y, 10, 10);

Bitte mach x und y private, füge getter hinzu (Geheimnisprinzip)

ergebnis = (Math.sqrt(dx^2+dy^2));

Das wird außerdem so nicht funktionieren, weil ^ in Java nicht das macht was du dir vorstellst. ^ ist Binary XOR. Oder veranschaulicht:

2 ^ 5

010 (2)
101 (5)
---- (XOR =)
111 (7)

Bitte nimm stattdessen Math.pow

 

[MoxxiManagarm]

Und nochmal zum Denkanstoß:

Meine Fragen jetzt sind, wie berechne ich den gesamten Weg, in welcher Reihenfolge sollen die Städte am besten gesucht werden und wie kann der Gesamtweg kürzer werden?

Der Gesamtweg ist nichts anderes als die Summe der Abstände zwischen stadtList(i) und stadtList(i+1). Die stadtList muss dafür umsortiert werden, dafür kannst du eine Heuristik einsetzen, die Heuristiken sind im web zahlreich erklärt.

 

[needInput]

Würde es mit einem Evolutionären Algorithmus versuchen.
Gibt viele gute Seiten, in denen es dir erklärt wird. (Einfach mal Googlen)
z.B.
http://www.theprojectspot.com/tutor...lgorithm-to-the-travelling-salesman-problem/5