From: Steinar H. Gunderson <sgunderson@bigfoot.com>
Date: Tue, 22 Jan 2013 16:18:14 +0000 (+0100)
Subject: Initial checkin for move to Git (no prior version history available).
X-Git-Url: https://git.sesse.net/?p=tsp;a=commitdiff_plain;h=e521e49ed4a55c73bf0b069e7cdef2d3ed162885

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

e521e49ed4a55c73bf0b069e7cdef2d3ed162885
diff --git a/nodes.txt b/nodes.txt
new file mode 100644
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
index 0000000..0b22c8b
Binary files /dev/null and b/tsp differ
diff --git a/tsp.cpp b/tsp.cpp
new file mode 100644
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);
+}