Initial checkin for move to Git (no prior version history available).

diff --git a/nodes.txt b/nodes.txt
new file mode 100644 (file)
index 0000000..275dcac
--- /dev/null
+++ b/nodes.txt
@@ -0,0 +1,21 @@
+fg fk 38
+uka lim 19
+lim radion 27
+uka sit 8
+uka ku 9
+sit ku 3
+sit klst 39
+ku klst 38
+klst soci 30
+klst stv 8
+stv laafte 17
+stv ud 8
+laafte ud 15
+ud regi 3
+laafte dg 19
+dg strindens 4
+klst styret 54
+styret ark 15
+ark sangern 13
+sangern fg 13
+uka radion 10

diff --git a/tsp b/tsp
new file mode 100755 (executable)
index 0000000..0b22c8b
Binary files /dev/null and b/tsp differ

diff --git a/tsp.cpp b/tsp.cpp
new file mode 100644 (file)
index 0000000..2c64c59
--- /dev/null
+++ b/tsp.cpp
@@ -0,0 +1,195 @@
+#include <assert.h>
+#include <stdio.h>
+#include <string.h>
+
+#include <vector>
+#include <string>
+#include <map>
+#include <set>
+#include <algorithm>
+
+using namespace std;
+
+#define INFINITY 10000
+
+vector<string> places; 
+set<string> places_set;
+map<pair<string, string>, int> sparse_dist;
+
+int* dist;
+
+void check_name_inserted(char* name)
+{
+       if (places_set.count(name) == 0) {
+               places_set.insert(name);
+               places.push_back(name);
+       }
+}
+
+void make_matrix()
+{
+       int num_places = places.size();
+       dist = new int[num_places * num_places];
+       
+       for (int i = 0; i < num_places; ++i) {
+               dist[i * num_places + i] = 0;
+       }
+
+       for (int i = 0; i < num_places; ++i) {
+               for (int j = i + 1; j < num_places; ++j) {
+                       int d = INFINITY;
+
+                       pair<string, string> comb = make_pair(places[i], places[j]);
+                       if (sparse_dist.count(comb) != 0) {
+                               d = sparse_dist[comb];
+                       }
+                       comb = make_pair(places[j], places[i]);
+                       if (sparse_dist.count(comb) != 0) {
+                               d = sparse_dist[comb];
+                       }
+                       dist[i * num_places + j] = d;
+                       dist[j * num_places + i] = d;
+               }
+       }
+}
+
+void print_matrix()
+{
+       int num_places = places.size();
+       for (int i = 0; i < num_places; ++i) {
+               printf("%d: %s\n", i, places[i].c_str());
+       }
+       for (int i = 0; i < num_places; ++i) {
+               for (int j = 0; j < num_places; ++j) {
+                       printf("%5d ", dist[i * num_places + j]);
+               }
+               printf("\n");
+       }
+}
+
+void floyd_warshall()
+{
+       int num_places = places.size();
+       
+       for (int k = 0; k < num_places; ++k) {
+               for (int i = 0; i < num_places; ++i) {
+                       for (int j = 0; j < num_places; ++j) {
+                               dist[i * num_places + j] =
+                                       min(dist[i * num_places + j],
+                                           dist[i * num_places + k] + dist[k * num_places + j]);
+                       }
+               }
+       }
+}
+
+int *cache;
+int cache_size;
+int best_cost;
+int finish_mask;
+
+void init_tsp()
+{
+       int num_places = places.size();
+       cache_size = (1 << num_places);
+       cache = new int[cache_size * num_places];
+
+       for (int i = 0; i < cache_size * num_places; ++i) {
+               cache[i] = -1;
+       }
+
+       best_cost = INFINITY;
+       finish_mask = (1 << num_places) - 1;
+}
+
+int tsp(int node_num, int visited_mask, int cost_so_far)
+{
+       int num_places = places.size();
+       if (cache[node_num * cache_size + visited_mask] != -1) {
+               return cache[node_num * cache_size + visited_mask];
+       }
+       if (cost_so_far > best_cost) {
+               return INFINITY;
+       }
+
+       if (visited_mask == finish_mask) {
+               return 0;
+/*
+               cost_so_far += dist[node_num * num_places + 0];
+               cache[node_num * cache_size + visited_mask] = dist[node_num * num_places + 0];
+               if (cost_so_far < best_cost) {
+                       best_cost = cost_so_far;
+               }
+               return dist[node_num * num_places + 0]; */
+       }
+
+       int best_this_cost = INFINITY;
+       for (int i = 0; i < num_places; ++i) {
+               if (visited_mask & (1 << i)) {
+                       continue;
+               }
+
+               int cost = dist[node_num * num_places + i]
+                   + tsp(i, visited_mask | (1 << i), cost_so_far + dist[node_num * num_places + i]);
+               if (cost < best_this_cost) {
+                       best_this_cost = cost;
+               }
+       }
+               
+       cache[node_num * cache_size + visited_mask] = best_this_cost;
+       return best_this_cost;
+}
+
+void backtrack(int node_num, int visited_mask)
+{
+       int num_places = places.size();
+       if (visited_mask == finish_mask) {
+               return;
+       }
+
+       int best_node = 0;
+       int best_this_cost = INFINITY;
+       for (int i = 0; i < num_places; ++i) {
+               if (visited_mask & (1 << i)) {
+                       continue;
+               }
+
+               int cost = dist[node_num * num_places + i] +
+                   cache[i * cache_size + (visited_mask | (1 << i))];
+               assert(cost != -1);
+               if (cost < best_this_cost) {
+                       best_node = i;
+                       best_this_cost = cost;
+               }
+       }
+
+       printf("%s [%d] [%d to %d costs %d]\n", places[best_node].c_str(), best_this_cost, node_num, best_node, dist[node_num * num_places + best_node]);
+       backtrack(best_node, visited_mask | (1 << best_node));
+}
+
+int main(void)
+{
+       for ( ;; ) {
+               char name1[256];
+               char name2[256];
+               int dist;
+
+               if (scanf("%s %s %d", name1, name2, &dist) != 3) {
+                       break;
+               }
+
+               check_name_inserted(name1);
+               check_name_inserted(name2);
+               sparse_dist.insert(make_pair(make_pair(name1, name2), dist));
+       }
+
+       make_matrix();
+       print_matrix();
+       printf("\n");
+       floyd_warshall();
+       print_matrix();
+
+       init_tsp();
+       tsp(0, 1, 0);
+       printf("fg [%d]\n", best_cost);
+       backtrack(0, 1);
+}