From 53e7f12d828bb94c05d2b6c4e04d61de9482c426 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Thu, 3 Dec 2015 01:12:26 +0100 Subject: Improving graoh chapter. --- graph/bitonicTSP.cpp | 19 +++++++++++-------- 1 file changed, 11 insertions(+), 8 deletions(-) (limited to 'graph/bitonicTSP.cpp') diff --git a/graph/bitonicTSP.cpp b/graph/bitonicTSP.cpp index 4e4dda0..bf01f9e 100644 --- a/graph/bitonicTSP.cpp +++ b/graph/bitonicTSP.cpp @@ -1,13 +1,16 @@ -vector< vector > dp; //initialize with -1 -vector< vector > dist; //initialize with all dists between points -vector lr, rl; //left-to-right and right-to-left paths -int n; //number of points -double get(int p1, int p2) { //call get(0, 0) to get length of shortest bitonic route +// Laufzeit: O(|V|^2) +vector< vector > dp; // Initialisiere mit -1 +vector< vector > dist; // Initialisiere mit Entfernungen zwischen Punkten. +vector lr, rl; // Links-nach-rechts und rechts-nach-links Pfade. +int n; // #Knoten + +// 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); //reconstructs the path, pushes v to rl if the choice does not matter - else rl.push_back(v); //change this if needed + 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); -} \ No newline at end of file +} -- cgit v1.2.3