#include <algorithm>
struct order {
- unsigned pt;
+ unsigned row, num;
int side;
-};
-struct try_order {
- order o;
int cost;
- bool operator< (const try_order &other) const
+ bool operator< (const order &other) const
{
return (cost < other.cost);
}
}
/* can we just switch sides? */
- if (row_from + 1 == row_to && side_from == 1 && side_to == -1) {
+ if (row_from + 1 == row_to && side_from == 1 && side_to == 0) {
return distance_switch(switch_from, switch_to);
}
- if (row_from == row_to + 1 && side_from == -1 && side_to == 1) {
+ if (row_from == row_to + 1 && side_from == 0 && side_to == 1) {
return distance_switch(switch_from, switch_to);
}
/* we'll need to go to one of the three middles */
- int best1 = distance_middle(switch_from, 1) + distance_middle(switch_to, 1);
int best2 = distance_middle(switch_from, 2) + distance_middle(switch_to, 2);
- int best3 = distance_middle(switch_from, 3) + distance_middle(switch_to, 3);
- return std::min(std::min(best1, best2), best3) + distance_row(row_from, row_to);
+ int distrow = distance_row(row_from, row_to);
+ if ((switch_from > 3) != (switch_to > 3))
+ return best2 + distrow;
+ if (switch_from > 3) {
+ int best3 = distance_middle(switch_from, 3) + distance_middle(switch_to, 3);
+ return std::min(best2, best3) + distrow;
+ } else {
+ int best1 = distance_middle(switch_from, 1) + distance_middle(switch_to, 1);
+ return std::min(best2, best1) + distrow;
+ }
}
int optimistic_distance(int row_from, int switch_from, int row_to, int switch_to)
if (abs(row_from - row_to) == 1)
return distance_switch(switch_from, switch_to);
else
- return distance(row_from, switch_from, -1, row_to, switch_to, -1);
+ return distance(row_from, switch_from, 0, row_to, switch_to, 0);
}
// extremely primitive O(V^2) prim
void print_tour(std::vector<std::pair<unsigned, unsigned> > &points)
{
+ std::set<std::pair<unsigned, unsigned> > points_left;
+ for (unsigned i = 0; i < points.size(); ++i) {
+ points_left.insert(points[i]);
+ }
+
for (unsigned i = 0; i < points.size(); ++i) {
- if (best_tour[i].side == -1)
- printf("%2u-%u (left side) ", points[best_tour[i].pt].first,
- points[best_tour[i].pt].second);
+ if (best_tour[i].side == 0)
+ printf("%2u-%u (left side) ", best_tour[i].row, best_tour[i].num);
else
- printf("%2u-%u (right side) ", points[best_tour[i].pt].first,
- points[best_tour[i].pt].second);
+ printf("%2u-%u (right side) ", best_tour[i].row, best_tour[i].num);
if (i == 0) {
printf(" ");
} else {
- unsigned cost = distance(
- points[best_tour[i-1].pt].first,
- points[best_tour[i-1].pt].second,
- best_tour[i-1].side,
- points[best_tour[i].pt].first,
- points[best_tour[i].pt].second,
- best_tour[i].side);
- printf("cost=%4u ", cost);
+ printf("cost=%4u ", best_tour[i].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;
- }
-
+ std::set<std::pair<unsigned, unsigned> > mst_tree = points_left;
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);
+ rest_cost += best_tour[j].cost;
}
printf("rest_cost=%5u", rest_cost);
}
+
printf("\n");
+
+ 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);
}
}
-unsigned do_tsp(std::vector<std::pair<unsigned, unsigned> > &points, order *ord, try_order *temp, unsigned ind, unsigned cost_so_far)
+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)
{
if (cost_so_far >= best_so_far)
return UINT_MAX;
* will give us a sizable cutoff.
*/
unsigned toi = 0;
- unsigned last_row = points[ord[ind-1].pt].first;
- unsigned last_switch = points[ord[ind-1].pt].second;
+ unsigned last_row = ord[ind-1].row;
+ unsigned last_switch = ord[ind-1].num;
unsigned last_side = ord[ind-1].side;
- std::set<std::pair<unsigned, unsigned> > mst_set;
+ std::set<std::pair<unsigned, unsigned> > mst_set = points_left;
mst_set.insert(std::make_pair(last_row, last_switch));
- for (unsigned i = 0; i < points.size(); ++i) {
- /* taken earlier? */
- for (unsigned j = 0; j < ind; ++j) {
- if (ord[j].pt == i)
- goto taken;
- }
-
+ for (std::set<std::pair<unsigned, unsigned> >::iterator i = points_left.begin(); i != points_left.end(); ++i) {
/* try both sides */
- temp[toi].o.pt = i;
- temp[toi].o.side = -1;
- temp[toi].cost = distance(last_row, last_switch, last_side,
- points[i].first, points[i].second, -1);
+ temp[toi].row = i->first;
+ temp[toi].num = i->second;
+ temp[toi].side = 0;
+ temp[toi].cost = distance(last_row, last_switch, last_side, i->first, i->second, 0);
++toi;
- temp[toi].o.pt = i;
- temp[toi].o.side = +1;
- temp[toi].cost = distance(last_row, last_switch, last_side,
- points[i].first, points[i].second, +1);
+ temp[toi].row = i->first;
+ temp[toi].num = i->second;
+ temp[toi].side = 1;
+ temp[toi].cost = distance(last_row, last_switch, last_side, i->first, i->second, 1);
++toi;
-
- mst_set.insert(points[i]);
-
-taken:
- 1;
}
unsigned min_rest_cost = prim_mst(mst_set);
unsigned best_this_cost = UINT_MAX;
for (unsigned i = 0; i < toi; ++i)
{
- ord[ind] = temp[i].o;
- unsigned cost_rest = do_tsp(points, ord, temp + points.size() * 2, ind + 1, cost_so_far + temp[i].cost);
+ ord[ind] = temp[i];
+
+ std::set<std::pair<unsigned, unsigned> >::iterator j = points_left.find(std::make_pair(temp[i].row, temp[i].num));
+ points_left.erase(j);
+ unsigned cost_rest = do_tsp(points, points_left, ord, temp + points.size() * 2, ind + 1, cost_so_far + temp[i].cost);
+ points_left.insert(std::make_pair(temp[i].row, temp[i].num));
+
best_this_cost = std::min(best_this_cost, cost_rest);
}
int main()
{
std::vector<std::pair<unsigned, unsigned> > points;
+ std::set<std::pair<unsigned, unsigned> > points_left;
for ( ;; ) {
unsigned row, sw;
break;
points.push_back(std::make_pair(row, sw));
+ if (points.size() != 1)
+ points_left.insert(std::make_pair(row, sw));
}
order *ord = new order[points.size()];
best_tour = new order[points.size()];
- try_order *temp = new try_order[points.size() * points.size() * 4];
+ order *temp = new order[points.size() * points.size() * 4];
/* always start at the first one, left side (hack) */
- ord[0].pt = 0;
- ord[0].side = -1;
+ ord[0].row = points[0].first;
+ ord[0].num = points[0].second;
+ ord[0].side = 0;
- do_tsp(points, ord, temp, 1, 0);
+ do_tsp(points, points_left, ord, temp, 1, 0);
printf("All done.\n");
}
projects / nms / blobdiff