Member 13573290 Ответов: 1

У меня есть проблема с построением расписания


#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 выходят одинаковыми

1 Ответов

Рейтинг:
0

KarstenK

С помощью Visual Studio вы можете Установка точки останова данных. Это поможет вам отладить ваш код.

Я предполагаю, что это какой-то массив вне границ или неправильное использование указателя. Проверьте размеры вашего массива и доступ к полю. Эти ошибки действительно трудно найти, чтобы эта техника должна вам помочь. Так что учитесь этому, чтобы развить свои навыки.

Дополнительно: рассмотрите возможность более текстового вывода для помощи пользователю и использования классов для лучшего проектирования и отладки. На данный момент ваш код немного запутан и труден для понимания. Это очень часто является причиной ошибок.

Пожалуйста, пишите также комментарии на английском языке. ;-)