From 3e4cca763aad161d84e524502605239487ccbf8e Mon Sep 17 00:00:00 2001
From: pjungeblut <paul.jungeblut@gmail.com>
Date: Tue, 25 Nov 2014 22:18:16 +0100
Subject: bitonic tsp

---
 graph/bitonicTSP.cpp | 13 +++++++++++++
 graph/graph.tex      |  3 +++
 2 files changed, 16 insertions(+)
 create mode 100644 graph/bitonicTSP.cpp

(limited to 'graph')

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}
+
-- 
cgit v1.2.3


From 2cc01237f578c21941aa70b908a2662d443f8c1a Mon Sep 17 00:00:00 2001
From: JBatzill <batzilljohannes@gmail.com>
Date: Wed, 26 Nov 2014 00:22:51 +0100
Subject: Create TSP.cpp

---
 graph/TSP.cpp | 28 ++++++++++++++++++++++++++++
 1 file changed, 28 insertions(+)
 create mode 100644 graph/TSP.cpp

(limited to 'graph')

diff --git a/graph/TSP.cpp b/graph/TSP.cpp
new file mode 100644
index 0000000..c38cbb2
--- /dev/null
+++ b/graph/TSP.cpp
@@ -0,0 +1,28 @@
+//nodes[0] has to be the start and end node.
+vector<vector<int>> dist;
+vector<int> TSP() {
+	int n = dist.size(), m = 1 << n;
+	vector<vector<ii>> dp(n, vector<ii>(m, ii(MAX_N, -1)));
+	
+	for(int c = 0; c < n; c++) dp[c][m-1].first = dist[c][0], dp[c][m-1].second = 0;
+
+	for(int v = m - 2; v >= 0; v--) {
+		for(int c = n - 1; c >= 0; c--) {
+			for(int g = 0; g < n; g++) { 
+				if(g != c && (((1 << g) & v) == 0)) {
+					if((dp[g][(v | (1 << g))].first + dist[c][g]) < dp[c][v].first) {
+						dp[c][v].first = dp[g][(v | (1 << g))].first + dist[c][g];
+						dp[c][v].second = g;
+					}
+				}
+			}
+		}
+	}
+	
+	vector<int> res; res.push_back(0); int v = 0;
+	while(res.back() != 0 || res.size() == 1) {
+		res.push_back(dp[res.back()][(v |= (1 << res.back()))].second);
+	}
+	
+	return res;
+}
-- 
cgit v1.2.3


From 24507ee02a8fe20fb22ae30642e3b15e411e82eb Mon Sep 17 00:00:00 2001
From: JBatzill <batzilljohannes@gmail.com>
Date: Wed, 26 Nov 2014 00:23:27 +0100
Subject: Update graph.tex

---
 graph/graph.tex | 3 +++
 1 file changed, 3 insertions(+)

(limited to 'graph')

diff --git a/graph/graph.tex b/graph/graph.tex
index a80f502..6c4b1e8 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -69,6 +69,9 @@ Finde die maximale Anzahl Pfade von $s$ nach $t$, die keinen Knoten teilen.
 \subsection{Maximal Cardinatlity Bipartite Mathcing}
 \lstinputlisting{graph/maxCarBiMatch.cpp}
 
+\subsection{TSP}
+\lstinputlisting{graph/TSP.cpp}
+
 \subsection{Bitonic TSP}
 \lstinputlisting{graph/bitonicTSP.cpp}
 
-- 
cgit v1.2.3