Hallo zusammen,
ich habe lange überlegt, ob dies der richtige Weg ist, um zu einer Lösung meines Problems zu kommen, da ich nicht einschätzen kann, ob das Nicht-Auffinden einer Lösung an meinen geringen Programmierkenntnissen liegt oder aber ein größeres Problem darstellt.
Nun zur Aufgabe: Ich schreibe in meiner Masterthesis über das Thema Traveling Salesman Problem. Genauer gesagt muss ich einen von mir gewählten Algorithmus in Java implementieren, diesen analysieren und im Anschluss Modifikationen vornehmen, um entweder Laufzeit oder Lösungsgüte zu verbessern. Da der Farthest Insertion Algorithmus eine sehr gute Heuristik zur Lösung des TSP ist, habe ich mich dazu entschieden, diesen zu implementieren. Was ich soweit auch geschafft habe. Das Problem ist nun, dass dieser Algorithmus laut Literatur eine Laufzeit von O(n²) hat. Die von mir implementierte Version dieses Algorithmus läuft allerdings in O(n³). Ich versuche seit einigen Wochen eine Lösung zu finden, da ich die Implementierung nicht als Grundlage für meine Analyse verwenden kann, wenn er ja eigentlich "schneller" läuft.
Nun noch kurz der Art, wie ich den Farthest Insertion implementiert habe:
1. Zwei Knoten des Graphen, die maximal zueinander entfernt sind, werden markiert (Laufzeit O(n²)).
2. Solange die Tour nicht vollständig ist, tue Folgendes:
2a. Der nächste einzufügende Knoten wird ausgewählt, indem die Abstände der verbleibenden Knoten zu den bereits markierten Knoten überprüft werden. Davon wird der minimale Abstand jedes verbleibenden Knoten zu den markierten zwischengespeichert und dann wiederum der Knoten gewählt, der von den Minima der Kantengewichte den maximalen Wert hat (Laufzeit O(n³)).
2b. Der ausgwählte Knoten wird an der günstigsten Stelle in die Subtour eingefügt (Laufzeit O(n²)).
Hier die Methode, die den Punkt 2 umfasst:
Ich würde mich sehr freuen, wenn jemand eine Idee hätte, wie ich aus dieser kubischen Laufzeit eine quadratische machen könnte. Ich habe schon versucht eine zweidimensionale Array-List zu erstellen, die die bereits überprüften Kanten zwischenspeichert. Da sie allerdings dynamisch sind (also sich ständig ändern) und Methoden wie remove() (O(n)) und sort() (O(nlogn)) ebenfalls Laufzeit verursachen, wodurch ich am Ende eine Laufzeit von O(n³logn) hatte, hab ich diesen Ansatz wieder verworfen.
Vielen Dank im Voraus fürs Grübeln!
Liebe Grüße
amb42
PS.: Hoher Speicherbedarf soll egal sein. Wichtig ist die Laufzeit.
ich habe lange überlegt, ob dies der richtige Weg ist, um zu einer Lösung meines Problems zu kommen, da ich nicht einschätzen kann, ob das Nicht-Auffinden einer Lösung an meinen geringen Programmierkenntnissen liegt oder aber ein größeres Problem darstellt.
Nun zur Aufgabe: Ich schreibe in meiner Masterthesis über das Thema Traveling Salesman Problem. Genauer gesagt muss ich einen von mir gewählten Algorithmus in Java implementieren, diesen analysieren und im Anschluss Modifikationen vornehmen, um entweder Laufzeit oder Lösungsgüte zu verbessern. Da der Farthest Insertion Algorithmus eine sehr gute Heuristik zur Lösung des TSP ist, habe ich mich dazu entschieden, diesen zu implementieren. Was ich soweit auch geschafft habe. Das Problem ist nun, dass dieser Algorithmus laut Literatur eine Laufzeit von O(n²) hat. Die von mir implementierte Version dieses Algorithmus läuft allerdings in O(n³). Ich versuche seit einigen Wochen eine Lösung zu finden, da ich die Implementierung nicht als Grundlage für meine Analyse verwenden kann, wenn er ja eigentlich "schneller" läuft.
Nun noch kurz der Art, wie ich den Farthest Insertion implementiert habe:
1. Zwei Knoten des Graphen, die maximal zueinander entfernt sind, werden markiert (Laufzeit O(n²)).
2. Solange die Tour nicht vollständig ist, tue Folgendes:
2a. Der nächste einzufügende Knoten wird ausgewählt, indem die Abstände der verbleibenden Knoten zu den bereits markierten Knoten überprüft werden. Davon wird der minimale Abstand jedes verbleibenden Knoten zu den markierten zwischengespeichert und dann wiederum der Knoten gewählt, der von den Minima der Kantengewichte den maximalen Wert hat (Laufzeit O(n³)).
2b. Der ausgwählte Knoten wird an der günstigsten Stelle in die Subtour eingefügt (Laufzeit O(n²)).
Hier die Methode, die den Punkt 2 umfasst:
Java:
/** Returns a hamiltonian path in an array list.*/
public ArrayList<Integer> getPath(UndirectedGraphAsAdjacencyMatrix g,
int [] insertedVertices, int [] leftVertices){
double[][]adj = g.getAdjacencyMatrix();
int wMin = Integer.MAX_VALUE;
int wIns = Integer.MAX_VALUE;
int index = 0;
int vertex = -1;
Set<Integer> inserted = new HashSet<Integer>();
Set<Integer> left = new HashSet<Integer>();
for(int i = 0; i<insertedVertices.length; i++){
inserted.add(insertedVertices[i]);
path.add(insertedVertices[i]);
}
for(int i = 0; i<leftVertices.length; i++)
left.add(leftVertices[i]);
while(path.size()<(insertedVertices.length+leftVertices.length)){
double minDist = Double.POSITIVE_INFINITY;
double maxDist = Double.NEGATIVE_INFINITY;
double minDistTour = Double.POSITIVE_INFINITY;
Integer [] ins = inserted.toArray(new Integer[inserted.size()]);
Integer[] le = left.toArray(new Integer[left.size()]);
if(le.length>1){
//Die beiden folgenden verschachtelten for-Schleifen innerhalb der while-Schleife
//führen zur kubischen Laufzeit, da jedes Mal alle Kanten überprüft werden.
for(int w = 0; w<le.length; w++){
for(int v = 0; v<ins.length; v++){
//Comparison of the edge weights
//between inserted and left Vertices
//and buffering of the minimal distance.
if(minDist>adj[ins[v]][le[w]]) {
minDist = adj[ins[v]][le[w]];
wMin = le[w];
}
}
//Selecting the left vertex
//of the buffered minimal distances
//which has the highest value.
if(maxDist<minDist){
maxDist = minDist;
wIns = wMin;
}
minDist = Double.POSITIVE_INFINITY;
}
}
else wIns = le[0];
for(int i=0; i<ins.length-1;i++){
//Insertion of the vertex based on
//min(c_(i)(wIns) + c_(wIns)(i+1) - c_(i)(i+1)).
if(minDistTour >
(adj[path.get(i).intValue()][wIns]
+adj[wIns][path.get(i+1).intValue()]
-adj[path.get(i).intValue()][path.get(i+1).intValue()])){
minDistTour =
adj[path.get(i).intValue()][wIns]
+adj[wIns][path.get(i+1).intValue()]
-adj[path.get(i).intValue()][path.get(i+1).intValue()];
index = i+1;
vertex = wIns;
}
//Insertion of the vertex based on
//min(c_(0)(wIns) + c_(wIns)(ins.length-1) - c_(0)(ins.length-1))
//to proof if return to first vertex is better
//than the other insertion positions.
if(minDistTour >
(adj[path.get(0).intValue()][wIns]
+adj[wIns][path.get(ins.length-1).intValue()]
-adj[path.get(0).intValue()][path.get(ins.length-1).intValue()])){
minDistTour =
adj[path.get(0).intValue()][wIns]
+adj[wIns][path.get(ins.length-1).intValue()]
-adj[path.get(0).intValue()][path.get(ins.length-1).intValue()];
index = ins.length;
vertex = wIns;
}
}
inserted.add(vertex);
left.remove(vertex);
minDistTour = Double.POSITIVE_INFINITY;
path.add(index, vertex);
}
return path;
}Ich würde mich sehr freuen, wenn jemand eine Idee hätte, wie ich aus dieser kubischen Laufzeit eine quadratische machen könnte. Ich habe schon versucht eine zweidimensionale Array-List zu erstellen, die die bereits überprüften Kanten zwischenspeichert. Da sie allerdings dynamisch sind (also sich ständig ändern) und Methoden wie remove() (O(n)) und sort() (O(nlogn)) ebenfalls Laufzeit verursachen, wodurch ich am Ende eine Laufzeit von O(n³logn) hatte, hab ich diesen Ansatz wieder verworfen.
Vielen Dank im Voraus fürs Grübeln!
Liebe Grüße
amb42
PS.: Hoher Speicherbedarf soll egal sein. Wichtig ist die Laufzeit.
