diff options
| -rw-r--r-- | planning/planning.cpp | 233 |
1 files changed, 159 insertions, 74 deletions
diff --git a/planning/planning.cpp b/planning/planning.cpp index 3a81b36..590d6b1 100644 --- a/planning/planning.cpp +++ b/planning/planning.cpp @@ -2,10 +2,10 @@ // About three times as fast as the old DP+heuristics-based solution // (<2ms for planning TG), and can deal with less regular cost metrics. // -// Given D distro switches and N access switches, complexity is approx. O(dn³) -// (runs n iterations, each iteration is O(VE), V is O(n), E is O(dn))). +// Given D distro switches and N access switches, complexity is approx. O(n²(log d+log n)) +// (runs n iterations, each iteration is O(Vlog E), V is O(n), E is O(dn))). // -// g++ -std=gnu++11 -Wall -g -O2 -DOUTPUT_FILES=1 -o planning planning.cpp && ./planning -3 -6 11 22 -26 35 +// g++ -std=gnu++11 -Wall -g -O3 -fopenmp -DOUTPUT_FILES=1 -o planning planning.cpp && ./planning -3 -6 11 22 -26 35 #include <stdio.h> #include <math.h> @@ -19,9 +19,11 @@ #include <netinet/in.h> #include <arpa/inet.h> +#include <atomic> #include <vector> #include <map> #include <string> +#include <queue> #define NUM_DISTRO 6 #define NUM_ROWS 41 @@ -119,6 +121,11 @@ struct Graph { vector<Edge> edges; vector<Node*> all_nodes; }; +struct CompareByCost { + bool operator() (const Node *a, const Node *b) const { + return a->cost_from_source > b->cost_from_source; + } +}; const unsigned horiz_cost[SWITCHES_PER_ROW] = { 216, 72, 72, 216 // Gap costs are added separately. @@ -144,14 +151,14 @@ class Planner { string *log_buf; unsigned find_distance(Switch from_where, int distro); - unsigned find_slack(Inventory inventory, unsigned distance); unsigned find_cost(Switch from_where, int distro); Inventory find_inventory(Switch from_where, int distro); + unsigned find_slack(Inventory inventory, unsigned distance); void logprintf(const char *str, ...); void init_switches(); void construct_graph(const vector<Switch> &switches, Graph *g); void find_mincost_maxflow(Graph *g); - void print_switch(const Graph &g, int i); + void print_switch(const Graph &g, int i, int distro); public: Planner() : log_buf(NULL) {} @@ -164,13 +171,22 @@ unsigned Planner::find_distance(Switch from_where, int distro) assert(distro != -1); const unsigned dp = std::abs(distro_placements[distro]); - // 3.6m from row to row (2.4m gap + 1.2m boards). - unsigned base_cost = 36 * abs(int(from_where.row) - int(dp)) + - horiz_cost[from_where.num]; + unsigned base_cost = horiz_cost[from_where.num]; if ((distro_placements[distro] >= 0) == (from_where.num >= 2)) { - // 5.0m horizontal gap. + int bridge_row = distro_placements[NUM_DISTRO - 1]; + + // Go to the bridge... + base_cost += 36 * abs(int(from_where.row) - bridge_row); + + // Cross it (5.0m horizontal gap)... base_cost += 50; + + // ...and away from the bridge again. + base_cost += 36 * abs(int(dp) - bridge_row); + } else { + // 3.6m from row to row (2.4m gap + 1.2m boards). + base_cost += 36 * abs(int(from_where.row) - int(dp)); } for (const VerticalGap& gap : vertical_gaps) { @@ -226,6 +242,12 @@ Inventory Planner::find_inventory(Switch from_where, int distro) inv.vert_chasm_crossings = 1; } + // So is the gap over the scene. + if ((abs(distro_placements[distro]) <= 13) == (from_where.row >= 14) && + from_where.num >= 2 && distro_placements[distro] < 0) { + inv.vert_chasm_crossings = 1; + } + return inv; } @@ -247,12 +269,15 @@ unsigned Planner::find_cost(Switch from_where, int distro) // cost = ((distance + 90) / 100) * 100; #endif +#if 0 // We really, really do not want to cross the gap on the north side. + // (now handled in bridge cost) if (from_where.row <= 30) { cost += _INF * inv.horiz_gap_crossings; } else { cost += HORIZ_GAP_COST * inv.horiz_gap_crossings; } +#endif // Also, the gap between Game and Sector 8 is unsurmountable. cost += _INF * inv.vert_chasm_crossings; @@ -393,25 +418,31 @@ void Planner::construct_graph(const vector<Switch> &switches, Graph *g) } g->all_nodes.push_back(&g->source_node); - strcpy(g->source_node.name, "source"); - g->all_nodes.push_back(&g->sink_node); - strcpy(g->sink_node.name, "sink"); for (unsigned i = 0; i < NUM_DISTRO; ++i) { g->all_nodes.push_back(&g->distro_nodes[i]); - sprintf(g->distro_nodes[i].name, "distro%d", i); } for (unsigned i = 0; i < switches.size(); ++i) { g->all_nodes.push_back(&g->switch_nodes[i]); + } + +#if 0 + strcpy(g->source_node.name, "source"); + strcpy(g->sink_node.name, "sink"); + for (unsigned i = 0; i < NUM_DISTRO; ++i) { + sprintf(g->distro_nodes[i].name, "distro%d", i); + } + for (unsigned i = 0; i < switches.size(); ++i) { sprintf(g->switch_nodes[i].name, "switch%d", i); } +#endif } void Planner::find_mincost_maxflow(Graph *g) { - // We use the successive shortest path algorithm, using a primitive Dijkstra - // (not heap-based, so O(VE)) for search. + // We use the successive shortest path algorithm, using a simple + // heap-based Dijkstra (O(Vlog E)) for search. int num_paths = 0; for ( ;; ) { // Reset Dijkstra state. @@ -422,42 +453,44 @@ void Planner::find_mincost_maxflow(Graph *g) } g->source_node.cost_from_source = 0; - for ( ;; ) { - Node *cheapest_unseen_node = NULL; - for (Node *n : g->all_nodes) { - if (n->seen || n->cost_from_source >= _INF) { - continue; - } - if (cheapest_unseen_node == NULL || - n->cost_from_source < cheapest_unseen_node->cost_from_source) { - cheapest_unseen_node = n; - } - } - if (cheapest_unseen_node == NULL) { - // Oops, no usable path. - goto end; + priority_queue<Node *, vector<Node *>, CompareByCost> q; + q.push(&g->source_node); + + while (!q.empty()) { + Node *u = q.top(); + q.pop(); + if (u->seen) { + continue; } - if (cheapest_unseen_node == &g->sink_node) { + u->seen = true; + if (u == &g->sink_node) { // Yay, we found a path to the sink. break; } - cheapest_unseen_node->seen = true; // Relax outgoing edges from this node. - for (Edge *e : cheapest_unseen_node->edges) { + for (Edge *e : u->edges) { + Node *v = e->to; + if (v->seen) { + continue; + } if (e->flow + 1 > e->capacity || e->reverse->flow - 1 > e->reverse->capacity) { // Not feasible. continue; } - if (e->to->cost_from_source <= cheapest_unseen_node->cost_from_source + e->cost) { + if (v->cost_from_source <= u->cost_from_source + e->cost) { // Already seen through a better path. continue; } - e->to->seen = false; - e->to->prev_edge = e; - e->to->cost_from_source = cheapest_unseen_node->cost_from_source + e->cost; + v->prev_edge = e; + v->cost_from_source = u->cost_from_source + e->cost; + q.push(v); } } + if (q.empty()) { + // Oops, no usable path. + goto end; + } // Increase flow along the path, moving backwards towards the source. Node *n = &g->sink_node; @@ -478,26 +511,30 @@ end: logprintf("Augmented using %d paths.\n", num_paths); } -// Figure out which distro this switch was connected to. -int find_distro(const Graph &g, int switch_index) +// Figure out which distro each switch was connected to. +map<int, int> find_switch_distro_map(const Graph &g) { - for (unsigned j = 0; j < NUM_DISTRO; ++j) { - for (Edge *e : g.distro_nodes[j].edges) { - if (e->to == &g.switch_nodes[switch_index] && e->flow > 0) { - return j; + map<int, int> ret; + for (unsigned distro_num = 0; distro_num < NUM_DISTRO; ++distro_num) { + for (Edge *e : g.distro_nodes[distro_num].edges) { + if (e->flow <= 0) { + continue; + } + if (e->to >= &g.switch_nodes[0] && e->to < &g.switch_nodes[g.switch_nodes.size()]) { + int switch_index = (e->to - &g.switch_nodes[0]); + ret.insert(make_pair(switch_index, distro_num)); } } } - return -1; + return ret; } -void Planner::print_switch(const Graph &g, int i) +void Planner::print_switch(const Graph &g, int i, int distro) { if (i == -1) { logprintf("%16s", ""); return; } - int distro = find_distro(g, i); if (distro == -1) { logprintf("[%u;22m- ", distro + 32); #if TRUNCATE_METRIC @@ -523,8 +560,6 @@ int Planner::do_work(int distro_placements[NUM_DISTRO]) { memcpy(this->distro_placements, distro_placements, sizeof(distro_placements[0]) * NUM_DISTRO); - num_ports_used.clear(); - Inventory total_inv; unsigned total_cost = 0, total_slack = 0; @@ -535,6 +570,27 @@ int Planner::do_work(int distro_placements[NUM_DISTRO]) Graph g; construct_graph(switches, &g); find_mincost_maxflow(&g); + map<int, int> switches_to_distros = find_switch_distro_map(g); + + for (unsigned i = 0; i < switches.size(); ++i) { + const auto distro_it = switches_to_distros.find(i); + if (distro_it == switches_to_distros.end()) { + total_cost += _INF; + continue; + } + int distro = distro_it->second; + total_cost += find_cost(switches[i], distro); + int this_distance = find_distance(switches[i], distro); + Inventory this_inv = find_inventory(switches[i], distro); + total_slack += find_slack(this_inv, this_distance); + total_inv += this_inv; + } + +#if !OUTPUT_FILES + if (log_buf == NULL) { + return total_cost; + } +#endif for (unsigned row = 1; row <= NUM_ROWS; ++row) { // Figure out distro markers. @@ -564,7 +620,12 @@ int Planner::do_work(int distro_placements[NUM_DISTRO]) logprintf("[31;22m%2u (%2u-%2u) ", row, row * 2 - 1, row * 2 + 0); for (unsigned num = 0; num < SWITCHES_PER_ROW; ++num) { - print_switch(g, switch_indexes[num]); + const auto distro_it = switches_to_distros.find(switch_indexes[num]); + if (distro_it == switches_to_distros.end()) { + print_switch(g, switch_indexes[num], -1); + } else { + print_switch(g, switch_indexes[num], distro_it->second); + } if (num == 1) { logprintf("%s %s", distro_marker_left, distro_marker_right); @@ -583,29 +644,17 @@ int Planner::do_work(int distro_placements[NUM_DISTRO]) } logprintf("[%u;22m\n", 37); - for (unsigned i = 0; i < switches.size(); ++i) { - int distro = find_distro(g, i); - if (distro == -1) { - total_cost += _INF; - continue; - } - int this_distance = find_distance(switches[i], distro); - Inventory this_inv = find_inventory(switches[i], distro); - total_cost += find_cost(switches[i], distro); - total_slack += find_slack(this_inv, this_distance); - total_inv += this_inv; - } - #if OUTPUT_FILES FILE *patchlist = fopen("patchlist.txt", "w"); FILE *switchlist = fopen("switches.txt", "w"); in_addr_t subnet_address = inet_addr(FIRST_SUBNET_ADDRESS); + num_ports_used.clear(); for (unsigned i = 0; i < switches.size(); ++i) { - int distro = find_distro(g, i); - if (distro == -1) { + const auto distro_it = switches_to_distros.find(i); + if (distro_it == switches_to_distros.end()) { continue; } - + int distro = distro_it->second; int port_num = num_ports_used[distro]++; fprintf(patchlist, "e%u-%u %s %s %s %s %s\n", switches[i].row * 2 - 1, switches[i].num + 1, @@ -649,29 +698,36 @@ int Planner::do_work(int distro_placements[NUM_DISTRO]) for (int i = 0; i < NUM_DISTRO; ++i) { Edge *e = g.source_node.edges[i]; - logprintf("Remaining ports on distro %d: %d\n", i + 1, e->capacity - e->flow); + logprintf("Remaining ports on distro %d: %d\n", i, e->capacity - e->flow); } return total_cost; } -void plan_recursively(int distro_placements[NUM_DISTRO], int distro_num, int min_placement, int max_placement, int *best_cost) +void plan_recursively(int distro_placements[NUM_DISTRO], int distro_num, int min_placement, int max_placement, atomic<int> *best_cost) { if (distro_num == NUM_DISTRO) { - string log; Planner p; - log.clear(); - p.set_log_buf(&log); - int cost = p.do_work(distro_placements); - if (cost >= *best_cost) { +try_again: + int old_best_cost = best_cost->load(); + if (cost >= old_best_cost) { return; } - *best_cost = cost; + if (!best_cost->compare_exchange_weak(old_best_cost, cost)) { + // Someone else changed the value in the meantime. + goto try_again; + } for (unsigned i = 0; i < NUM_DISTRO; ++i) { printf("%d ", distro_placements[i]); } printf("= %d\n", cost); + + // Do it once more, but this time with logging enabled. + string log; + p.set_log_buf(&log); + p.do_work(distro_placements); printf("%s\n", log.c_str()); + return; } @@ -699,9 +755,38 @@ int main(int argc, char **argv) printf("%s\n", log.c_str()); return 0; #else - int best_cost = _INF * 1000; + atomic<int> best_cost(_INF * 1000); distro_placements[0] = -3; // obvious - plan_recursively(distro_placements, 1, 6, NUM_ROWS, &best_cost); + + constexpr int min_placement = 6; + constexpr int max_placement = NUM_ROWS; + + // Boring single-threaded version + // plan_recursively(distro_placements, 1, min_placement, max_placement, &best_cost); + + #pragma omp parallel for schedule(dynamic,1) collapse(2) + for (int i = min_placement; i <= max_placement; ++i) { + for (int j = min_placement; j <= max_placement; ++j) { + if (j <= i) continue; + + int new_distro_placements[NUM_DISTRO]; + memcpy(new_distro_placements, distro_placements, sizeof(distro_placements)); + + new_distro_placements[1] = i; + + new_distro_placements[2] = j; + plan_recursively(new_distro_placements, 3, j + 1, max_placement, &best_cost); + new_distro_placements[2] = -j; + plan_recursively(new_distro_placements, 3, j + 1, max_placement, &best_cost); + + new_distro_placements[1] = -i; + new_distro_placements[2] = j; + plan_recursively(new_distro_placements, 3, j + 1, max_placement, &best_cost); + new_distro_placements[2] = -j; + plan_recursively(new_distro_placements, 3, j + 1, max_placement, &best_cost); + } + } + return 0; #endif } |