explore.cpp (3230B)
1 #include <cstdio> 2 #include <algorithm> 3 #include <vector> 4 #include <queue> 5 using namespace std; 6 #include "../louis/louis.cpp" 7 #include "../louis/ameliore.cpp" 8 9 #define ULM 8254 10 #define DEPTH 10 11 // now better than never 12 #define DAMPING 1.1 13 14 // TODO MAUVAISE PONDERATION 15 16 int min_vehicle(int temps[]) { 17 int earliest_val = t_autorise+1, earliest_pos = 0; 18 for (int i=0; i<8; i++) 19 if(temps[i] < earliest_val) { 20 earliest_val = temps[i]; 21 earliest_pos = i; 22 } 23 return earliest_pos; 24 } 25 26 double explore(int depth, bool aretes[], int pos[], int temps[], int v) { 27 //int v = min_vehicle(temps); 28 int position = pos[v]; 29 double best_score = -1; 30 int best_pos = -1; 31 32 if (depth == 0) 33 return 0; 34 35 for (unsigned int i=0; i < adj[pos[v]].size(); i++) { 36 //printf("(%d) consider option: move car %d to %d\n", depth, v, adj[pos[v]][i]); 37 int aid = id_arete[make_pair(position, adj[pos[v]][i])]; 38 int opos = pos[v]; 39 bool visited = aretes[aid]; 40 double score = 0; 41 if (!visited) { 42 //score = ((double) longueur[aid])/cout[aid]; 43 score = ((double) longueur[aid]); 44 } 45 // modify 46 pos[v] = adj[pos[v]][i]; 47 temps[v] += cout[aid]; 48 aretes[aid] = true; 49 score += explore(depth-1, aretes, pos, temps, v)/DAMPING; 50 aretes[aid] = visited; 51 temps[v] -= cout[aid]; 52 pos[v] = opos; 53 if (score > best_score) { 54 //printf("(%d) new record: moving car %d to %d achieves %lf beating %lf\n", depth, v, adj[pos[v]][i], score, best_score); 55 best_score = score; 56 best_pos = adj[pos[v]][i]; 57 } 58 } 59 60 //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); 61 if (depth == DEPTH) { 62 return best_pos; 63 } 64 return best_score; 65 } 66 67 void glouton(vector<int> moves[]) { 68 int temps[8]; 69 int pos[8]; 70 int score = 0; 71 bool aretes[N_ARETES_MAJ]; 72 for (int i=0; i<8; i++) { 73 pos[i] = s_depart; 74 temps[i] = 0; 75 } 76 for (int i=0; i<=n_aretes; i++) 77 aretes[i] = false; 78 int best_pos; 79 int first_car; 80 for (int i=0; i<8; i++) { 81 moves[i].push_back(s_depart); 82 if (i < 4) 83 moves[i].push_back(ULM); 84 //moves[i].push_back(rand()%n_sommets); 85 } 86 // goto_etoile(moves); 87 for (int i=0; i<8; i++) { 88 moves[i] = complete(moves[i]); 89 pos[i] = moves[i].back(); 90 } 91 92 93 while(temps[first_car = min_vehicle(temps)] <= t_autorise) { 94 best_pos = explore(DEPTH, aretes, pos, temps, first_car); 95 fprintf(stderr, "decide to move car %d to %d\n", first_car, best_pos); 96 // move the first car to best_pos 97 int aid = id_arete[make_pair(pos[first_car], best_pos)]; 98 if(!aid) { 99 printf("WTF! no edge from %d to %d\n", pos[first_car], best_pos); 100 return; 101 } 102 moves[first_car].push_back(best_pos); 103 temps[first_car] += cout[aid]; 104 //printf("car %d has now time %d\n", first_car, temps[first_car]); 105 pos[first_car] = best_pos; 106 score += (aretes[aid]?0:longueur[aid]); 107 aretes[aid] = true; 108 //printf("score now %d\n", score); 109 } 110 } 111 112 int main() { 113 lecture_entree(); 114 init_use(); 115 vector<int> moves[8]; 116 glouton(moves); 117 tronque_solution(moves, t_autorise); 118 fprintf(stderr, "FINAL: %d\n", score_solution(moves)); 119 affiche_sortie(moves); 120 } 121