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 +++++++++++++ 1 file changed, 13 insertions(+) create mode 100644 graph/bitonicTSP.cpp (limited to '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 -- cgit v1.2.3