From 6679f0299d4d1a36b4fcda2de8c9c7065c7c9ba5 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Wed, 29 Jun 2016 17:52:45 +0200 Subject: Fixed TSP implementation. --- graph/TSP.cpp | 18 ++++++------------ 1 file changed, 6 insertions(+), 12 deletions(-) diff --git a/graph/TSP.cpp b/graph/TSP.cpp index 0161d3c..7fba361 100644 --- a/graph/TSP.cpp +++ b/graph/TSP.cpp @@ -1,29 +1,23 @@ -// Laufzeit: O(n*2^n) -// nodes[0] ist Start- und Endknoten. -vector> dist; +// Laufzeit: O(n^2*2^n) +vector> dist; // Entfernung zwischen je zwei Punkten. vector TSP() { int n = dist.size(), m = 1 << n; - vector> dp(n, vector(m, ii(MAX_N, -1))); + vector> dp(n, vector(m, ii(INF, -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(g != c && !((1 << g) & v)) { 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 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; + return res; // Enthält Knoten 0 zweimal. An erster und letzter Position. } -- cgit v1.2.3