commit 24928d67a2807f940ce4feae7dafddaded8eafee
parent b63726e7909eac79b536506b693166288ec9dc4d
Author: Marc Jeanmougin <marc@jeanmougin.fr>
Date: Thu, 10 Apr 2014 01:29:35 +0200
utility
Diffstat:
2 files changed, 754 insertions(+), 0 deletions(-)
diff --git a/contest/mehdi/a.cpp b/contest/mehdi/a.cpp
@@ -629,6 +629,7 @@ int main(int argc, char *argv[]) {
ameliore = 0;
prev_amel = amel;
+ #pragma omp parallel for
for (int v = 0; v < n_vehicules; v++)
ameliore |= amel[v] = ajoute_fin(v) || (!prev_amel[v] && ajoute_force(v));
diff --git a/contest/mehdi/b.cpp b/contest/mehdi/b.cpp
@@ -0,0 +1,753 @@
+
+#include <csignal>
+#include <bitset>
+#include <numeric>
+#include <map>
+#include "../louis/louis.cpp"
+//#include "../mc/lecture.cpp"
+#include "../mc/prune.cpp"
+#include "../louis/ameliore.cpp"
+
+typedef pair<int, vector<int> > pivi;
+typedef unsigned int uint;
+
+// ATTENTION: 3 globales maintenues à jour tout le temps, faites pas de conneries !
+int score = 0;
+int temps[8];
+int passages[N_ARETES_MAJ];
+
+// const int MAX_RM = 7;
+// const int MAX_ADD = 7;
+uint MAX_RM = 4;
+uint MAX_ADD = 4;
+const int MAX_GIT = 20;
+volatile bool interrupted = false;
+
+bool force_affiche_interm = false;
+void intHandler(int sig) {
+ if (interrupted) {
+ fprintf(stderr, "Ok, ok, j'ai compris\n");
+ exit(0);
+ } else if (force_affiche_interm) {
+ fprintf(stderr, "Will terminate soon(ish)... ^C à nouveau pour vraiment quitter (pas de sortie)\n");
+ interrupted = true;
+ } else {
+ fprintf(stderr, "Je vais écrire une solution intermédiaire. ^C à nouveau pour quitter\n");
+ force_affiche_interm = true;
+ }
+}
+
+void affiche_score() {
+ for (int v = 0; v < n_vehicules; v++)
+ fprintf(stderr, "t[%d] = %d\n", v, temps[v]);
+ fprintf(stderr, "score = %d\n", score);
+}
+
+void affiche() {
+ affiche_score();
+ affiche_sortie(_solution);
+}
+
+int nbinterm = 0;
+char interm_filename[255];
+char *interm_basename;
+void affiche_interm() {
+ sprintf(interm_filename, "%s_%05d", interm_basename, nbinterm);
+ affiche_sortie(_solution, interm_filename);
+ affiche_score();
+ fprintf(stderr, "\t\t\t\t\t\t\t\tPRINT %s\n", interm_filename);
+ nbinterm++;
+}
+
+inline void check_interrupt() {
+ if (force_affiche_interm) {
+ affiche_interm();
+ force_affiche_interm = false;
+ }
+
+ if (interrupted) {
+ affiche();
+ exit(0);
+ }
+}
+
+bool ajoute_fin(int v) {
+ int cur = _solution[v].back();
+ for (uint i = 0; i < adj[cur].size(); i++) {
+ int voisin = adj[cur][i];
+ int arete = id_arete[make_pair(cur, voisin)];
+ if (passages[arete])
+ continue;
+ if (temps[v] + cout[arete] > t_autorise)
+ continue;
+ _solution[v].push_back(voisin);
+ temps[v] += cout[arete];
+ if (!passages[arete])
+ score += longueur[arete];
+ passages[arete]++;
+ fprintf(stderr, "%d\t+%d\tAjoute fin %d à vehicule %d (t = %d)\n", score, longueur[arete] * (passages[arete] == 1), voisin, v, temps[v]);
+ return true;
+ }
+ return false;
+}
+
+#ifdef AJOUTEFORCE
+bool ajoute_force(int v) {
+ int cur = _solution[v].back();
+ uint deg = adj[cur].size();
+ bitset<N_DEGRE_MAJ> a;
+ uint remaining = deg;
+ while (remaining) {
+ uint i = rand() % deg;
+ if (a[i])
+ continue;
+ a[i] = true;
+ remaining--;
+
+ int voisin = adj[cur][i];
+ int arete = id_arete[make_pair(cur, voisin)];
+ if (temps[v] + cout[arete] > t_autorise)
+ continue;
+ _solution[v].push_back(voisin);
+ temps[v] += cout[arete];
+ if (!passages[arete])
+ score += longueur[arete];
+ passages[arete]++;
+ fprintf(stderr, "%d\t+%d\tAjoute force fin %d à vehicule %d (t = %d)\n", score, longueur[arete] * (passages[arete] == 1), voisin, v, temps[v]);
+ return true;
+ }
+ return false;
+}
+#else
+bool ajoute_force(int v) { return false; }
+#endif
+
+void mul_pos(int v, uint i, int mul) {
+ // fprintf(stderr, "mul_pos %d %d %d\n", v, i, mul);
+ int arete = id_arete[make_pair(_solution[v][i], _solution[v][i+1])];
+ temps[v] += cout[arete] * mul;
+ if (!passages[arete])
+ score += longueur[arete];
+ passages[arete] += mul;
+ if (!passages[arete])
+ score -= longueur[arete];
+}
+
+pivi cherche_modif(int v, int debut, int fin, int max_add, int score_a_battre, int temps_a_battre) {
+ pivi best;
+ best.first = -1;
+ for (uint i = 0; i < adj[debut].size(); i++) {
+ int voisin = adj[debut][i];
+ if (nb_aretes[voisin][fin] > max_add)
+ continue;
+ // if (!max_add && voisin != fin)
+ // continue;
+ int arete = id_arete[make_pair(debut, voisin)];
+ if (temps[v] + cout[arete] > t_autorise)
+ continue;
+ if (!passages[arete])
+ score += longueur[arete];
+ if (!max_add) {
+ if (score > score_a_battre || (score == score_a_battre && temps[v] + cout[arete] < temps_a_battre)) {
+ // fprintf(stderr, "%d > %d (%d -> %d)\n", score, score_a_battre, debut, fin);
+ best.first = score;
+ best.second.push_back(fin);
+ }
+ if (!passages[arete])
+ score -= longueur[arete];
+ return best;
+ }
+ passages[arete]++;
+ temps[v] += cout[arete];
+ pivi cur = cherche_modif(v, voisin, fin, max_add - 1, score_a_battre, temps_a_battre);
+ if (cur.first > best.first) {
+ best = cur;
+ best.second.push_back(voisin);
+ // fprintf(stderr, "add to best %d -> %d\n", debut, voisin);
+ }
+ temps[v] -= cout[arete];
+ passages[arete]--;
+ if (!passages[arete])
+ score -= longueur[arete];
+ }
+ return best;
+}
+
+void debug_car(int v) {
+ fprintf(stderr, "Car %d\tt %d :\n ", v, temps[v]);
+ for (uint i = 0; i < _solution[v].size(); i++)
+ fprintf(stderr, "%d ", _solution[v][i]);
+ fprintf(stderr, "\n");
+}
+
+bool modif(int v) {
+ bool didit = false;
+ for (uint rm = 0; rm <= MAX_RM; rm++) {
+ check_interrupt();
+ for (int pos = int(_solution[v].size()) - rm - 1 ; pos >= 0; pos--) {
+ if (pos + rm + 1 > _solution[v].size())
+ continue;
+ int prev_score = score;
+ int prev_temps = temps[v];
+ for (uint dp = 0; dp < rm; dp++)
+ mul_pos(v, pos + dp, -1);
+ pivi mod = cherche_modif(v, _solution[v][pos], _solution[v][pos+rm], MAX_ADD, prev_score, prev_temps);
+ if (mod.first < 0) {
+ for (uint dp = 0; dp < rm; dp++)
+ mul_pos(v, pos + dp, 1);
+ continue;
+ }
+ // debug_car(v);
+ _solution[v].erase(_solution[v].begin() + pos + 1, _solution[v].begin() + pos + 1 + rm);
+ // debug_car(v);
+ _solution[v].insert(_solution[v].begin() + pos + 1, mod.second.rbegin(), mod.second.rend());
+ // debug_car(v);
+ for (uint j = 0; j < mod.second.size(); j++)
+ mul_pos(v, pos + j, 1);
+ int dt = temps[v] - prev_temps;
+ 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);
+ if (score < prev_score || (score == prev_score && dt > 0)) {
+ debug_car(v);
+ exit(0);
+ }
+ didit = true;
+ //return true;
+ }
+ }
+ return didit;
+}
+
+#ifdef DEBUG
+void debug_sol() {
+ vector<int> T = evalue_solution(_solution);
+ fprintf(stderr, "Score %d (vs %d)\n", score, T[0]);
+ for (int v = 0; v < n_vehicules; v++) {
+ fprintf(stderr, "Car %d\tt %d (vs %d) :\n ", v, temps[v], T[v+1]);
+ for (uint i = 0; i < _solution[v].size(); i++) {
+ fprintf(stderr, " %d", _solution[v][i]);
+#ifdef DEBUGA
+ if (i < _solution[v].size() - 1) {
+ int arete = id_arete[make_pair(_solution[v][i], _solution[v][i+1])];
+ fprintf(stderr, " [t %d]", cout[arete]);
+ }
+#endif
+ }
+ fprintf(stderr, "\n");
+ }
+ fprintf(stderr, "\n");
+}
+#else
+#define debug_sol()
+#endif
+
+/*
+int order[8] = {0,1,2,3,4,5,6,7};
+
+void prune() {
+ random_shuffle(order, order+n_vehicules);
+ for (int i = 0; i < n_vehicules; i++) {
+ int v = order[i];
+ int skipped_last = 0;
+ vector<int> res(1, _solution[v][0]);
+
+ }
+}*/
+
+void calc_glob() {
+ vector<int> T = evalue_solution(_solution);
+ score = T[0];
+ memset(passages,0,sizeof(passages));
+ for (int v = 0; v < n_vehicules; v++) {
+ temps[v] = T[v+1];
+ for (uint i = 0; i < _solution[v].size() - 1; i++) {
+ int arete = id_arete[make_pair(_solution[v][i], _solution[v][i+1])];
+ passages[arete]++;
+ }
+ }
+}
+
+int temps_total() {
+ return accumulate(temps, temps+n_vehicules, 0);
+}
+
+int order[8] = {0, 1, 2, 3, 4, 5, 6, 7};
+
+bool prune_and_complete() {
+ random_shuffle(order, order+n_vehicules);
+
+ int prev_temps = temps_total();
+ int prev_score = score;
+ memset(passages, 0, sizeof(passages));
+ score = 0;
+ for (int iv = 0; iv < n_vehicules; iv++) {
+ int v = order[iv];
+ temps[v] = 0;
+ bool skipped_last = false;
+ vector<int> res;
+ res.push_back(_solution[v][0]);
+ for (uint i = 0; i < _solution[v].size() - 1; i++) {
+ int a = id_arete[make_pair(_solution[v][i], _solution[v][i+1])];
+ if (!a) {
+ fprintf(stderr, "ERREUR");
+ exit(1);
+ }
+ if (!passages[a]) {
+ if (skipped_last) {
+ while (res.back() != _solution[v][i]) {
+ int n = use[res.back()][_solution[v][i]];
+ int b = id_arete[make_pair(res.back(), n)];
+ if (!passages[b])
+ score += longueur[b];
+ passages[b]++;
+ temps[v] += cout[b];
+ res.push_back(n);
+ }
+ }
+ res.push_back(_solution[v][i+1]);
+ if (!passages[a])
+ score += longueur[a];
+ passages[a]++;
+ temps[v] += cout[a];
+ skipped_last = false;
+ } else {
+ skipped_last = true;
+ }
+ }
+ /*
+ if (skipped_last) {
+ while (res.back() != _solution[v].back()) {
+ int n = use[res.back()][_solution[v].back()];
+ int b = id_arete[make_pair(res.back(), n)];
+ if (!passages[b])
+ score += longueur[b];
+ passages[b]++;
+ temps[v] += cout[b];
+ res.push_back(n);
+ }
+ }
+ */
+ _solution[v] = res;
+ }
+ int dt = prev_temps - temps_total();
+ int ds = score - prev_score;
+ if (dt < 0 || ds < 0) {
+ fprintf(stderr, "Failed to prune correctly, t -= %d\tscore += %d\n", dt, ds);
+ //exit(1);
+ } else if (dt || ds) {
+ fprintf(stderr, "Pruned! t -= %d\tscore += %d\n", dt, ds);
+ return true;
+ }
+ return false;
+}
+
+/*
+ <X> A B <Y> B A <Z> A B <T>
+ ->
+ <X> A <Z> A B <Y> B <T>
+
+ <X> B A <Y> A B <Z> A B <T>
+ ->
+ <X> B <Z> A <Y> A B <T>
+ */
+bool simplif_elarnon(vector<int> sol[], int v) {
+ short posa[2][N_ARETES_MAJ];
+ memset(posa, 0, sizeof(posa));
+
+ for (uint i = 0; i < sol[v].size() - 1; i++) {
+ int a = id_arete[make_pair(sol[v][i], sol[v][i+1])];
+ int sens = sol[v][i] == depart[a];
+ if (posa[sens][a] && posa[!sens][a]) {
+ temps[v] -= 2 * cout[a];
+ passages[a] -= 2;
+ vector<int> res;
+ //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);
+ if (posa[sens][a] < posa[!sens][a]) {
+ res.insert(res.end(), sol[v].begin(), sol[v].begin() + posa[sens][a]); // <X> A
+ res.insert(res.end(), sol[v].begin() + posa[!sens][a] + 1, sol[v].begin() + i + 2); // <Z> A B
+ res.insert(res.end(), sol[v].begin() + posa[sens][a] + 1, sol[v].begin() + posa[!sens][a]); // <Y> B
+ res.insert(res.end(), sol[v].begin() + i + 2, sol[v].end()); // <T>
+ } else {
+ res.insert(res.end(), sol[v].begin(), sol[v].begin() + posa[!sens][a]); // <X> B
+ res.insert(res.end(), sol[v].begin() + posa[sens][a] + 1, sol[v].begin() + i + 1); // <Z> A
+ res.insert(res.end(), sol[v].begin() + posa[!sens][a] + 1, sol[v].begin() + posa[sens][a] + 1); // <Y> A B
+ res.insert(res.end(), sol[v].begin() + i + 2, sol[v].end()); // <T>
+ }
+ sol[v] = res;
+ return true;
+ }
+ posa[sens][a] = i+1;
+ }
+ return false;
+}
+
+bool simplif_elarnon() {
+ int prev_temps = temps_total();
+ random_shuffle(order, order+n_vehicules);
+ bool r = false;
+ for (int i = 0; i < n_vehicules; i++) {
+ int v = order[i];
+ r |= simplif_elarnon(_solution, v);
+ }
+ if (r) {
+ int dt = prev_temps - temps_total();
+ fprintf(stderr, "Elarnon in action, t -= %d\n", dt);
+ }
+ return r;
+}
+
+void vraie_etoile(vector<int> sol[]) {
+
+ bool ameliore = true;
+ double d[n_vehicules];
+ fill(d, d+n_vehicules, 0.0);
+ while (ameliore) {
+ ameliore = false;
+ for (int v = 0; v < n_vehicules; v++) {
+ double best = -42.0;
+ int bestVoisin = -1;
+ int bestArete = -1;
+ int cur = sol[v].back();
+ for (uint i = 0; i < adj[cur].size(); i++) {
+ int voisin = adj[cur][i];
+ int a = id_arete[make_pair(cur, voisin)];
+ if (temps[v] + cout[a] > t_autorise)
+ continue;
+ double mi = 19840000.0;
+ for (int w = 0; w < n_vehicules; w++)
+ if (v != w) {
+#ifdef JUSTHEAD
+ int wcur = sol[w].back();
+#else
+ for (uint j = 0; j < sol[w].size(); j++) {
+ int wcur = sol[w][j];
+#endif
+ mi = min(mi, hypot(longitude[voisin] - longitude[wcur],
+ latitude[voisin] - latitude[wcur]));
+#ifndef JUSTHEAD
+ }
+#endif
+ }
+#ifdef LONDONISBAD
+ mi = min(mi, hypot(longitude[voisin] - longitude[s_depart],
+ latitude[voisin] - latitude[s_depart]));
+#endif
+ if (mi > best) {
+ best = mi;
+ bestVoisin = voisin;
+ bestArete = a;
+ }
+ }
+ if (bestVoisin < 0)
+ continue;
+ //fprintf(stderr, "Etoile v %d, go to %d, dist %lf\n", v, bestVoisin, best);
+ if (best > d[v]) {
+ ameliore = true;
+ d[v] = best;
+ }
+#ifdef BRUTETOILE
+ d[v] = best;
+#endif
+ sol[v].push_back(bestVoisin);
+ temps[v] += cout[bestArete];
+ if (!passages[bestArete])
+ score += longueur[bestArete];
+ passages[bestArete]++;
+ }
+ }
+}
+
+void positions_choisies() {
+ _solution[0].push_back(plus_proche(48.848451,2.263328));
+ _solution[1].push_back(plus_proche(48.836136,2.289421));
+ _solution[2].push_back(plus_proche(48.825401,2.334568));
+ _solution[3].push_back(plus_proche(48.830939,2.377998));
+ _solution[4].push_back(plus_proche(48.862004,2.407696));
+ _solution[5].push_back(plus_proche(48.88673,2.394306));
+ _solution[6].push_back(plus_proche(48.897791,2.357399));
+ _solution[7].push_back(plus_proche(48.886053,2.288048));
+}
+
+inline double dist(int s1, int s2) {
+ return hypot(longitude[s1] - longitude[s2], latitude[s1] - latitude[s2]);
+}
+
+void gloutonne() {
+ const double INF = 123456789.0;
+ int GLOUTONNE_MAX = n_aretes;
+ vector<pair<int, int> > ar;
+ for (int a = 1; a <= n_aretes; a++)
+ ar.push_back(make_pair(longueur[a], a));
+ sort(ar.begin(), ar.end());
+ GLOUTONNE_MAX = min(GLOUTONNE_MAX, int(ar.size()));
+ for (int i = 0; i < GLOUTONNE_MAX; i++) {
+ int a = ar[i].second;
+ if (passages[a])
+ continue;
+ double d[n_vehicules];
+ bool o[n_vehicules];
+ uint p[n_vehicules];
+ for (int v = 0; v < n_vehicules; v++) {
+ d[v] = INF;
+ if (temps[v] >= t_autorise)
+ continue;
+ for (uint j = 0; j < _solution[v].size(); j++) {
+ double f = dist(_solution[v][j], depart[a]);
+ if (f < d[v]) {
+ d[v] = f;
+ o[v] = false;
+ p[v] = j;
+ }
+ if (dbsens[a]) {
+ double e = dist(_solution[v].back(), arrivee[a]);
+ if (e < d[v]) {
+ d[v] = e;
+ o[v] = true;
+ p[v] = j;
+ }
+ }
+ }
+ }
+ int v = min_element(d, d + n_vehicules) - d;
+ if (d[v] == INF)
+ break;
+ int go;
+ if (o[v])
+ go = arrivee[a];
+ else
+ go = depart[a];
+ fprintf(stderr, "Gloutonne, vehicule %d, pos %u va à %d pour arête %d\n", v, p[v], go, a);
+ vector<int> toinsert;
+ toinsert.push_back(_solution[v][p[v]]);
+ while (toinsert.back() != go) {
+ int u = use[toinsert.back()][go];
+ int b = id_arete[make_pair(toinsert.back(), u)];
+ if (!passages[b])
+ score += longueur[b];
+ passages[b]++;
+ temps[v] += cout[b];
+ toinsert.push_back(u);
+ }
+ if (p[v] < _solution[v].size() - 1) {
+ if (!passages[a]) {
+ toinsert.push_back(go == arrivee[a] ? depart[a] : arrivee[a]);
+ temps[v] += cout[a];
+ score += longueur[a];
+ }
+ passages[a]++;
+ go = _solution[v][p[v]];
+ while (toinsert.back() != go) {
+ int u = use[toinsert.back()][go];
+ int b = id_arete[make_pair(toinsert.back(), u)];
+ if (!passages[b])
+ score += longueur[b];
+ passages[b]++;
+ temps[v] += cout[b];
+ toinsert.push_back(u);
+ }
+ }
+ _solution[v].erase(_solution[v].begin() + p[v]);
+ _solution[v].insert(_solution[v].begin() + p[v], toinsert.begin(), toinsert.end());
+ }
+}
+
+bool try_ameliore_louis() {
+ int prev_score = score;
+ ameliore_louis(_solution);
+ calc_glob();
+ if (score > prev_score) {
+
+ fprintf(stderr, "Merci Louis ! (score += %d)\n", score - prev_score);
+ return true;
+ }
+ if (prev_score > score) {
+ fprintf(stderr, "Louis, tu fais de la merde (score -= %d)\n", prev_score - score);
+ exit(1);
+ }
+ fprintf(stderr, "Louis, inutile !\n");
+ return false;
+}
+
+void print_stats() {
+ map<int, int> nb_passages;
+ for (int a = 1; a <= n_aretes; a++)
+ nb_passages[passages[a]]++;
+ int m = nb_passages.rbegin()->first;
+ for (int p = 0; p <= m; p++)
+ fprintf(stderr, "%d route%s à %d passage%s\n", nb_passages[p], nb_passages[p] >= 2 ? "s" : "", p, p >= 2 ? "s" : "");
+}
+
+int main(int argc, char *argv[]) {
+ /*
+ Usage: a.out [INTERM_BASENAME [INIT_SOLUTION]]
+ INTERM_BASENAME: nom de base pour écrire les solutions intermédiaires
+ INIT_SOLUTION: nom du fichier de la solution initiale
+ */
+
+ signal(SIGINT, intHandler);
+
+ srand(time(NULL));
+ lecture_entree();
+ init_use();
+ init_nb_aretes();
+
+ if (argc > 2)
+ lire_solution(argv[2], _solution);
+ else {
+ init_solution(_solution);
+ // vraie_etoile(_solution);
+#ifdef CHOIZ
+ positions_choisies();
+ complete_all(_solution);
+#endif
+#ifdef GLOUTONNE
+ gloutonne();
+ tronque_solution(_solution);
+#endif
+ }
+
+ calc_glob();
+ affiche_score();
+ print_stats();
+
+ debug_sol();
+ prune_and_complete();
+ debug_sol();
+
+ bool ameliore = true;
+ bitset<8> prev_amel, amel;
+
+ fprintf(stderr, "C'est parti...\n");
+
+ if (argc > 1)
+ interm_basename = argv[1];
+
+while(1){
+
+int go=1;
+//
+ vector<int> time[8];
+ for(int i=0;i<8;i++){
+ int t=0;
+ time[i].push_back(0);
+ for(int j=0;j<_solution[i].size()-1;j++){
+ t+=cout[id_arete[make_pair(_solution[i][j],_solution[i][j+1])]];
+ time[i].push_back(t);
+//
+
+}}
+
+// for(int i=0;i<7 && go;i++){i=3;
+int i=0;int mmax=time[i][time[i].size()-1];int mmin=time[i][time[i].size()-1];
+ for(int x=0;x<8;x++){
+ int a=time[x][time[x].size()-1];
+ if(a>mmax){mmax=a;i=x;}
+ if(a<mmin){mmin=a;}
+ }
+ fprintf(stderr,"max,min %d %d\n",mmax,mmin);
+
+ if(mmax-mmin<1){affiche();return 0;}
+// if(mmax<53720){affiche();return 0;}
+
+ for(int j=0;j<8 && go ;j++){
+if(j==i)continue;
+
+ check_interrupt();
+ fprintf(stderr,"trying %d %d\n",i,j);
+ //foreach pair of cars
+
+ vector<int> comm_i;
+ vector<int> comm_j;
+
+ for(int xx=0;xx<_solution[i].size();xx++)
+ for(int yy=0;yy<_solution[j].size();yy++){
+ if(_solution[i][xx]==_solution[j][yy]){
+ comm_i.push_back(xx);comm_j.push_back(yy);
+ }
+ }
+ fprintf(stderr,"comm= %d %d\n",comm_i.size(),comm_j.size());
+
+ for(int ii1=0;ii1<comm_i.size() && go;ii1++){
+ for(int jj1=0;jj1<comm_j.size()&& go;jj1++){
+ int i1=comm_i[ii1];
+ int j1=comm_j[jj1];
+ if(_solution[i][i1]!=_solution[j][j1])continue;
+ for(int ii2=ii1+1;ii2<comm_i.size()&& go;ii2++){
+// fprintf(stderr,"... %d %d\n",ii1,jj1);
+ for(int jj2=jj1+1;jj2<comm_j.size()&& go;jj2++){
+ int i2=comm_i[ii2];
+ int j2=comm_j[jj2];
+ if(_solution[i][i2]!=_solution[j][j2])continue;
+ if(i2<i1 or j2<j1)continue;
+
+ int ti=time[i][time[i].size()-1];
+ int tj=time[j][time[j].size()-1];
+
+ int ti1=time[i][i1];
+ int ti2=time[i][i2];
+ int tj1=time[j][j1];
+ int tj2=time[j][j2];
+
+ //exchange paths ?
+ int ex=0;
+ if(ti<tj){
+ if(ti2-ti1 < tj2-tj1 && ti-(ti2-ti1)+(tj2-tj1)<tj && tj-(tj2-tj1)+(ti2-ti1)<tj ){ex=1;}
+ }else{
+ if(ti2-ti1 > tj2-tj1 && ti-(ti2-ti1)+(tj2-tj1)<ti && tj-(tj2-tj1)+(ti2-ti1)<ti ){ex=1;}
+ }
+ if(ex){
+ go=0;
+ fprintf(stderr,"would exchange %d between %d : %d %d (%d)and %d : %d %d(%d)\n",ti2-ti1-tj2+tj1,i,i1,i2,ti,j,j1,j2,tj);
+
+ //i1..i2 <-> j1..j2
+ vector<int> newi;
+ vector<int> newj;
+ for(int x=0;x<i1;x++)newi.push_back(_solution[i][x]);
+ for(int x=j1;x<j2;x++)newi.push_back(_solution[j][x]);
+ for(int x=i2;x<_solution[i].size();x++)newi.push_back(_solution[i][x]);
+
+ for(int x=0;x<j1;x++)newj.push_back(_solution[j][x]);
+ for(int x=i1;x<i2;x++)newj.push_back(_solution[i][x]);
+ for(int x=j2;x<_solution[j].size();x++)newj.push_back(_solution[j][x]);
+ _solution[i]=newi;
+ _solution[j]=newj;
+// affiche();return 0;
+// goto lab;
+ }
+
+ }}}}
+
+ }
+ if(go){break;}
+ //}
+}//while1
+lab:
+/* for (int git = 0; git < MAX_GIT; git++) {
+ ameliore = 1;
+ for (; ameliore; it++) {
+ debug_sol();
+
+ ameliore = 0;
+ prev_amel = amel;
+ #pragma omp parallel for
+ for (int v = 0; v < n_vehicules; v++)
+ ameliore |= amel[v] = ajoute_fin(v) || (!prev_amel[v] && ajoute_force(v));
+
+ check_interrupt();
+
+ debug_sol();
+ for (int v = 0; v < n_vehicules; v++)
+ ameliore |= amel[v] = amel[v] || modif(v);
+
+ ameliore |= prune_and_complete();
+ ameliore |= simplif_elarnon();
+
+ check_interrupt();
+ // if (!ameliore)
+ // ameliore = try_ameliore_louis();
+ }
+ MAX_ADD++;
+ MAX_RM+=2;
+ }*/
+
+ affiche();
+}
