У меня есть проблема с построением расписания
#include <bits/stdc++.h> #define MAX_N 110 // 최대 장소 수 #define MAX_C 7 // 최대 #define MAX_D 7 // 최대 요일 수 #define MAX_P 10 // 최대 수업 시수 #define CN 5 // 반 수 (1반 2반 3반 4반 5반) #define DN 5 // 요일 수 (월화수목금) #define INF 1234567890 // 큰 수 (무한대로 생각) #define CAFETERIA 8 // 급식실 번호 (4교시 수업 -> 급식실 -> 5교시 수업) using namespace std; FILE *fi = fopen("input.txt", "r"); FILE *fo = fopen("output.txt", "w"); typedef pair<int, int> pii; struct timetable { int tt[MAX_C][MAX_P]; // 요일, 교시 time_table int sum[MAX_D]; // 요일별 이동거리 합 int total_dist; } team[MAX_C], team2[MAX_C]; // team 1개 = 반 1개 float avg[MAX_D]; // 요일별 반들의 이동거리합 평균 float avg2[MAX_D]; // 요일별 반들의 이동거리합 평균 int lessonhour[MAX_D]={0, 7, 6, 6, 6, 7, 0}; // 요일별 몇교시까지 있는지 int N, M; //vertex N, edge M vector<pii> vt[MAX_N]; int dist[MAX_N]; int graph[MAX_N][MAX_N]; void input() { fscanf(fi, "%d %d", &N, &M); for(int i=1;i<=M;i++) { int u, v, w; fscanf(fi, "%d %d %d", &u, &v, &w); vt[u].push_back(make_pair(w, v)); vt[v].push_back(make_pair(w, u)); } for(int r_class=1;r_class<=CN;r_class++) { for(int r_day=1;r_day<=DN;r_day++) { for(int r_period=1;r_period<=lessonhour[r_day];r_period++) { fscanf(fi, "%d", &team[r_class].tt[r_day][r_period]); } } } } void init_dist() { for(int i=1;i<=N;i++) { dist[i] = INF; } } int dijkstra(int s, int e) { init_dist(); dist[s] = 0; priority_queue<pii, vector<pii>, greater<pii> > pq; pq.push(make_pair(0, s)); while(!pq.empty()) { pii tmp = pq.top(); pq.pop(); int here = tmp.second; for(int i=0;i<vt[here].size();i++) { int add_dist = vt[here][i].first; int there = vt[here][i].second; if(dist[here]+add_dist < dist[there]) { dist[there] = dist[here]+add_dist; pq.push(make_pair(dist[there], there)); } } } return dist[e]; } void min_dist() { for(int s=1;s<=N;s++) { for(int e=s+1;e<=N;e++) { graph[s][e] = graph[e][s] = dijkstra(s, e); } } /* int T; scanf("%d", &T); while(T--) { int u, v; scanf("%d %d", &u, &v); printf("%d\n", graph[u][v]); } /*/ } void update() { for(int i=1;i<=CN;i++) { // 반별로 요일별 이동거리 합 구하기 team[i].total_dist = 0; for(int day=1;day<=DN;day++) { //요일 team[i].sum[day] = 0; for(int lecture=1;lecture<=lessonhour[day];lecture++) { int pre = team[i].tt[day][lecture-1]; int now = team[i].tt[day][lecture]; team[i].sum[day] += graph[pre][now]; } int p4 = team[i].tt[day][4]; // 4교시 수업 int p5 = team[i].tt[day][5]; // 5교시 수업 team[i].sum[day] += (graph[p4][CAFETERIA] + graph[CAFETERIA][p5]); // 4교시->급식->5교시 avg[day] += team[i].sum[day]; team[i].total_dist += team[i].sum[day]; } } for(int i=1;i<=DN;i++) { avg[i] /= CN; } } void update2() { for(int i=1;i<=CN;i++) { // 반별로 요일별 이동거리 합 구하기 team2[i].total_dist = 0; for(int day=1;day<=DN;day++) { //요일 team2[i].sum[day] = 0; for(int lecture=1;lecture<=lessonhour[day];lecture++) { int pre = team2[i].tt[day][lecture-1]; int now = team2[i].tt[day][lecture]; team2[i].sum[day] += graph[pre][now]; } int p4 = team2[i].tt[day][4]; // 4교시 수업 int p5 = team2[i].tt[day][5]; // 5교시 수업 team2[i].sum[day] += (graph[p4][CAFETERIA] + graph[CAFETERIA][p5]); // 4교시->급식->5교시 avg2[day] += team2[i].sum[day]; team2[i].total_dist += team2[i].sum[day]; } } for(int i=1;i<=DN;i++) { avg2[i] /= CN; } } float standard_deviation() { update(); float week_avg=0; for(int i=1;i<=DN;i++) { week_avg += team[i].total_dist; } week_avg /= DN; float ret=0; for(int i=1;i<=CN;i++) { ret += (team[i].total_dist-week_avg)*(team[i].total_dist-week_avg); } ret /= CN; // 분산 ret = sqrt(ret); // 표준편차 return ret; } bool possible(int r_class) { // 새로 만든 시간표가 다른 반과 겹치는 일은 없는지 for(int i=1;i<=CN;i++) { if(i==r_class) continue; for(int j=1;j<=DN;j++) { for(int k=1;k<=lessonhour[j];k++) { if(team2[r_class].tt[j][k] == team2[i].tt[j][k]) { return false; } } } } return true; } void monte_carlo() { int cnt=0; for(;;) { cnt++; srand(time(NULL)); int r_class = rand()%MAX_C+1; srand(time(NULL)); int r_day1 = rand()%MAX_D+1; srand(time(NULL)); int r_day2 = rand()%MAX_D+1; srand(time(NULL)); int r_p1 = rand()%lessonhour[r_day1]+1; srand(time(NULL)); int r_p2 = rand()%lessonhour[r_day2]+1; swap(team2[r_class].tt[r_day1][r_p1], team2[r_class].tt[r_day2][r_p2]); puts("possible?"); if(possible(r_class)) { puts("possible!"); break; } else { swap(team2[r_class].tt[r_day1][r_p1], team2[r_class].tt[r_day2][r_p2]); } } } float standard_deviation2() { puts("s1"); for(int i=1;i<=CN;i++) { team2[i] = team[i]; } puts("s2"); monte_carlo(); // change 2 periods puts("s3"); update2(); puts("s4"); float week_avg=0; for(int i=1;i<=DN;i++) { week_avg += team2[i].total_dist; } week_avg /= DN; puts("s5"); float ret=0; for(int i=1;i<=CN;i++) { ret += (team2[i].total_dist-week_avg)*(team2[i].total_dist-week_avg); } ret /= CN; // 분산 ret = sqrt(ret); // 표준편차 puts("fin"); return ret; } void change_status() { for(int i=1;i<=CN;i++) { team[i] = team2[i]; } } /* p = e^((E1-E)/(k*T)) */ float K=0; // 볼츠만 상수 float dT=0.95; // 온도 감률 void simulated_annealing() { float T, Tc; T = 1; Tc = 0.00001; while(T>Tc) { // Tc : 임계온도 printf("%f\n", T); float E1 = standard_deviation(); // 현재 상태의 에너지 printf("E1=%f\n", E1); float E2 = standard_deviation2(); // 새로운 상태의 에너지 printf("E2=%f\n", E2); float p = exp((E1-E2)/(K*T)); srand(time(NULL)); float r = rand()%1000+1; r = r/1000; // r = 0~1 사이 난수 if(p>r) { change_status(); } T *= dT; } } int main() { input(); puts("input"); min_dist(); puts("min_dist"); printf("initial standard_deviation = %f\n", standard_deviation()); simulated_annealing(); puts("simulated_annealing"); printf("standard_deviation = %f\n", standard_deviation()); for(int p_class=1;p_class<=CN;p_class++) { printf("class %d : total_distance %d\n", p_class, team[p_class].total_dist); for(int p_period=1;p_period<=7;p_period++) { for(int p_day=1;p_day<=DN;p_day++) { printf("%d ", team[p_class].tt[p_day][p_period]); } printf("\n"); } printf("\n"); } return 0; }
с этим кодом E1 и E2 выходит то же самое.
Я не могу найти где переодеться
пожалуйста помочь
Что я уже пробовал:
мы смотрели на код в течение недели, но мы не могли решить его.
Другие работают хорошо, но проблема в том, что E1 и E2 выходят одинаковыми