Methoden Traveling Salesman Tour

[Karrzun]

Heyho zusammen,

ich bin gerade dabei, für eine gegebene Menge an Punkten* im R² eine möglichst optimale Traveling Salesman Tour zu berechnen. Prinzipiell gilt, dass alle Punkte von allen anderen Punkten aus erreichbar sind - es werden keine extra Wege/Kanten angegeben. Natürlich können auch Punkte direkt übereinander liegen. Mein Plan ist folgender:
1. Adjazenzmatrix aufstellen, die alle Abstände der Punkte untereinander enthält
2. Aus dieser Adjazentmatrix mit dem Algorithmus von Kruskal einen Spannbaum aufstellen
3. Entlang des Spannbaums eine Tiefensuche durchführen und mir die Reihenfolge der Knoten in einer Liste speichern
4. Diese Liste bildet (ohne eventuell noch vorhandene Duplikate?) meine Traveling Salesman Tour

Ausgegeben wird die Tour dann durch ein Polygon**, dass die Punkte in entsprechender Reihenfolge verbindet.


So sieht man Code bisher aus:

public class EuclideanTSP extends AlgorithmPlugin {  
    private List<Edge> edges;
    private int verticesCount;
    public static final double MAX_VALUE = Double.POSITIVE_INFINITY;
    private int visited[];
    private double spanning_tree[][];
    private List<Point> depthSearch;
    private boolean known[];
    private List<Point> salesmanRoute;
    private AlgorithmInput points;

    public EuclideanTSP() {
        points = new InputCollectionPoint();

        points.setName("points");

        inputs.add(points);
    }

    @Override
    public boolean startAlgorithm() {
        if (hasValidInput() == false) {
            return false;
        }
        result.clear();
      
        @SuppressWarnings("unchecked")
        List<Point> pointsList = (List<Point>) this.points.getValue();
      
        verticesCount = pointsList.size();
        edges = new LinkedList<Edge>();
        visited = new int[verticesCount + 1];
        spanning_tree = new double[verticesCount + 1][verticesCount + 1];
        depthSearch = new LinkedList<Point>();
        known = new boolean[verticesCount + 1]; //should be unnecessary
        salesmanRoute = new LinkedList<Point>(); //should be unnecessary

        if(verticesCount<2){
            return true;
        }
        if(verticesCount==2){
            LineSegment lsRes = new LineSegment(pointsList.get(0), pointsList.get(1));
            result.add(lsRes);
            return true;
        }
    
        createAdjacencyMatrix(pointsList);
        depthSearchFromSpanningTree(0, pointsList);
        Polygon polyRes = travelingSalesmanTourFromDepthSearch();

        result.add(polyRes);
        points.reset();
        return true;
    }

    private void createAdjacencyMatrix(List<Point> pointsList) {
        double adjacency_matrix[][] = new double[verticesCount + 1][verticesCount + 1];

        //Kantengewichte ermitteln
        for (int i = 0; i < verticesCount; i++) {
            for (int j = 0; j < verticesCount; j++) {
                adjacency_matrix[i][j] = pointsList.get(i).getDistance(pointsList.get(j));
                System.out.println("Abstand "+ i + " zu " + j +": " + pointsList.get(i).getDistance(pointsList.get(j)));
                if (i == j) {
                    adjacency_matrix[i][j] = 0;
                    continue;
                }
                if (adjacency_matrix[i][j] == 0) {
                    adjacency_matrix[i][j] = MAX_VALUE;
                }
            }
        }
      
        spanningTreeWithKruskal(adjacency_matrix);
    }

    public void spanningTreeWithKruskal(double adjacencyMatrix[][]) {
        boolean finished = false;
        for (int start = 0; start < verticesCount; start++) {
            for (int end = 0; end < verticesCount; end++) {
                if (adjacencyMatrix[start][end] != MAX_VALUE
                        && start != end) {
                    Edge edge = new Edge();
                    edge.start = start;
                    edge.end = end;
                    edge.weight = adjacencyMatrix[start][end];
                    adjacencyMatrix[end][start] = MAX_VALUE;
                    edges.add(edge);
                }
            }
        }
        Collections.sort(edges, new EdgeComparator());
        CheckCycle checkCycle = new CheckCycle();
        for (Edge edge : edges) {
            spanning_tree[edge.start][edge.end] = edge.weight;
            spanning_tree[edge.end][edge.start] = edge.weight;
            if (checkCycle.checkCycle(spanning_tree, edge.start)) {
                spanning_tree[edge.start][edge.end] = 0;
                spanning_tree[edge.end][edge.start] = 0;
                edge.weight = -1;
                continue;
            }
            visited[edge.start] = 1;
            visited[edge.end] = 1;
            for (int i = 0; i < visited.length; i++) {
                if (visited[i] == 0) {
                    finished = false;
                    break;
                } else {
                    finished = true;
                }
            }
            if (finished)
                break;
        }
    }

    private void depthSearchFromSpanningTree(int start, List<Point> pointsList) {
        depthSearch.add(pointsList.get(start));
        known[start]=true;
      
        for(int i=0; i<verticesCount; i++){
            if(spanning_tree[start][i]!=0 && !known[i]){
                depthSearchFromSpanningTree(i, pointsList);
            }
        }
    }
  
    /**
    * Should be unnecessary as the spanning tree should not contain any duplicates
    * But just in case...
    */
    private Polygon travelingSalesmanTourFromDepthSearch() {
        for(Point p : depthSearch){
            if(!salesmanRoute.contains(p)){
                salesmanRoute.add(p);
            }
        }
      
        return new Polygon(salesmanRoute);
    }
}

class Edge {
    int start;
    int end;
    double weight;
}

class EdgeComparator implements Comparator<Edge> {
    @Override
    public int compare(Edge edge1, Edge edge2) {
        if (edge1.weight < edge2.weight)
            return -1;
        if (edge1.weight > edge2.weight)
            return 1;
        return 0;
    }
}

class CheckCycle {
    private Stack<Integer> stack;
    private double adjacencyMatrix[][];

    public CheckCycle() {
        stack = new Stack<Integer>();
    }

    public boolean checkCycle(double adjacency_matrix[][], int source) {
        boolean cyclepresent = false;
        int number_of_nodes = adjacency_matrix[source].length - 1;

        adjacencyMatrix = new double[number_of_nodes + 1][number_of_nodes + 1];
        for (int start = 1; start <= number_of_nodes; start++) {
            for (int end = 1; end <= number_of_nodes; end++) {
                adjacencyMatrix[start][end] = adjacency_matrix[start][end];
            }
        }

        int visited[] = new int[number_of_nodes + 1];
        int element = source;
        int i = source;
        visited[source] = 1;
        stack.push(source);

        while (!stack.isEmpty()) {
            element = stack.peek();
            i = element;
            while (i <= number_of_nodes) {
                if (adjacencyMatrix[element][i] >= 1 && visited[i] == 1) {
                    if (stack.contains(i)) {
                        cyclepresent = true;
                        return cyclepresent;
                    }
                }
                if (adjacencyMatrix[element][i] >= 1 && visited[i] == 0) {
                    stack.push(i);
                    visited[i] = 1;
                    adjacencyMatrix[element][i] = 0;// mark as labelled;
                    adjacencyMatrix[i][element] = 0;
                    element = i;
                    i = 1;
                    continue;
                }
                i++;
            }
            stack.pop();
        }
        return cyclepresent;
    }

Das Blöde ist nur, dass das Ganze wohl irgendwo einen (Rechen-?)Fehler hat, denn ich bekomme leider keine richtigen Lösungen raus.
Kann mir jemand helfen, den Fehler zu finden? Ich komm einfach nicht drauf und verzweifle langsam an der Suche danach.


Grüße und schon mal Dank im Vorab,

Karrzun


PS: Da das Ganze eine Übung für die Uni ist, wäre es nett, wenn mir jemand nur einen Wink mit dem Zaunpfahl geben könnte, wo der Fehler drin steckt und mir keine korrigierte Version geschickt wird.

*Punkte sind eine eigens definierte Klasse, die sich zwei double-Werte als x- und y-Koordinate (x, y) speichert.

**Polygone sind eine eigens definierte Klasse, die sich mindestens 3 Punkte speichert.

 

[losgehts]

Hallo,

ich habe nur einen kleinen Test mit der Methode "checkCycle" gemacht, sie liefert bei meinem Test nicht immer das richtige Ergebnis.

Grüße, Ulrich

 

[losgehts]

... ich habe noch etwas vergessen zu erwähnen:

Vorweg: du musst wissen, dass ich mich nicht so sonderlich auskenne in der Thematik.

Ohne da jetzt sonderlich nachgelesen zu haben und ohne dass ich weiß, was du genau mit "Tiefensuche" meinst (falls das ein Fachbegriff ist: ich bin kein Informatiker): Der Algorithmus von Kruskal liefert dir ja einen Baum, dessen Knoten (Blätter) deine Städte darstellen, und dessen Äste die Wege zwischen den Städten symbolisieren. Dieser Baum (vom Kruskal-Algo) kann an einem Knoten eine ungerade Anzahl (z.B. drei) an Ästen haben, was für das TSP keine Lösung darstellt. Ich kann aus deinem Code nicht genau erkennen, ob du das bedacht hast. Falls ja, dann vergiss einfach diesen Beitrag hier.

Grüße, Ulrich

 

[Bitfehler]

Hallo,

beim TSP wird ein Rundweg gesucht, d.h. der Startpunkt ist auch der Endpunkt.
Der Kruskal-Algo liefert jedoch einen minimal aufspannenden Baum (MST). Ein MST enthält nach Definition jedoch kein Kreis, wodurch das mit dem Rundweg schwierig wird. (wenn ich das noch richtig im Kopf habe)

Ist Kruskal vorgegeben, da es sich um eine gestellte Aufgabe handelt?

Gruß