bitonic tsp

2 files changed, 16 insertions, 0 deletions

diff --git a/graph/bitonicTSP.cpp b/graph/bitonicTSP.cpp
new file mode 100644
index 0000000..4e4dda0
--- /dev/null
+++ b/graph/bitonicTSP.cpp
@@ -0,0 +1,13 @@
+vector< vector<double> > dp; //initialize with -1
+vector< vector<double> > dist; //initialize with all dists between points
+vector<int> 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
+	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
+	return min(tryLR, tryRL);
+}
\ No newline at end of file
diff --git a/graph/graph.tex b/graph/graph.tex
index 98d5ffd..a80f502 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -69,3 +69,6 @@ Finde die maximale Anzahl Pfade von $s$ nach $t$, die keinen Knoten teilen.
 \subsection{Maximal Cardinatlity Bipartite Mathcing}
 \lstinputlisting{graph/maxCarBiMatch.cpp}
 
+\subsection{Bitonic TSP}
+\lstinputlisting{graph/bitonicTSP.cpp}
+