From 3e4cca763aad161d84e524502605239487ccbf8e Mon Sep 17 00:00:00 2001 From: pjungeblut Date: Tue, 25 Nov 2014 22:18:16 +0100 Subject: bitonic tsp --- graph/bitonicTSP.cpp | 13 +++++++++++++ graph/graph.tex | 3 +++ tcr.pdf | Bin 203167 -> 204181 bytes 3 files changed, 16 insertions(+) create mode 100644 graph/bitonicTSP.cpp 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 > 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 + 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} + diff --git a/tcr.pdf b/tcr.pdf index 628d51c..0778bd6 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3