printf("%2u-%u (right side) ", points[best_tour[i].pt].first,
points[best_tour[i].pt].second);
if (i == 0) {
- printf("\n");
+ printf(" ");
} else {
unsigned cost = distance(
points[best_tour[i-1].pt].first,
points[best_tour[i].pt].first,
points[best_tour[i].pt].second,
best_tour[i].side);
- printf("cost=%4u\n", cost);
+ printf("cost=%4u ", cost);
}
+
+ // let's see how good the MST heuristics are
+ if (i != points.size() - 1) {
+ std::set<std::pair<unsigned, unsigned> > mst_tree;
+
+ mst_tree.insert(points[best_tour[i].pt]);
+
+ for (unsigned j = 0; j < points.size(); ++j) {
+ for (unsigned k = 0; k < i; ++k)
+ if (best_tour[k].pt == j)
+ goto taken;
+
+ mst_tree.insert(points[j]);
+
+taken:
+ 1;
+ }
+
+ printf("mst_bound=%5u, ", prim_mst(mst_tree));
+
+ unsigned rest_cost = 0;
+ for (unsigned j = i + 1; j < points.size(); ++j) {
+ rest_cost += distance(
+ points[best_tour[j-1].pt].first,
+ points[best_tour[j-1].pt].second,
+ best_tour[j-1].side,
+ points[best_tour[j].pt].first,
+ points[best_tour[j].pt].second,
+ best_tour[j].side);
+ }
+
+ printf("rest_cost=%5u", rest_cost);
+ }
+ printf("\n");
}
}