ens-ulm-1

commit 6b5a3888b30edb830f98a3507057d3d5723e1da1
parent 6708cd26b3ca2478bef78a2227a1a69e42e7c45b
Author: Jachiet Louis <louis@jachiet.com>
Date:   Sat,  5 Apr 2014 14:45:28 +0200

Fix lectures.cpp

Diffstat:
contest/louis/algo.cpp
 | 
5
++++-
contest/louis/ameliore.cpp
 | 
71
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
contest/mc/lecture.cpp
 | 
5
+++--

3 files changed, 78 insertions(+), 3 deletions(-)
diff --git a/contest/louis/algo.cpp b/contest/louis/algo.cpp
@@ -1,4 +1,5 @@
 #include "louis.cpp"
+#include "ameliore.cpp"
 
 int main()
 {
@@ -21,5 +22,7 @@ int main()
 	  //	  fprintf(stderr,"%d %d %d\n",i,chem[i].back(),arrivee);
 	}
     }
-  affiche_sortie(chem);
+  ameliore_louis(chem);
+  //affiche_sortie(chem);
 }
+
diff --git a/contest/louis/ameliore.cpp b/contest/louis/ameliore.cpp
@@ -0,0 +1,71 @@
+class sol_louis
+{
+public:
+  vector<int> cibles[8] ;
+  int score ;
+
+  void note()
+  {
+    vector<int> n[8];
+    for(int i = 0 ; i < 8 ; i++ )
+      n[i] = complete(cibles[i]) ;
+    score = score_solution(n);
+  }
+  
+  sol_louis(vector<int> c[])
+  {
+    for(int i = 0 ; i < 8 ; i++ )
+      cibles[i] = c[i];
+    note();
+  }
+
+  sol_louis(sol_louis & o)
+  {
+    score = o.score ;
+    for(int i = 0 ; i < 8 ; i++ )
+      cibles[i] = o.cibles[i];
+  }
+  void update()
+  {
+    for(int i = 0 ; i < 8 ; i++ )
+      {
+	const int id = rand() % cibles[i].size();
+	const int n = cibles[i][id];
+	int v = adj[n][rand()%adj[n].size()] ;
+	cibles[i][id] = v;
+      }
+    note();
+  }
+};
+
+void ameliore_louis(vector<int> c[])
+{
+  sol_louis r_best(c) ;
+  double temp = 1000 * 1000 ;
+  const int nb_iter_max = 100 ;
+  //for( int i = 0 ; i < 10 ; i++ )
+    {
+      temp = 1000 * 1000  ;
+      sol_louis cur(c);
+      cur.update();
+      sol_louis best = cur ;
+      int nb_iter = 0;
+
+      while( nb_iter < nb_iter_max )
+	{
+	  fprintf(stderr,"cur_score %d[%d] | %d | %d \n",cur.score,cur.cibles[0].size(),r_best.score,score_solution(cur.cibles));
+	  cur = best;
+	  cur.update();
+
+	  if( cur.score > best.score || ((double(rand())/RAND_MAX) > (cur.score-best.score) * temp / (1000*1000) ))
+	    {
+	      best = cur ;
+	      if( best.score > r_best.score )
+		r_best = best;
+	    }
+	  temp *= 0.9935 ;
+	  nb_iter++;
+	}
+    }
+  affiche_sortie(r_best.cibles);
+}
diff --git a/contest/mc/lecture.cpp b/contest/mc/lecture.cpp
@@ -61,11 +61,12 @@ vector<int> evalue_solution(vector<int> trajectoires[]) {
       pair<int, int> p = make_pair(trajectoires[i][j], trajectoires[i][j+1]);
       int a = id_arete[p];
       if (!a) {
+	fprintf(stderr,"ERREUR !");
         resultat.clear();
         return resultat;
       }
       temps += cout[a];
-      if (temps > max_limit) {
+      if (temps > t_autorise) {
         // undo
         temps -= cout[a];
         break;
@@ -98,7 +99,7 @@ int tronque_solution(vector<int> trajectoires[], int max_limit) {
         return -1;
       }
       temps += cout[a];
-      if (temps > max_limit) {
+      if (temps > t_autorise) {
         // j'ai deborde, je cesse la
         trajectoires[i].resize(j);
         break;