ens-ulm-1

commit b433a5cd7aff34501c60022b256e2722634d9e47
parent 7b152fea05f15aaffea1e46f89b17f6bd53ebc29
Author: Marc Jeanmougin <marc@jeanmougin.fr>
Date:   Sat,  5 Apr 2014 17:31:14 +0200

Merge branch 'master' of ssh://gitorious.org/ens-ulm-1/ens-ulm-1

Diffstat:
contest/mc/explore.cpp
 | 
110
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 110 insertions(+), 0 deletions(-)
diff --git a/contest/mc/explore.cpp b/contest/mc/explore.cpp
@@ -0,0 +1,110 @@
+#include <cstdio>
+#include <algorithm>
+#include <vector>
+#include <queue>
+using namespace std;
+#include "../louis/louis.cpp"
+#include "../louis/ameliore.cpp"
+
+#define DEPTH 10
+// now better than never
+#define DAMPING 1.1
+
+// TODO MAUVAISE PONDERATION
+
+int min_vehicle(int temps[]) {
+  int earliest_val = t_autorise+1, earliest_pos = 0;
+  for (int i=0; i<8; i++)
+    if(temps[i] < earliest_val) {
+      earliest_val = temps[i];
+      earliest_pos = i;
+    }
+  return earliest_pos;
+}
+
+double explore(int depth, bool aretes[], int pos[], int temps[], int v) {
+  //int v = min_vehicle(temps);
+  int position = pos[v];
+  double best_score = -1;
+  int best_pos = -1;
+
+  if (depth == 0)
+    return 0;
+
+  for (unsigned int i=0; i < adj[pos[v]].size(); i++) {
+    //printf("(%d) consider option: move car %d to %d\n", depth, v, adj[pos[v]][i]);
+    int aid = id_arete[make_pair(position, adj[pos[v]][i])];
+    int opos = pos[v];
+    bool visited = aretes[aid];
+    double score = 0;
+    if (!visited) {
+      //score = ((double) longueur[aid])/cout[aid];
+      score = ((double) longueur[aid]);
+    }
+    // modify
+    pos[v] = adj[pos[v]][i];
+    temps[v] += cout[aid];
+    aretes[aid] = true;
+    score += explore(depth-1, aretes, pos, temps, v)/DAMPING;
+    aretes[aid] = visited;
+    temps[v] -= cout[aid];
+    pos[v] = opos;
+    if (score > best_score) {
+      //printf("(%d) new record: moving car %d to %d achieves %lf beating %lf\n", depth, v, adj[pos[v]][i], score, best_score);
+      best_score = score;
+      best_pos = adj[pos[v]][i];
+    }
+  }
+  
+  //printf("(%d) best motion for car %d is to go from %d to %d achieving %lf\n", depth, v, pos[v], best_pos, best_score);
+  if (depth == DEPTH) {
+    return best_pos;
+  }
+  return best_score;
+}
+
+void glouton(vector<int> moves[]) {
+  int temps[8];
+  int pos[8];
+  int score = 0;
+  bool aretes[N_ARETES_MAJ];
+  for (int i=0; i<8; i++) {
+    pos[i] = s_depart;
+    temps[i] = 0;
+  }
+  for (int i=0; i<=n_aretes; i++)
+    aretes[i] = false;
+  int best_pos;
+  int first_car;
+  for (int i=0; i<8; i++)
+    moves[i].push_back(s_depart);
+
+  while(temps[first_car = min_vehicle(temps)] <= t_autorise) {
+    best_pos = explore(DEPTH, aretes, pos, temps, first_car);
+    //printf("decide to move car %d to %d\n", first_car, best_pos);
+    // move the first car to best_pos
+    int aid = id_arete[make_pair(pos[first_car], best_pos)];
+    if(!aid) {
+      printf("WTF! no edge from %d to %d\n", pos[first_car], best_pos);
+      return;
+    }
+    moves[first_car].push_back(best_pos);
+    temps[first_car] += cout[aid];
+    //printf("car %d has now time %d\n", first_car, temps[first_car]);
+    pos[first_car] = best_pos;
+    score += (aretes[aid]?0:longueur[aid]);
+    aretes[aid] = true;
+    //printf("score now %d\n", score);
+  }
+}
+
+int main() {
+  lecture_entree();
+  init_use();
+  vector<int> moves[8];
+  glouton(moves);
+  tronque_solution(moves, t_autorise);
+  printf("FINAL: %d\n", score_solution(moves));
+  affiche_sortie(moves);
+}
+