a.cpp (18590B)
1 2 #include <csignal> 3 #include <bitset> 4 #include <numeric> 5 #include <map> 6 #include "../louis/louis.cpp" 7 //#include "../mc/lecture.cpp" 8 #include "../mc/prune.cpp" 9 #include "../louis/ameliore.cpp" 10 11 typedef pair<int, vector<int> > pivi; 12 typedef unsigned int uint; 13 14 // ATTENTION: 3 globales maintenues à jour tout le temps, faites pas de conneries ! 15 int score = 0; 16 int temps[8]; 17 int passages[N_ARETES_MAJ]; 18 19 // const int MAX_RM = 7; 20 // const int MAX_ADD = 7; 21 uint MAX_RM = 4; 22 uint MAX_ADD = 4; 23 const int MAX_GIT = 20; 24 volatile bool interrupted = false; 25 26 bool force_affiche_interm = false; 27 void intHandler(int sig) { 28 if (interrupted) { 29 fprintf(stderr, "Ok, ok, j'ai compris\n"); 30 exit(0); 31 } else if (force_affiche_interm) { 32 fprintf(stderr, "Will terminate soon(ish)... ^C à nouveau pour vraiment quitter (pas de sortie)\n"); 33 interrupted = true; 34 } else { 35 fprintf(stderr, "Je vais écrire une solution intermédiaire. ^C à nouveau pour quitter\n"); 36 force_affiche_interm = true; 37 } 38 } 39 40 void affiche_score() { 41 for (int v = 0; v < n_vehicules; v++) 42 fprintf(stderr, "t[%d] = %d\n", v, temps[v]); 43 fprintf(stderr, "score = %d\n", score); 44 } 45 46 void affiche() { 47 affiche_score(); 48 affiche_sortie(_solution); 49 } 50 51 int nbinterm = 0; 52 char interm_filename[255]; 53 char *interm_basename; 54 void affiche_interm() { 55 sprintf(interm_filename, "%s_%05d", interm_basename, nbinterm); 56 affiche_sortie(_solution, interm_filename); 57 affiche_score(); 58 fprintf(stderr, "\t\t\t\t\t\t\t\tPRINT %s\n", interm_filename); 59 nbinterm++; 60 } 61 62 inline void check_interrupt() { 63 if (force_affiche_interm) { 64 affiche_interm(); 65 force_affiche_interm = false; 66 } 67 68 if (interrupted) { 69 affiche(); 70 exit(0); 71 } 72 } 73 74 bool ajoute_fin(int v) { 75 int cur = _solution[v].back(); 76 for (uint i = 0; i < adj[cur].size(); i++) { 77 int voisin = adj[cur][i]; 78 int arete = id_arete[make_pair(cur, voisin)]; 79 if (passages[arete]) 80 continue; 81 if (temps[v] + cout[arete] > t_autorise) 82 continue; 83 _solution[v].push_back(voisin); 84 temps[v] += cout[arete]; 85 if (!passages[arete]) 86 score += longueur[arete]; 87 passages[arete]++; 88 fprintf(stderr, "%d\t+%d\tAjoute fin %d à vehicule %d (t = %d)\n", score, longueur[arete] * (passages[arete] == 1), voisin, v, temps[v]); 89 return true; 90 } 91 return false; 92 } 93 94 #ifdef AJOUTEFORCE 95 bool ajoute_force(int v) { 96 int cur = _solution[v].back(); 97 uint deg = adj[cur].size(); 98 bitset<N_DEGRE_MAJ> a; 99 uint remaining = deg; 100 while (remaining) { 101 uint i = rand() % deg; 102 if (a[i]) 103 continue; 104 a[i] = true; 105 remaining--; 106 107 int voisin = adj[cur][i]; 108 int arete = id_arete[make_pair(cur, voisin)]; 109 if (temps[v] + cout[arete] > t_autorise) 110 continue; 111 _solution[v].push_back(voisin); 112 temps[v] += cout[arete]; 113 if (!passages[arete]) 114 score += longueur[arete]; 115 passages[arete]++; 116 fprintf(stderr, "%d\t+%d\tAjoute force fin %d à vehicule %d (t = %d)\n", score, longueur[arete] * (passages[arete] == 1), voisin, v, temps[v]); 117 return true; 118 } 119 return false; 120 } 121 #else 122 bool ajoute_force(int v) { return false; } 123 #endif 124 125 void mul_pos(int v, uint i, int mul) { 126 // fprintf(stderr, "mul_pos %d %d %d\n", v, i, mul); 127 int arete = id_arete[make_pair(_solution[v][i], _solution[v][i+1])]; 128 temps[v] += cout[arete] * mul; 129 if (!passages[arete]) 130 score += longueur[arete]; 131 passages[arete] += mul; 132 if (!passages[arete]) 133 score -= longueur[arete]; 134 } 135 136 pivi cherche_modif(int v, int debut, int fin, int max_add, int score_a_battre, int temps_a_battre) { 137 pivi best; 138 best.first = -1; 139 for (uint i = 0; i < adj[debut].size(); i++) { 140 int voisin = adj[debut][i]; 141 if (nb_aretes[voisin][fin] > max_add) 142 continue; 143 // if (!max_add && voisin != fin) 144 // continue; 145 int arete = id_arete[make_pair(debut, voisin)]; 146 if (temps[v] + cout[arete] > t_autorise) 147 continue; 148 if (!passages[arete]) 149 score += longueur[arete]; 150 if (!max_add) { 151 if (score > score_a_battre || (score == score_a_battre && temps[v] + cout[arete] < temps_a_battre)) { 152 // fprintf(stderr, "%d > %d (%d -> %d)\n", score, score_a_battre, debut, fin); 153 best.first = score; 154 best.second.push_back(fin); 155 } 156 if (!passages[arete]) 157 score -= longueur[arete]; 158 return best; 159 } 160 passages[arete]++; 161 temps[v] += cout[arete]; 162 pivi cur = cherche_modif(v, voisin, fin, max_add - 1, score_a_battre, temps_a_battre); 163 if (cur.first > best.first) { 164 best = cur; 165 best.second.push_back(voisin); 166 // fprintf(stderr, "add to best %d -> %d\n", debut, voisin); 167 } 168 temps[v] -= cout[arete]; 169 passages[arete]--; 170 if (!passages[arete]) 171 score -= longueur[arete]; 172 } 173 return best; 174 } 175 176 void debug_car(int v) { 177 fprintf(stderr, "Car %d\tt %d :\n ", v, temps[v]); 178 for (uint i = 0; i < _solution[v].size(); i++) 179 fprintf(stderr, "%d ", _solution[v][i]); 180 fprintf(stderr, "\n"); 181 } 182 183 bool modif(int v) { 184 bool didit = false; 185 for (uint rm = 0; rm <= MAX_RM; rm++) { 186 check_interrupt(); 187 for (int pos = int(_solution[v].size()) - rm - 1 ; pos >= 0; pos--) { 188 if (pos + rm + 1 > _solution[v].size()) 189 continue; 190 int prev_score = score; 191 int prev_temps = temps[v]; 192 for (uint dp = 0; dp < rm; dp++) 193 mul_pos(v, pos + dp, -1); 194 pivi mod = cherche_modif(v, _solution[v][pos], _solution[v][pos+rm], MAX_ADD, prev_score, prev_temps); 195 if (mod.first < 0) { 196 for (uint dp = 0; dp < rm; dp++) 197 mul_pos(v, pos + dp, 1); 198 continue; 199 } 200 // debug_car(v); 201 _solution[v].erase(_solution[v].begin() + pos + 1, _solution[v].begin() + pos + 1 + rm); 202 // debug_car(v); 203 _solution[v].insert(_solution[v].begin() + pos + 1, mod.second.rbegin(), mod.second.rend()); 204 // debug_car(v); 205 for (uint j = 0; j < mod.second.size(); j++) 206 mul_pos(v, pos + j, 1); 207 int dt = temps[v] - prev_temps; 208 fprintf(stderr, "%d\t+%d\tModif longueur %zu (rm %d) à vehicule %d pos %d (t %c= %d)\n", score, score - prev_score, mod.second.size(), rm, v, pos, dt > 0 ? '+' : '-', dt > 0 ? dt : -dt); 209 if (score < prev_score || (score == prev_score && dt > 0)) { 210 debug_car(v); 211 exit(0); 212 } 213 didit = true; 214 //return true; 215 } 216 } 217 return didit; 218 } 219 220 #ifdef DEBUG 221 void debug_sol() { 222 vector<int> T = evalue_solution(_solution); 223 fprintf(stderr, "Score %d (vs %d)\n", score, T[0]); 224 for (int v = 0; v < n_vehicules; v++) { 225 fprintf(stderr, "Car %d\tt %d (vs %d) :\n ", v, temps[v], T[v+1]); 226 for (uint i = 0; i < _solution[v].size(); i++) { 227 fprintf(stderr, " %d", _solution[v][i]); 228 #ifdef DEBUGA 229 if (i < _solution[v].size() - 1) { 230 int arete = id_arete[make_pair(_solution[v][i], _solution[v][i+1])]; 231 fprintf(stderr, " [t %d]", cout[arete]); 232 } 233 #endif 234 } 235 fprintf(stderr, "\n"); 236 } 237 fprintf(stderr, "\n"); 238 } 239 #else 240 #define debug_sol() 241 #endif 242 243 /* 244 int order[8] = {0,1,2,3,4,5,6,7}; 245 246 void prune() { 247 random_shuffle(order, order+n_vehicules); 248 for (int i = 0; i < n_vehicules; i++) { 249 int v = order[i]; 250 int skipped_last = 0; 251 vector<int> res(1, _solution[v][0]); 252 253 } 254 }*/ 255 256 void calc_glob() { 257 vector<int> T = evalue_solution(_solution); 258 score = T[0]; 259 memset(passages,0,sizeof(passages)); 260 for (int v = 0; v < n_vehicules; v++) { 261 temps[v] = T[v+1]; 262 for (uint i = 0; i < _solution[v].size() - 1; i++) { 263 int arete = id_arete[make_pair(_solution[v][i], _solution[v][i+1])]; 264 passages[arete]++; 265 } 266 } 267 } 268 269 int temps_total() { 270 return accumulate(temps, temps+n_vehicules, 0); 271 } 272 273 int order[8] = {0, 1, 2, 3, 4, 5, 6, 7}; 274 275 bool prune_and_complete() { 276 random_shuffle(order, order+n_vehicules); 277 278 int prev_temps = temps_total(); 279 int prev_score = score; 280 memset(passages, 0, sizeof(passages)); 281 score = 0; 282 for (int iv = 0; iv < n_vehicules; iv++) { 283 int v = order[iv]; 284 temps[v] = 0; 285 bool skipped_last = false; 286 vector<int> res; 287 res.push_back(_solution[v][0]); 288 for (uint i = 0; i < _solution[v].size() - 1; i++) { 289 int a = id_arete[make_pair(_solution[v][i], _solution[v][i+1])]; 290 if (!a) { 291 fprintf(stderr, "ERREUR"); 292 exit(1); 293 } 294 if (!passages[a]) { 295 if (skipped_last) { 296 while (res.back() != _solution[v][i]) { 297 int n = use[res.back()][_solution[v][i]]; 298 int b = id_arete[make_pair(res.back(), n)]; 299 if (!passages[b]) 300 score += longueur[b]; 301 passages[b]++; 302 temps[v] += cout[b]; 303 res.push_back(n); 304 } 305 } 306 res.push_back(_solution[v][i+1]); 307 if (!passages[a]) 308 score += longueur[a]; 309 passages[a]++; 310 temps[v] += cout[a]; 311 skipped_last = false; 312 } else { 313 skipped_last = true; 314 } 315 } 316 /* 317 if (skipped_last) { 318 while (res.back() != _solution[v].back()) { 319 int n = use[res.back()][_solution[v].back()]; 320 int b = id_arete[make_pair(res.back(), n)]; 321 if (!passages[b]) 322 score += longueur[b]; 323 passages[b]++; 324 temps[v] += cout[b]; 325 res.push_back(n); 326 } 327 } 328 */ 329 _solution[v] = res; 330 } 331 int dt = prev_temps - temps_total(); 332 int ds = score - prev_score; 333 if (dt < 0 || ds < 0) { 334 fprintf(stderr, "Failed to prune correctly, t -= %d\tscore += %d\n", dt, ds); 335 //exit(1); 336 } else if (dt || ds) { 337 fprintf(stderr, "Pruned! t -= %d\tscore += %d\n", dt, ds); 338 return true; 339 } 340 return false; 341 } 342 343 /* 344 <X> A B <Y> B A <Z> A B <T> 345 -> 346 <X> A <Z> A B <Y> B <T> 347 348 <X> B A <Y> A B <Z> A B <T> 349 -> 350 <X> B <Z> A <Y> A B <T> 351 */ 352 bool simplif_elarnon(vector<int> sol[], int v) { 353 short posa[2][N_ARETES_MAJ]; 354 memset(posa, 0, sizeof(posa)); 355 356 for (uint i = 0; i < sol[v].size() - 1; i++) { 357 int a = id_arete[make_pair(sol[v][i], sol[v][i+1])]; 358 int sens = sol[v][i] == depart[a]; 359 if (posa[sens][a] && posa[!sens][a]) { 360 temps[v] -= 2 * cout[a]; 361 passages[a] -= 2; 362 vector<int> res; 363 //fprintf(stderr, "elarnon pos %u/%zu arete %d, deja utilise en %d et %d\n", i, sol[v].size(), a, posa[sens][a]-1, posa[!sens][a]-1); 364 if (posa[sens][a] < posa[!sens][a]) { 365 res.insert(res.end(), sol[v].begin(), sol[v].begin() + posa[sens][a]); // <X> A 366 res.insert(res.end(), sol[v].begin() + posa[!sens][a] + 1, sol[v].begin() + i + 2); // <Z> A B 367 res.insert(res.end(), sol[v].begin() + posa[sens][a] + 1, sol[v].begin() + posa[!sens][a]); // <Y> B 368 res.insert(res.end(), sol[v].begin() + i + 2, sol[v].end()); // <T> 369 } else { 370 res.insert(res.end(), sol[v].begin(), sol[v].begin() + posa[!sens][a]); // <X> B 371 res.insert(res.end(), sol[v].begin() + posa[sens][a] + 1, sol[v].begin() + i + 1); // <Z> A 372 res.insert(res.end(), sol[v].begin() + posa[!sens][a] + 1, sol[v].begin() + posa[sens][a] + 1); // <Y> A B 373 res.insert(res.end(), sol[v].begin() + i + 2, sol[v].end()); // <T> 374 } 375 sol[v] = res; 376 return true; 377 } 378 posa[sens][a] = i+1; 379 } 380 return false; 381 } 382 383 bool simplif_elarnon() { 384 int prev_temps = temps_total(); 385 random_shuffle(order, order+n_vehicules); 386 bool r = false; 387 for (int i = 0; i < n_vehicules; i++) { 388 int v = order[i]; 389 r |= simplif_elarnon(_solution, v); 390 } 391 if (r) { 392 int dt = prev_temps - temps_total(); 393 fprintf(stderr, "Elarnon in action, t -= %d\n", dt); 394 } 395 return r; 396 } 397 398 void vraie_etoile(vector<int> sol[]) { 399 400 bool ameliore = true; 401 double d[n_vehicules]; 402 fill(d, d+n_vehicules, 0.0); 403 while (ameliore) { 404 ameliore = false; 405 for (int v = 0; v < n_vehicules; v++) { 406 double best = -42.0; 407 int bestVoisin = -1; 408 int bestArete = -1; 409 int cur = sol[v].back(); 410 for (uint i = 0; i < adj[cur].size(); i++) { 411 int voisin = adj[cur][i]; 412 int a = id_arete[make_pair(cur, voisin)]; 413 if (temps[v] + cout[a] > t_autorise) 414 continue; 415 double mi = 19840000.0; 416 for (int w = 0; w < n_vehicules; w++) 417 if (v != w) { 418 #ifdef JUSTHEAD 419 int wcur = sol[w].back(); 420 #else 421 for (uint j = 0; j < sol[w].size(); j++) { 422 int wcur = sol[w][j]; 423 #endif 424 mi = min(mi, hypot(longitude[voisin] - longitude[wcur], 425 latitude[voisin] - latitude[wcur])); 426 #ifndef JUSTHEAD 427 } 428 #endif 429 } 430 #ifdef LONDONISBAD 431 mi = min(mi, hypot(longitude[voisin] - longitude[s_depart], 432 latitude[voisin] - latitude[s_depart])); 433 #endif 434 if (mi > best) { 435 best = mi; 436 bestVoisin = voisin; 437 bestArete = a; 438 } 439 } 440 if (bestVoisin < 0) 441 continue; 442 //fprintf(stderr, "Etoile v %d, go to %d, dist %lf\n", v, bestVoisin, best); 443 if (best > d[v]) { 444 ameliore = true; 445 d[v] = best; 446 } 447 #ifdef BRUTETOILE 448 d[v] = best; 449 #endif 450 sol[v].push_back(bestVoisin); 451 temps[v] += cout[bestArete]; 452 if (!passages[bestArete]) 453 score += longueur[bestArete]; 454 passages[bestArete]++; 455 } 456 } 457 } 458 459 void positions_choisies() { 460 _solution[0].push_back(plus_proche(48.848451,2.263328)); 461 _solution[1].push_back(plus_proche(48.836136,2.289421)); 462 _solution[2].push_back(plus_proche(48.825401,2.334568)); 463 _solution[3].push_back(plus_proche(48.830939,2.377998)); 464 _solution[4].push_back(plus_proche(48.862004,2.407696)); 465 _solution[5].push_back(plus_proche(48.88673,2.394306)); 466 _solution[6].push_back(plus_proche(48.897791,2.357399)); 467 _solution[7].push_back(plus_proche(48.886053,2.288048)); 468 } 469 470 inline double dist(int s1, int s2) { 471 return hypot(longitude[s1] - longitude[s2], latitude[s1] - latitude[s2]); 472 } 473 474 void gloutonne() { 475 const double INF = 123456789.0; 476 int GLOUTONNE_MAX = n_aretes; 477 vector<pair<int, int> > ar; 478 for (int a = 1; a <= n_aretes; a++) 479 ar.push_back(make_pair(longueur[a], a)); 480 sort(ar.begin(), ar.end()); 481 GLOUTONNE_MAX = min(GLOUTONNE_MAX, int(ar.size())); 482 for (int i = 0; i < GLOUTONNE_MAX; i++) { 483 int a = ar[i].second; 484 if (passages[a]) 485 continue; 486 double d[n_vehicules]; 487 bool o[n_vehicules]; 488 uint p[n_vehicules]; 489 for (int v = 0; v < n_vehicules; v++) { 490 d[v] = INF; 491 if (temps[v] >= t_autorise) 492 continue; 493 for (uint j = 0; j < _solution[v].size(); j++) { 494 double f = dist(_solution[v][j], depart[a]); 495 if (f < d[v]) { 496 d[v] = f; 497 o[v] = false; 498 p[v] = j; 499 } 500 if (dbsens[a]) { 501 double e = dist(_solution[v].back(), arrivee[a]); 502 if (e < d[v]) { 503 d[v] = e; 504 o[v] = true; 505 p[v] = j; 506 } 507 } 508 } 509 } 510 int v = min_element(d, d + n_vehicules) - d; 511 if (d[v] == INF) 512 break; 513 int go; 514 if (o[v]) 515 go = arrivee[a]; 516 else 517 go = depart[a]; 518 fprintf(stderr, "Gloutonne, vehicule %d, pos %u va à %d pour arête %d\n", v, p[v], go, a); 519 vector<int> toinsert; 520 toinsert.push_back(_solution[v][p[v]]); 521 while (toinsert.back() != go) { 522 int u = use[toinsert.back()][go]; 523 int b = id_arete[make_pair(toinsert.back(), u)]; 524 if (!passages[b]) 525 score += longueur[b]; 526 passages[b]++; 527 temps[v] += cout[b]; 528 toinsert.push_back(u); 529 } 530 if (p[v] < _solution[v].size() - 1) { 531 if (!passages[a]) { 532 toinsert.push_back(go == arrivee[a] ? depart[a] : arrivee[a]); 533 temps[v] += cout[a]; 534 score += longueur[a]; 535 } 536 passages[a]++; 537 go = _solution[v][p[v]]; 538 while (toinsert.back() != go) { 539 int u = use[toinsert.back()][go]; 540 int b = id_arete[make_pair(toinsert.back(), u)]; 541 if (!passages[b]) 542 score += longueur[b]; 543 passages[b]++; 544 temps[v] += cout[b]; 545 toinsert.push_back(u); 546 } 547 } 548 _solution[v].erase(_solution[v].begin() + p[v]); 549 _solution[v].insert(_solution[v].begin() + p[v], toinsert.begin(), toinsert.end()); 550 } 551 } 552 553 bool try_ameliore_louis() { 554 int prev_score = score; 555 ameliore_louis(_solution); 556 calc_glob(); 557 if (score > prev_score) { 558 559 fprintf(stderr, "Merci Louis ! (score += %d)\n", score - prev_score); 560 return true; 561 } 562 if (prev_score > score) { 563 fprintf(stderr, "Louis, tu fais de la merde (score -= %d)\n", prev_score - score); 564 exit(1); 565 } 566 fprintf(stderr, "Louis, inutile !\n"); 567 return false; 568 } 569 570 void print_stats() { 571 map<int, int> nb_passages; 572 for (int a = 1; a <= n_aretes; a++) 573 nb_passages[passages[a]]++; 574 int m = nb_passages.rbegin()->first; 575 for (int p = 0; p <= m; p++) 576 fprintf(stderr, "%d route%s à %d passage%s\n", nb_passages[p], nb_passages[p] >= 2 ? "s" : "", p, p >= 2 ? "s" : ""); 577 } 578 579 int main(int argc, char *argv[]) { 580 /* 581 Usage: a.out [INTERM_BASENAME [INIT_SOLUTION]] 582 INTERM_BASENAME: nom de base pour écrire les solutions intermédiaires 583 INIT_SOLUTION: nom du fichier de la solution initiale 584 */ 585 586 signal(SIGINT, intHandler); 587 588 srand(1337); 589 lecture_entree(); 590 init_use(); 591 init_nb_aretes(); 592 593 if (argc > 2) 594 lire_solution(argv[2], _solution); 595 else { 596 init_solution(_solution); 597 // vraie_etoile(_solution); 598 #ifdef CHOIZ 599 positions_choisies(); 600 complete_all(_solution); 601 #endif 602 #ifdef GLOUTONNE 603 gloutonne(); 604 tronque_solution(_solution); 605 #endif 606 } 607 608 calc_glob(); 609 affiche_score(); 610 print_stats(); 611 612 debug_sol(); 613 prune_and_complete(); 614 debug_sol(); 615 616 bool ameliore = true; 617 bitset<8> prev_amel, amel; 618 619 fprintf(stderr, "C'est parti...\n"); 620 621 if (argc > 1) 622 interm_basename = argv[1]; 623 624 int it = 0; 625 for (int git = 0; git < MAX_GIT; git++) { 626 fprintf(stderr, "On passe aux rm<=%d et add<=%d\n", MAX_RM, MAX_ADD); 627 ameliore = 1; 628 for (; ameliore; it++) { 629 debug_sol(); 630 631 ameliore = 0; 632 prev_amel = amel; 633 #pragma omp parallel for 634 for (int v = 0; v < n_vehicules; v++) 635 ameliore |= amel[v] = ajoute_fin(v) || (!prev_amel[v] && ajoute_force(v)); 636 637 check_interrupt(); 638 639 debug_sol(); 640 641 random_shuffle(order, order+n_vehicules); 642 for (int i = 0; i < n_vehicules; i++) { 643 int v = order[i]; 644 ameliore |= amel[v] = amel[v] || modif(v); 645 } 646 647 ameliore |= prune_and_complete(); 648 ameliore |= simplif_elarnon(); 649 650 check_interrupt(); 651 // if (!ameliore) 652 // ameliore = try_ameliore_louis(); 653 } 654 MAX_ADD++; 655 MAX_RM+=2; 656 } 657 658 affiche(); 659 }