#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)],
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
printf(" ");
} else {
printf("cost=%4u ", best_tour[i].cost);
+ total_cost += best_tour[i].cost;
}
// let's see how good the MST heuristics are
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)
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;
}
projects / nms / blobdiff