X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=tsp%2Ftsp.cpp;h=a5f36205624fb75533b5ab78a6f94938c779c01e;hb=HEAD;hp=97682576cf3db1a5a44016fe23e8f1eb924f4b85;hpb=0945959b4496e6a640637bad5be81d3078724991;p=nms

diff --git a/tsp/tsp.cpp b/tsp/tsp.cpp
index 9768257..a5f3620 100644
--- a/tsp/tsp.cpp
+++ b/tsp/tsp.cpp
@@ -9,6 +9,9 @@
 #define MIN_SWITCH 1
 #define MAX_SWITCH 6
 #define HEAP_MST 0
+#define USE_KOPT 1
+#define KOPT_SLICES 3
+#define KOPT_ITERATIONS 10000
 
 static const unsigned num_cache_elem = (MAX_ROW * MAX_SWITCH * 2) * (MAX_ROW * MAX_SWITCH * 2);
 static unsigned short dist_cache[(MAX_ROW * MAX_SWITCH * 2) * (MAX_ROW * MAX_SWITCH * 2)],
@@ -254,11 +257,13 @@ int prim_mst(std::set<std::pair<unsigned, unsigned> > &set1)
 void print_tour(std::vector<std::pair<unsigned, unsigned> > &points)
 {
 	std::set<std::pair<unsigned, unsigned> > points_left;
+	unsigned total_cost = 0;
 	for (unsigned i = 0; i < points.size(); ++i) {
 		points_left.insert(points[i]);
 	}
 	
 	for (unsigned i = 0; i < points.size(); ++i) {
+		printf("%2u: ", i);
 		if (best_tour[i].side == 0)
 			printf("%2u-%u (left side)  ", best_tour[i].row, best_tour[i].num);
 		else
@@ -267,6 +272,7 @@ void print_tour(std::vector<std::pair<unsigned, unsigned> > &points)
 			printf("           ");
 		} else {
 			printf("cost=%4u  ", best_tour[i].cost);
+			total_cost += best_tour[i].cost;
 		}
 
 		// let's see how good the MST heuristics are
@@ -287,6 +293,141 @@ void print_tour(std::vector<std::pair<unsigned, unsigned> > &points)
 		std::set<std::pair<unsigned, unsigned> >::iterator j = points_left.find(std::make_pair(best_tour[i].row, best_tour[i].num));
 		points_left.erase(j);
 	}
+	printf("Done (total_cost=%u)\n", total_cost);
+}
+
+bool any_opt;
+std::pair<unsigned, unsigned> best_reorganization[KOPT_SLICES];
+
+void optimize_specific_tour(order *tour, std::set<std::pair<unsigned, unsigned> > &fragments,
+	std::vector<std::pair<unsigned, unsigned> > &history, unsigned cost_so_far)
+{
+	if (fragments.size() == 1) {
+		if (cost_so_far < best_so_far) {
+			any_opt = true;
+			memcpy(best_reorganization, &history[0], sizeof(std::pair<unsigned, unsigned>)*history.size());
+			best_so_far = cost_so_far;
+		}
+		return;
+	}
+
+	// match the first point with all the others
+	std::set<std::pair<unsigned, unsigned> >::iterator start = fragments.begin();
+	std::pair<unsigned, unsigned> start_val = *start;
+
+	std::set<std::pair<unsigned, unsigned> >::iterator i = start;
+	++i;
+
+	fragments.erase(start);
+
+	while (i != fragments.end()) {
+		std::pair<unsigned, unsigned> i_val = *i;
+		std::set<std::pair<unsigned, unsigned> >::iterator i_copy = i;
+		++i;
+		
+		unsigned p1 = start_val.second, p2 = i_val.first;
+		history[fragments.size() - 1] = std::make_pair(p1, p2);
+		
+		unsigned this_cost = cache(
+			tour[p1].row, tour[p1].num, tour[p1].side,
+			tour[p2].row, tour[p2].num, tour[p2].side
+		);
+
+		std::set<std::pair<unsigned, unsigned> > frag_copy = fragments;
+		frag_copy.erase(frag_copy.find(i_val));
+		frag_copy.insert(std::make_pair(start_val.first, i_val.second));
+		optimize_specific_tour(tour, frag_copy, history, cost_so_far + this_cost);
+	}
+	
+	fragments.insert(start_val);
+}
+
+void piece_fragment(std::vector<std::pair<unsigned, unsigned> > &points, order *ntour, std::set<std::pair<unsigned, unsigned> > &fragments, unsigned s, unsigned j)
+{
+	// find this fragment, and copy
+	for (std::set<std::pair<unsigned, unsigned> >::iterator i = fragments.begin(); i != fragments.end(); ++i) {
+		if (i->first != s)
+			continue;
+		memcpy(best_tour + j, ntour + s, sizeof(order) * (i->second - i->first + 1));
+		
+		j += (i->second - i->first + 1);
+
+		// find the connection point, if any
+		for (unsigned k = 0; k < KOPT_SLICES; ++k) {
+			if (best_reorganization[k].first == i->second) {
+				piece_fragment(points, ntour, fragments, best_reorganization[k].second, j);
+				best_tour[j].cost = 
+					cache(best_tour[j-1].row, best_tour[j-1].num, best_tour[j-1].side,
+					      best_tour[j].row, best_tour[j].num, best_tour[j].side);
+				return;
+			}
+		}
+	}
+}
+
+void reorganize_tour(std::vector<std::pair<unsigned, unsigned> > &points, std::set<std::pair<unsigned, unsigned> > &fragments)
+{
+	order *ntour = new order[points.size()];
+	memcpy(ntour, best_tour, sizeof(order) * points.size());
+
+	piece_fragment(points, ntour, fragments, 0, 0);
+
+	delete[] ntour;
+}
+
+void optimize_tour(std::vector<std::pair<unsigned, unsigned> > &points)
+{
+	if (points.size() < KOPT_SLICES * 2) {
+		fprintf(stderr, "Warning: Too high KOPT_SLICES set (%u), can't optimize\n", KOPT_SLICES);
+	}
+	
+	order *tour = new order[points.size()];
+	any_opt = false;
+	
+	for (unsigned i = 0; i < KOPT_ITERATIONS; ++i) {
+		int cost = best_so_far;
+		memcpy(tour, best_tour, sizeof(order) * points.size());
+		
+		for (unsigned j = 0; j < KOPT_SLICES; ++j) {
+			// we break the link between RR and RR+1.
+			unsigned rand_remove;
+			do {
+				rand_remove = (unsigned)((points.size() - 2) * (rand() / (RAND_MAX + 1.0)));
+			} while (tour[rand_remove + 1].cost == -1 || (rand_remove != 0 && tour[rand_remove].cost == -1));
+			
+			cost -= tour[rand_remove + 1].cost;
+			tour[rand_remove + 1].cost = -1;
+		}
+
+		/* find the starts and the ends of each point */
+		int last_p = 0;
+		std::set<std::pair<unsigned, unsigned> > fragments;
+		for (unsigned j = 1; j < points.size(); ++j) {
+			if (tour[j].cost != -1)
+				continue;
+			fragments.insert(std::make_pair(last_p, j - 1));
+			last_p = j;
+		}
+		fragments.insert(std::make_pair(last_p, points.size() - 1));
+		
+		/* brute force */
+		std::vector<std::pair<unsigned, unsigned> > history(KOPT_SLICES);
+		optimize_specific_tour(tour, fragments, history, cost);
+
+		if (any_opt) {
+			printf("\nk-opt reduced cost to %u:\n", best_so_far);
+
+			reorganize_tour(points, fragments);
+			print_tour(points);
+			optimize_tour(points);
+
+			return;
+		}
+	}
+
+	delete[] tour;
+
+	printf("\nk-opt made no further improvements.\n");
 }
 
 unsigned do_tsp(std::vector<std::pair<unsigned, unsigned> > &points, std::set<std::pair<unsigned, unsigned> > &points_left, order *ord, order *temp, unsigned ind, unsigned cost_so_far)
@@ -298,6 +439,9 @@ unsigned do_tsp(std::vector<std::pair<unsigned, unsigned> > &points, std::set<st
 		printf("\nNew best tour found! cost=%u\n", cost_so_far);
 		print_tour(points);
 		best_so_far = cost_so_far;
+#if USE_KOPT		
+		optimize_tour(points);
+#endif
 		return 0;
 	}