/* An earlier version of this program was published on June 27, 2020, which was extended to this version. */ #include #include #define N 39 #define MAX 10000 const char *places[N] = { "Home","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","a","b","c","d","e","f","g","h","i","j","k","l"}; int place(const char *s) { for (int i = 0; i < N; i++) if (strcmp(places[i], s) == 0) return i; fprintf(stderr, "Unknown '%s'\n", s); return -1; } int mat[N][N]; void add(const char *a, const char *b, int l) { int i = place(a); int j = place(b); if (i == -1 || j == -1) return; mat[i][j] = l; mat[j][i] = l; } long d_min = 100000; void measure(const char *r) { int all[N]; for (int i = 0; i < N; i++) all[i] = 0; int v = 0; int d = 0; int pp = -1; while (*r != '\0') { char p[6]; int i = 0; while (*r != '\0' && *r != ',') p[i++] = *r++; p[i] = '\0'; if (*r == ',') r++; i = place(p); if (i == -1) return; if (pp >= 0) { if (mat[pp][i] == MAX) printf("%s-%s ", places[pp], places[i]); d += mat[pp][i]; v++; all[i]++; } pp = i; } for (int i = 0; i < N; i++) if (all[i] != 1) printf("%s: %d ", places[i], all[i]); printf("%d %d\n", v, d); if (d < d_min) d_min = d; } bool selected[N][N]; struct Edge { int place; int distance; bool selected; }; struct Place { Edge edges[N-1]; int selected_distance; int degree; int group; }; Place places2[N]; bool available(int i, int j) { return places2[i].degree != 2 && places2[j].degree != 2 && !selected[i][j]; } long minTotalDistance() { long d = 0; for (int i = 0; i < N; i++) { d += places2[i].selected_distance; int l = places2[i].degree; if (l < 2) { bool no_end = l == 1; for (int j = 0; j < N-1 && l < 2; j++) { int p = places2[i].edges[j].place; if (!selected[i][p] && places2[p].degree < 2 && (!no_end || places2[p].degree == 0)) { l++; d += mat[i][p]; if (places2[p].degree == 1) no_end = true; } } } } return d; } struct SelectEdge { SelectEdge(int i, int j) { _i = i; _j = j; selected[_i][_j] = true; selected[_j][_i] = true; places2[_i].degree++; places2[_j].degree++; places2[_i].selected_distance += mat[i][j]; places2[_j].selected_distance += mat[i][j]; } ~SelectEdge() { selected[_i][_j] = false; selected[_j][_i] = false; places2[_i].degree--; places2[_j].degree--; places2[_i].selected_distance -= mat[_i][_j]; places2[_j].selected_distance -= mat[_i][_j]; } private: int _i; int _j; }; void init() { for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) selected[i][j] = false; for (int i = 0; i < N; i++) { int ps = 0; places2[i].degree = 0; places2[i].group = -1; places2[i].selected_distance = 0; for (int j = 0; j < N; j++) if (i != j) { int pd = mat[i][j]; int pi = j; for (int k = 0; k < ps; k++) if (places2[i].edges[k].distance > pd) { int h_pd = places2[i].edges[k].distance; int h_pi = places2[i].edges[k].place; places2[i].edges[k].distance = pd; places2[i].edges[k].place = pi; pd = h_pd; pi = h_pi; } places2[i].edges[ps].distance = pd; places2[i].edges[ps].place = pi; ps++; } } } #define SSIZE 1000 class Smallest { public: Smallest(int n) : nr(0), max_nr(n) {} void add(int i, int j, long v) { for (int e = 0; e < nr; e++) if (vs[e] > v) { long h_v = vs[e]; int h_i = is[e]; int h_j = js[e]; vs[e] = v; is[e] = i; js[e] = j; v = h_v; i = h_i; j = h_j; } if (nr < max_nr) { vs[nr] = v; is[nr] = i; js[nr] = j; nr++; } } int max_nr; int nr; int is[SSIZE]; int js[SSIZE]; long vs[SSIZE]; }; void expand() { int ps[2]; int nr_p = 0; int p_left; int nr_left = 0; for (int i = 0; i < N; i++) if (places2[i].degree == 0) { nr_left++; p_left = i; } else if (places2[i].degree == 1) ps[nr_p++] = i; if (nr_left == 1) { selected[ps[0]][p_left] = true; selected[p_left][ps[0]] = true; selected[ps[1]][p_left] = true; selected[p_left][ps[1]] = true; int d = 0; for (int i = 0; i < N-1; i++) for (int j = i+1; j < N; j++) if (selected[i][j]) { d += mat[i][j]; } if (d < d_min) { d_min = d; printf("%s", places[0]); int pp = 0; int p; for (p = 1; p < N; p++) if (selected[pp][p]) break; for (;;) { printf("-%s", places[p]); if (p == 0) break; int np; for (np = 0; np < N; np++) if (np != p && np != pp && selected[p][np]) break; pp = p; p = np; } printf(" = %d\n", d); } selected[ps[0]][p_left] = false; selected[p_left][ps[0]] = false; selected[ps[1]][p_left] = false; selected[p_left][ps[1]] = false; return; } Smallest smallest(10); for (int i = 0; i < 2; i++) { int p = ps[i]; for (int k = 0; k < N-1; k++) { int p2 = places2[p].edges[k].place; if (places2[p2].degree == 0) { SelectEdge select(p, p2); long v = minTotalDistance(); if (v <= d_min*2) smallest.add(p, p2, v); } } } int c = 0; for (int i = 0; i < smallest.nr && c < 3; i++) if (smallest.is[i] == smallest.is[0]) { c++; SelectEdge select(smallest.is[i], smallest.js[i]); expand(); } } void solve() { d_min = 100000; init(); // Find ten smallest available distances Smallest smallest(10); for (int i = 0; i < N-1; i++) for (int j = i+1; j < N; j++) if (available(i, j)) smallest.add(i, j, mat[i][j]); printf("%d\n", smallest.nr); // Find out the best to select Smallest smallest2(10); for (int e = 0; e < smallest.nr; e++) { SelectEdge selectData(smallest.is[e], smallest.js[e]); long v = minTotalDistance(); if (v <= d_min*2) smallest2.add(smallest.is[e], smallest.js[e], v); } for (int e = 0; e < smallest2.nr; e++) { SelectEdge selectData(smallest2.is[e], smallest2.js[e]); expand(); } } struct Sol { long d; long sel_d; int edges[2]; struct { int degree; int p[2]; } ps[N]; Sol *next; void init(int p1, int p2) { for (int i = 0; i < N; i++) ps[i].degree = 0; sel_d = 0; add_edge(p1, p2); edges[0] = p1; edges[1] = p2; calc(); } void add_half_edge(int p1, int p2) { if (ps[p1].degree++ == 0) ps[p1].p[0] = p2; else if (ps[p1].p[0] < p2) ps[p1].p[1] = p2; else { ps[p1].p[1] = ps[p1].p[0]; ps[p1].p[0] = p2; } } void add_edge(int p1, int p2) { add_half_edge(p1, p2); add_half_edge(p2, p1); sel_d += mat[p1][p2]; } void add(int p1, int p2) { add_edge(p1, p2); if (edges[0] == p2) p2 = edges[1]; else if (edges[0] == p1) p1 = edges[1]; else if (edges[1] == p2) p2 = edges[0]; else if (edges[1] == p1) p1 = edges[0]; if (p1 > p2) { int h = p1; p1 = p2; p2 = h; } edges[0] = p1; edges[1] = p2; calc(); } void calc() { d = 2 * sel_d; for (int i = 0; i < N; i++) { int l = ps[i].degree; if (l < 2) { bool no_end = l == 1; for (int j = 0; j < N-1 && l < 2; j++) { int p = places2[i].edges[j].place; if (p != ps[i].p[0] && ps[p].degree < 2 && (!no_end || ps[p].degree == 0)) { l++; d += mat[i][p]; if (ps[p].degree == 1) no_end = true; } } } } } bool equal(Sol *sol) { if ( sol->d != d || sol->sel_d != sel_d || sol->edges[0] != edges[0] || sol->edges[1] != edges[1]) return false; for (int i = 0; i < N; i++) if (sol->ps[i].degree != ps[i].degree) return false; else { for (int j = 0; j < ps[i].degree; j++) if (sol->ps[i].p[j] != ps[i].p[j]) return false; } return true; } void print() { int p = edges[0]; int p_p = -1; while (p != edges[1]) { if (p < 0 || p >= N) { printf("%d!!!\n", p); return; } printf("%s-", places[p]); int n_p = -1; for (int i = 0; i < ps[p].degree; i++) if (ps[p].p[i] != p_p) { n_p = ps[p].p[i]; break; } p_p = p; p = n_p; } printf("%s = %ld (%ld)\n", places[p], d, sel_d); } void close() { int m = -1; for (int i = 0; i < N; i++) if (ps[i].degree == 0) { m = i; break; } if (m == -1 || ps[edges[0]].degree != 1 || ps[edges[1]].degree != 1) { printf("Error\n"); return; } int e1 = edges[0]; int e2 = edges[1]; add_edge(m, e1); add_edge(m, e2); edges[0] = 0; edges[1] = 0; d = 2 * sel_d; } void print_comp() { printf("%s", places[0]); int p_p = 0; int p = ps[0].p[0]; for (int i = 0; i < 40; i++) { printf("-%s", places[p]); if (p == 0) break; int n_p = -1; for (int i = 0; i < ps[p].degree; i++) if (ps[p].p[i] != p_p) { n_p = ps[p].p[i]; break; } p_p = p; p = n_p; } for (int i = 0; i < N; i++) if (ps[i].p[0] > ps[i].p[1]) printf(" %d:%d>%d", i, ps[i].p[0], ps[i].p[1]); printf(" = %ld\n", sel_d); } }; Sol *old_sols = 0; Sol *new_sol(Sol &sol, Sol *next) { Sol *n_sol; if (old_sols != 0) { n_sol = old_sols; old_sols = old_sols->next; } else n_sol = new Sol; *n_sol = sol; n_sol->next = next; return n_sol; } void free_sols(Sol *sols) { if (sols == 0) return; Sol **ref_sols = &sols; while (*ref_sols != 0) ref_sols = &(*ref_sols)->next; *ref_sols = old_sols; old_sols = sols; } #define MAX_PSOL 5000 void insert(Sol &sol, Sol **ref_sol) { int n = 0; for (;; n++) if (*ref_sol == 0 || (*ref_sol)->d > sol.d) { (*ref_sol) = new_sol(sol, (*ref_sol)); break; } else if (sol.equal(*ref_sol)) return; else ref_sol = &(*ref_sol)->next; for (;n < MAX_PSOL; n++) if (*ref_sol == 0) return; else ref_sol = &(*ref_sol)->next; if (*ref_sol != 0) { free_sols(*ref_sol); *ref_sol = 0; } } void solve2() { init(); // Find ten smallest available distances Smallest smallest(1000); for (int i = 0; i < N-1; i++) for (int j = i+1; j < N; j++) if (available(i, j)) smallest.add(i, j, mat[i][j]); Sol *cur_sols = 0; for (int e = 0; e < smallest.nr; e++) { Sol sol; sol.init(smallest.is[e], smallest.js[e]); insert(sol, &cur_sols); } for (int pass = 0; pass < N-3; pass++) { fprintf(stderr, "pass %d\n", pass); Sol *next_sols = 0; for (Sol *sol = cur_sols; sol != 0; sol = sol->next) { for (int i = 0; i < 2; i++) { int p = sol->edges[i]; for (int k = 0; k < N-1; k++) { int p2 = places2[p].edges[k].place; if (sol->ps[p2].degree == 0) { Sol n_sol = *sol; n_sol.add(p, p2); if (n_sol.d <= d_min * 2) insert(n_sol, &next_sols); } } } } Sol *prev_sols = cur_sols; cur_sols = next_sols; free_sols(prev_sols); } printf("\n\n"); Sol *final_sols = 0; for (Sol *sol = cur_sols; sol != 0; sol = sol->next) { Sol f_sol = *sol; f_sol.close(); if (f_sol.d <= 2*d_min) insert(f_sol, &final_sols); } for (Sol *sol = final_sols; sol != 0; sol = sol->next) sol->print_comp(); } int main(int argc, char *argv[]) { for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) mat[i][j] = MAX; add("Home","C", 1602); add("Home","D", 434); add("Home","E", 2730); add("Home","F", 2210); add("Home","G", 2234); add("A","B", 1893); add("A","C", 2221); add("A","D", 2980); add("A","R", 1988); add("B","E", 867); add("B","I", 814); add("B","R", 589); add("C","E", 1232); add("C","D", 1602); add("E","F", 831); add("E","J", 767); add("E","I", 803); add("F","G", 795); add("F","J", 827); add("G","H", 1326); add("H","L", 1322); add("H","O", 1837); add("I","J", 531); add("I","Q", 410); add("I","R", 690); add("J","K", 552); add("J","Q", 442); add("K","M", 234); add("K","a", 1144); add("L","M", 244); add("L","N", 386); add("M","N", 188); add("M","a", 1286); add("N","O", 678); add("O","P", 446); add("P","f", 848); add("P","g", 573); add("Q","Y", 1156); add("Q","a", 869); add("R","S", 240); add("R","Y", 963); add("S","T", 468); add("T","U", 400); add("T","W", 464); add("U","V", 994); add("U","X", 694); add("V","b", 652); add("V","l", 927); add("W","X", 260); add("W","Y", 224); add("X","l", 341); add("Y","Z", 774); add("Y","l", 431); add("Z","a", 358); add("Z","i", 472); add("Z","k", 553); add("Z","l", 733); add("a","g", 555); add("b","c", 310); add("c","d", 313); add("d","e", 329); add("d","j", 513); add("e","f", 311); add("e","h", 533); add("f","h", 342); add("g","h", 353); add("g","i", 301); add("h","i", 257); add("h","j", 666); add("i","j", 498); add("i","k", 479); add("j","k", 267); add("j","l", 512); add("k","l", 267); measure("Home,D,C,A,B,R,S,T,U,X,W,Y,l,V,b,c,d,e,f,h,i,j,k,Z,a,g,P,O,H,L,N,M,K,J,Q,I,E,F,G,Home"); // Floyds for (int j = 0; j < N; j++) for (int i = 0; i < N; i++) for (int k = 0; k < N; k++) if (mat[i][k] > mat[i][j] + mat[j][k]) mat[i][k] = mat[i][j] + mat[j][k]; int degree[N]; for (int i = 0; i < N; i++) degree[i] = N-1; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) selected[i][j] = i != j; for (;;) { int max_i, max_j; int max = 0; for (int i = 0; i < N-1; i++) if (degree[i] > 2) for (int j = i+1; j < N; j++) if (degree[j] > 2 && selected[i][j] && mat[i][j] > max) { max = mat[i][j]; max_i = i; max_j = j; } if (max == 0) break; selected[max_i][max_j] = false; degree[max_i]--; degree[max_j]--; } printf("\n"); for (int i = 0; i < N-1; i++) for (int j = i+1; j < N; j++) if (selected[i][j]) printf("%s-%s ", places[i], places[j]); printf("\n"); for (int i = 0; i < N; i++) if (degree[i] != 2) printf("%s:%d ", places[i], degree[i]); printf("\n\n"); /* Home-C Home-D A-B A-R B-R C-D E-I E-J F-G F-J G-H H-L I-Q J-Q K-M K-N L-M N-O O-P P-g R-S S-T T-U U-X V-b V-l W-X W-Y Y-l Z-a Z-i a-g b-c c-d d-e e-f f-h h-i i-j j-k k-l J:3 R:3 i:3 l:3 */ measure("Home,D,A,B,R,S,T,U,X,W,Y,l,V,b,c,d,e,f,h,i,j,k,Z,a,g,P,O,N,M,K,L,H,G,F,J,Q,I,E,C,Home"); // Generating input for TSP Solver and Generator by Oleksii Serdiuk { FILE *f = fopen("out.tspt", "wb"); char header[9] = { 0x54, 0x53, 0x50, 0x54, 0x1, 0x1, 0xB, 0x0, N }; fwrite(header, 1, 9, f); for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (i != j) { union { double v; unsigned char r[8]; } info; info.v = mat[i][j]; unsigned char dd[8]; for (int k = 0; k < 8; k++) dd[k] = info.r[7-k]; fwrite(dd, 1, 8, f); } fclose(f); } // Recursive solver //solve(); /* Home-D-C-A-B-R-S-T-U-X-W-Y-l-k-j-i-g-h-f-e-d-c-b-V-Z-a-P-O-N-M-L-K-J-Q-I-E-F-G-H-Home = 27298 Home-C-E-I-Q-J-F-G-H-K-L-M-N-O-P-a-Z-V-b-c-d-e-f-h-g-i-j-k-l-Y-W-X-U-T-S-R-B-A-D-Home = 26973 Home-C-E-I-Q-J-F-G-H-L-K-M-N-O-P-a-Z-V-b-c-d-e-f-h-g-i-j-k-l-Y-W-X-U-T-S-R-B-A-D-Home = 26485 Home-C-E-I-Q-J-F-G-H-L-K-M-N-O-P-g-a-Z-V-b-c-d-e-f-h-i-j-k-l-Y-W-X-U-T-S-R-B-A-D-Home = 26088 Home-C-E-I-Q-J-F-G-H-L-K-M-N-O-P-g-a-Z-k-j-i-h-f-e-d-c-b-V-l-Y-W-X-U-T-S-R-B-A-D-Home = 25641 Home-C-E-I-Q-J-F-G-H-L-K-M-N-O-P-g-a-Z-Y-W-X-l-k-j-i-h-f-e-d-c-b-V-U-T-S-R-B-A-D-Home = 25412 */ // Batch solver solve2(); /* Home-C-E-I-Q-J-F-G-H-L-M-K-N-O-P-g-a-Z-Y-W-X-l-k-j-i-h-f-e-d-c-b-V-U-T-S-R-B-A-D-Home = 25412 Home-C-E-I-Q-J-F-G-H-L-K-M-N-O-P-g-a-Z-Y-W-X-l-k-j-i-h-f-e-d-c-b-V-U-T-S-R-B-A-D-Home = 25412 Home-C-E-I-Q-J-F-G-H-L-K-M-N-O-P-g-a-Z-Y-W-X-l-j-k-i-h-f-e-d-c-b-V-U-T-S-R-B-A-D-Home = 25638 Home-C-E-I-Q-J-F-G-H-L-M-K-N-O-P-g-a-Z-Y-W-X-l-j-k-i-h-f-e-d-c-b-V-U-T-S-R-B-A-D-Home = 25638 Home-C-E-I-Q-J-F-G-H-L-M-K-N-O-P-g-a-Z-k-j-i-h-f-e-d-c-b-V-l-Y-W-X-U-T-S-R-B-A-D-Home = 25641 Home-C-E-I-Q-J-F-G-H-L-K-M-N-O-P-g-a-Z-k-j-i-h-f-e-d-c-b-V-l-Y-W-X-U-T-S-R-B-A-D-Home = 25641 */ }