+ 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");