From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Mon, 27 Jun 2022 17:19:28 +0200
Subject: updated tcr

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

(limited to 'graph/bitonicTSPsimple.cpp')

diff --git a/graph/bitonicTSPsimple.cpp b/graph/bitonicTSPsimple.cpp
new file mode 100644
index 0000000..ff605d9
--- /dev/null
+++ b/graph/bitonicTSPsimple.cpp
@@ -0,0 +1,28 @@
+vector<vector<double>> dist; // Entfernungen zwischen Punkten.
+vector<vector<double>> dp;
+
+double get(int p1, int p2) {
+	int v = max(p1, p2) + 1;
+	if (v == sz(dist)) 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);
+	double tryRL = dist[p2][v] + get(p1, v);
+	return dp[p1][p2] = min(tryLR, tryRL);
+}
+
+void bitonicTour() {
+	dp = vector<vector<double>>(sz(dist), 
+							vector<double>(sz(dist), -1));
+	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) < sz(dist);) {
+		if (dp[p1][p2] == dist[p1][v] + dp[v][p2]) {
+			lr.push_back(v); p1 = v;
+		} else {
+			rl.push_back(v); p2 = v;
+	}}
+	lr.insert(lr.end(), rl.rbegin(), rl.rend());
+	// Enthält Knoten 0 zweimal. An erster und letzter Position.
+	// return lr;
+}
\ No newline at end of file
-- 
cgit v1.2.3