Merge pull request #28 from mzuenni/master

implemented new bitonic tsp algorithm

2 files changed, 28 insertions, 16 deletions

diff --git a/graph/bitonicTSP.cpp b/graph/bitonicTSP.cpp
index bf01f9e..f607f2c 100644
--- a/graph/bitonicTSP.cpp
+++ b/graph/bitonicTSP.cpp
@@ -1,16 +1,29 @@
-// 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.
+vector<vector<double>> dp;
+vector<vector<bool>> choice;
 
-// 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);
+    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);
+}
+
+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.
 }
diff --git a/graph/graph.tex b/graph/graph.tex
index 937b976..596c0d6 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -37,7 +37,6 @@ Erkennt negative Zyklen.
 \subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)}
 \lstinputlisting{graph/scc.cpp}
 
-% TODO (pjungeblut): This has errors for bridges!
 \subsection{Artikulationspunkte und Brücken}
 \lstinputlisting{graph/articulationPoints.cpp}
 
@@ -110,6 +109,6 @@ Nochmal ca. Faktor 2 schneller als Ford Fulkerson mit Capacity Scaling.
 % \subsection{TSP}
 % \lstinputlisting{graph/TSP.cpp}
 
-% \subsection{Bitonic TSP}
-% \lstinputlisting{graph/bitonicTSP.cpp}
+\subsection{Bitonic TSP}
+\lstinputlisting{graph/bitonicTSP.cpp}