diff options
| -rw-r--r-- | graph/bitonicTSP.cpp | 54 |
1 files changed, 24 insertions, 30 deletions
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. } |