From dc1014bf6441d8bd61d4257fc481394736491da7 Mon Sep 17 00:00:00 2001
From: mzuenni <mzuenni@users.noreply.github.com>
Date: Sun, 30 Jul 2017 18:04:38 +0200
Subject: simplified code

---
 graph/bitonicTSP.cpp | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)

(limited to 'graph')

diff --git a/graph/bitonicTSP.cpp b/graph/bitonicTSP.cpp
index f607f2c..9e4fac1 100644
--- a/graph/bitonicTSP.cpp
+++ b/graph/bitonicTSP.cpp
@@ -1,25 +1,22 @@
 // Laufzeit: O(n^2)
 vector<vector<double>> dist; // Initialisiere mit Entfernungen zwischen Punkten.
 vector<vector<double>> dp;
-vector<vector<bool>> choice;
 
 double get(int p1, int p2) {
     int v = max(p1, p2) + 1;
     if (v == dist.size()) 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), tryRL = dist[p2][v] + get(p1, v);
-	choice[p1][p2] = tryLR < tryRL;
 	return dp[p1][p2] = min(tryLR, tryRL);
 }
 
 void bitonicTour() {
     dp = vector<vector<double>>(dist.size(), vector<double>(dist.size(), -1));
-    choice = vector<vector<bool>>(dist.size(), vector<bool>(dist.size()));
     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) < dist.size();) {
-        if (choice[p1][p2]) {
+        if (dp[p1][p2] == dist[p1][v] + dp[v][p2]) {
             lr.push_back(v); p1 = v;
         } else {
             rl.push_back(v); p2 = v;
-- 
cgit v1.2.3