ens-ulm-1

google hashcode 2014 source for team ens-ulm-1
git clone https://a3nm.net/git/ens-ulm-1/
Log | Files | Refs

ameliore.cpp (1761B)

      1 #include <assert.h>
      2 
      3 class sol_louis
      4 {
      5 public:
      6   vector<int> cibles[8] ;
      7   int score ;
      8 
      9   void note()
     10   {
     11     vector<int> n[8];
     12     for(int i = 0 ; i < 8 ; i++ )
     13       n[i] = complete(cibles[i]) ;
     14     score = score_solution(n);
     15   }
     16   
     17   sol_louis(vector<int> c[])
     18   {
     19     for(int i = 0 ; i < 8 ; i++ )
     20       {
     21 	cibles[i] = c[i];
     22 	for(int c = 0 ; c < 100 ; c++ )
     23 	  cibles[i].push_back(rand()%n_sommets);
     24       }
     25     note();
     26   }
     27 
     28   sol_louis(const sol_louis& o)
     29   {
     30     score = o.score ;
     31     for(int i = 0 ; i < 8 ; i++ )
     32       cibles[i] = o.cibles[i];
     33   }
     34   void update(int temps)
     35   {
     36     for(int i = 0 ; i < 8 ; i++ )
     37       for(int c = 0 ; c <= rand()%(temps+1) ; c++ )
     38 	{
     39 	  const int id = (rand() % (cibles[i].size()-1))+1;
     40 	  if(rand()%(temps+1)==1)
     41 	    cibles[i][id] = rand()%cibles[i].size();
     42 	  else
     43 	    {
     44 	      const int n = cibles[i][id];
     45 	      int v = adj[n][rand()%adj[n].size()] ;
     46 	      cibles[i][id] = v;
     47 	    }
     48 	}
     49     note();
     50   }
     51 };
     52 
     53 void ameliore_louis(vector<int> c[])
     54 {
     55   sol_louis r_best(c) ;
     56   double temp = 1000 * 1000 ;
     57   const int nb_iter_max = 2*1000 ;
     58   //for( int i = 0 ; i < 10 ; i++ )
     59     {
     60       temp = 20  ;
     61       sol_louis cur(c);
     62       cur.update(20);
     63       sol_louis best = cur ;
     64       int nb_iter = 0;
     65 
     66       while( nb_iter < nb_iter_max )
     67 	{
     68 	  if(nb_iter %200 == 0)
     69 	    fprintf(stderr,"cur_score %d[%zu] | %d | %lf \n",cur.score,cur.cibles[0].size(),r_best.score,temp);
     70 	  cur = best;
     71 	  cur.update(temp);
     72 
     73 	  if( cur.score > best.score)
     74 	    {
     75 	      best = cur ;
     76 	      if( best.score > r_best.score )
     77 		r_best = best;
     78 	    }
     79 	  temp *= 0.9998 ;
     80 	  nb_iter++;
     81 	}
     82     }
     83     vector<int> r[8];
     84     for(int i = 0 ; i < 8 ; i++ )
     85       r[i] = complete(r_best.cibles[i]);
     86     tronque_solution(r);
     87     //affiche_sortie(r);
     88 }