diff options
| -rw-r--r-- | graph/bitonicTSP.cpp | 47 |
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. } |