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:
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.
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:
Java:
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.
Zuletzt bearbeitet von einem Moderator: