From c7c2ee8604b84227be8f1b727930cf544efe2fcc Mon Sep 17 00:00:00 2001
From: mzuenni <mzuenni@users.noreply.github.com>
Date: Sat, 29 Jul 2017 11:44:53 +0200
Subject: reimplemented old dp solution and added path reconstruction

---
 graph/bitonicTSP.cpp | 54 +++++++++++++++++++++++-----------------------------
 1 file changed, 24 insertions(+), 30 deletions(-)

(limited to 'graph')

diff --git a/graph/bitonicTSP.cpp b/graph/bitonicTSP.cpp
index babddbd..f607f2c 100644
--- a/graph/bitonicTSP.cpp
+++ b/graph/bitonicTSP.cpp
@@ -1,35 +1,29 @@
 // Laufzeit: O(n^2)
 vector<vector<double>> dist; // Initialisiere mit Entfernungen zwischen Punkten.
+vector<vector<double>> dp;
+vector<vector<bool>> choice;
 
-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
+double get(int p1, int p2) {
+    int v = max(p1, p2) + 1;
+    if (v == dist.size()) return dist[p1][v - 1] + dist[p2][v - 1];
+    if (dp[p1][p2] >= 0.0) return dp[p1][p2];
+    double tryLR = dist[p1][v] + get(v, p2), tryRL = dist[p2][v] + get(p1, v);
+	choice[p1][p2] = tryLR < tryRL;
+	return dp[p1][p2] = min(tryLR, tryRL);
+}
 
-    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.back() == 1 ? lt : ut).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.
+void bitonicTour() {
+    dp = vector<vector<double>>(dist.size(), vector<double>(dist.size(), -1));
+    choice = vector<vector<bool>>(dist.size(), vector<bool>(dist.size()));
+    get(0, 0);
+    // return dp[0][0]; // Länger der Tour
+    vector<int> lr = {0}, rl = {0};
+    for (int p1 = 0, p2 = 0, v; (v = max(p1, p2) + 1) < dist.size();) {
+        if (choice[p1][p2]) {
+            lr.push_back(v); p1 = v;
+        } else {
+            rl.push_back(v); p2 = v;
+	}}
+    lr.insert(lr.end(), rl.rbegin(), rl.rend());
+    // return lr; // Enthält Knoten 0 zweimal. An erster und letzter Position.
 }
-- 
cgit v1.2.3