implemented new bitonic tsp algorithm

this algorithm technically can be used to to solve bitonic tsp with linear space (by calculating dist[i][j] on the fly)
it should be easier to use, a little bit quicker and is able reconstruct the used tour(maybe there is an easier way to reconstruct it?)

1 files changed, 33 insertions, 14 deletions

diff --git a/graph/bitonicTSP.cpp b/graph/bitonicTSP.cpp
index bf01f9e..478362d 100644
--- a/graph/bitonicTSP.cpp
+++ b/graph/bitonicTSP.cpp
@@ -1,16 +1,35 @@
-// Laufzeit: O(|V|^2)
-vector< vector<double> > dp; // Initialisiere mit -1
-vector< vector<double> > dist; // Initialisiere mit Entfernungen zwischen Punkten.
-vector<int> lr, rl; // Links-nach-rechts und rechts-nach-links Pfade.
-int n; // #Knoten
+// Laufzeit: O(n^2)
+vector<vector<double>> dist; // Initialisiere mit Entfernungen zwischen Punkten.
 
-// get(0, 0) gibt die Länge der kürzesten bitonischen Route.
-double get(int p1, int p2) {
-	int v = max(p1, p2) + 1;
-	if (v == n - 1) return dist[p1][v] + dist[v][p2];
-	if (dp[p1][p2] > -0.5) return dp[p1][p2];
-	double tryLR = dist[p1][v] + get(v, p2), tryRl = dist[v][p2] + get(p1, v);
-	if (tryLR < tryRL) lr.push_back(v); // Baut die Pfade auf. Fügt v zu rl hinzu, falls beide gleich teuer.
-	else rl.push_back(v); // Änder das, falls nötig.
-	return min(tryLR, tryRL);
+void bitonicTSP() {
+    vector<double> dp(dist.size(), HUGE_VAL);
+    vector<int> pre(dist.size()); // nur für Tour
+    dp[0] = 0, dp[1] = 2 * dist[0][1], pre[1] = 0;
+    for (unsigned int i = 2; i < dist.size(); i++) {
+        double link = 0;
+        for (int j = i - 2; j >= 0; j--) {
+            link += dist[j + 1][j + 2];
+            double opt = link + dist[j][i] + dp[j + 1] - dist[j][j + 1];
+            if (opt < dp[i]) {
+                dp[i] = opt;
+                pre[i] = j;
+    }}}
+    // return dp[dist.size() - 1]; // Länger der Tour
+
+    int n = dist.size() - 1;
+    vector<int> lt, ut;
+    lt.push_back(n), lt.push_back(n - 1);
+    int j;
+    do {
+        j = pre[n];
+        (lt.back() == n ? lt : ut).push_back(j);
+        for (int i = n - 1; i > j + 1; i--) {
+            (lt.back() == i ? lt : ut).push_back(i - 1);
+        }
+        n = j + 1;
+    } while(j != 0);
+    lt.push_back(0);
+    reverse(lt.begin(), lt.end());
+    lt.insert(lt.end(), ut.begin(), ut.end());
+    //return lt;// Enthält Knoten 0 zweimal. An erster und letzter Position.
 }