From 873cc9485d540a6fd26ee8e752df24afabfd58f5 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sun, 22 Oct 2017 22:58:21 +0200 Subject: Fixing linebreaks in bitonic TSP. --- graph/bitonicTSP.cpp | 34 ++++++++++++++++------------------ 1 file changed, 16 insertions(+), 18 deletions(-) (limited to 'graph') diff --git a/graph/bitonicTSP.cpp b/graph/bitonicTSP.cpp index 9e4fac1..2a8b5f9 100644 --- a/graph/bitonicTSP.cpp +++ b/graph/bitonicTSP.cpp @@ -1,26 +1,24 @@ // Laufzeit: O(n^2) -vector> dist; // Initialisiere mit Entfernungen zwischen Punkten. -vector> dp; +vector> dp, dist; // Entfernungen zwischen Punkten. 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); - return dp[p1][p2] = min(tryLR, tryRL); + 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); + double tryRL = dist[p2][v] + get(p1, v); + return dp[p1][p2] = min(tryLR, tryRL); } void bitonicTour() { - dp = vector>(dist.size(), vector(dist.size(), -1)); - get(0, 0); - // return dp[0][0]; // Länger der Tour - vector lr = {0}, rl = {0}; - for (int p1 = 0, p2 = 0, v; (v = max(p1, p2) + 1) < dist.size();) { - if (dp[p1][p2] == dist[p1][v] + dp[v][p2]) { - lr.push_back(v); p1 = v; - } else { - rl.push_back(v); p2 = v; + dp.assign(dist.size(), vector(dist.size(), -1)); + get(0, 0); // return dp[0][0]; // Länger der Tour + vector lr = {0}, rl = {0}; + for (int p1 = 0, p2 = 0, v; (v = max(p1, p2) + 1) < dist.size();) { + if (dp[p1][p2] == dist[p1][v] + dp[v][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. + lr.insert(lr.end(), rl.rbegin(), rl.rend()); // Tour, Knoten 0 doppelt. } -- cgit v1.2.3