連続ですみません(´; ω ;｀) コードの添削お願いします!!

mikamika33 · #1

さきほど質問させて頂いたのに連続ですみませんが、巡回セールス問題を遺伝的アルゴリズムを使って解こうと
していて、一通り完成させたのですが、なんだか処理に時間がかかってしまうときと、さらっと終わる時があって、、、
私が書いたコードのどこが悪いか、こういう風に書いた方がいいよ！みたいなアドバイスを頂けたら嬉しいです！！
よろしくおねがいします！！(>_<)

コード:


#include <iostream>
#include <math.h>

#define SIZE 38
#define NUM_OF_GENES 12
//店舗のデータを格納するオブジェクトのクラス定義
class shops
{
private:
    double x;
    double y;
    char name[40];
public:
    void set_x(double x);
    void set_y(double y);
    void set_name(char *name);
    double get_x();
    double get_y();
    char* get_name();
};

//shopsクラスのメソッド定義
void shops::set_x(double _x) {
    x = _x;
}
void shops::set_y(double _y) {
    y = _y;
}
void shops::set_name(char *_name) {
    strcpy(name, _name);
}
double shops::get_x() {
    return x;
}
double shops::get_y() {
    return y;
}
char* shops::get_name() {
    return name;
}

//各店舗のデータを格納するshopsクラスのインスタンス生成
shops shop[SIZE];


////ランダムに巡回ルートを作成する関数
void makeRoute(int *gene);
//２店舗間の距離を返す関数
float getDistance(shops *shop1, shops *shop2);
//巡回ルートの合計距離を返す関数
float getTotalDistance(int *gene);
//遺伝子同士を交配する関数
void getNextGeneration(int (*genes)[SIZE]);

int main(void)
{
    printf("ラーメン二郎全店を巡回する最短ルートを探索しています...\n");
    //二郎全店舗名を入力する配列
    char names[SIZE][40] = {"三田本店", "目黒店", "品川店", "新橋店", "神田神保町店", "亀戸店", "環七一之江店", "小岩店", "千住大橋駅前店", "赤羽店", "西台駅前店", "桜台駅前店", "荻窪店", "環七新代田店", "上野毛店", "新宿小滝橋通り店", "歌舞伎町店", "池袋東口店", "仙川店", "ひばりヶ丘駅前店", "新小金井街道店", "府中店", "立川店", "八王子野猿街道店２", "めじろ台法政大学前店", "京急川崎店", "鶴見店", "横浜関内店", "中山駅前店", "相模大野店", "湘南藤沢店", "松戸駅前店", "京成大久保店", "茨城守谷店", "大宮店", "栃木街道店", "仙台店", "札幌店"};
    //各店舗のx座標
    double cordinates_x[SIZE] = {35.6480801, 35.6341918, 35.6238941, 35.6656255, 35.6963775, 35.7019335, 35.6840881, 35.7349536, 35.7425936, 35.7798005, 35.7868841, 35.7388065, 35.7035931, 35.6619732, 35.612421, 35.6964591, 35.6957565, 35.7282785, 35.6617852, 35.7500101, 35.7084359, 35.6720481, 35.6965106, 35.6295148, 35.6294833, 35.5349024, 35.4970884, 35.4421385, 35.5130707, 35.5299308, 35.3429086, 35.7860021, 35.6914847, 35.9240496, 35.9034403, 36.4236329, 38.26171009999999, 43.0673949};
    //各店舗のy座標
    double cordinates_y[SIZE] = {139.74161430000004, 139.70705120000002, 139.74299569999994, 139.75057130000005, 139.75646989999996, 139.82667820000006, 139.88195110000004, 139.88001039999995, 139.7970037, 139.72084730000006, 139.6748096, 139.66185940000003, 139.62628870000003, 139.66042670000002, 139.63897769999994, 139.69845810000004, 139.70192450000002, 139.7138357, 139.58388289999994, 139.54379649999998, 139.4962084, 139.47725300000002, 139.40952679999998, 139.40136670000004, 139.31035739999993, 139.705734, 139.66126680000002, 139.63070389999996, 139.53857500000004, 139.4329335, 139.48232830000006, 139.8994156, 140.04961500000002, 140.00057889999994, 139.62628459999996, 139.7956385, 140.86612300000002, 141.34382140000002};
    //店舗データの設定
    int i, j;
    for (i = 0; i < SIZE; i++) {
        shop[i].set_x(cordinates_x[i]);
        shop[i].set_y(cordinates_y[i]);
        shop[i].set_name(names[i]);
    }
    //巡回ルートのデータを持つ遺伝子の宣言
    int genes[NUM_OF_GENES][SIZE];
    //乱数の種を初期化
    srand((unsigned)time(NULL));
    //geneに巡回ルートを組み込む
    for (i = 0; i < NUM_OF_GENES; i++) {
        makeRoute(genes[i]);
    }
    for (i = 0; i < 20; i++) {
        getNextGeneration(genes);
    }
    //それぞれのルートの合計距離のソート
    int distance[12]; //巡回ルートの合計距離を記録
    int rank[SIZE]; //ソート結果を記録
    for (i = 0; i < NUM_OF_GENES; i++) {
        rank[i] = i;
    }
    for (i = 0; i < NUM_OF_GENES; i++) {
        distance[i] = getTotalDistance(genes[i]);
    }
    int tmp;
    for (i = 0; i < NUM_OF_GENES; i++) {
        for (j = i + 1; j < NUM_OF_GENES - 1; j++) {
            if (distance[i] < distance[j]) {
                tmp = rank[i];
                rank[i] = rank[j];
                rank[j] = tmp;
            }
        }
    }
    printf("結果は以下のようになりました\n");
    for (i = 0; i < SIZE; i++) {
        printf("%d.%s\n", i + 1, shop[genes[rank[0]][i]].get_name());
    }
    
    return 0;
}

//ランダムに巡回ルートを作成する関数の定義
void makeRoute(int *gene) {
    //配列の初期化
    int i;
    for (i = 0; i < SIZE; i++){
        gene[i] = i;
    }
    //シャッフルする
    int tmp;
    int num;
    for (i = 0; i < 100; i++) {
        num = rand() % SIZE;
        tmp = gene[num];
        if (num == SIZE - 1) {
            gene[num] = gene[0];
            gene[0] = tmp;
        } else {
            gene[num] = gene[num + 1];
            gene[num + 1] = tmp;
        }
    }
}
//２店舗間の距離を返す関数の定義
float getDistance(shops shop1, shops shop2) {
    return sqrt(pow(shop1.get_x() - shop2.get_x(), 2) + pow(shop1.get_y() - shop2.get_y(), 2));
};

//巡回ルートの合計距離を返す関数の定義
float getTotalDistance(int* gene) {
    float result;
    result = 0;
    int i;
    for (i = 0; i < SIZE - 2; i++) {
        result += getDistance(shop[gene[i]], shop[gene[i+1]]);
    }
    return result;
}

//遺伝子同士を交配する関数
void getNextGeneration(int (*genes)[SIZE]) {
    int i, j;
    //それぞれのルートの合計距離のソート
    int distance[12]; //巡回ルートの合計距離を記録
    int rank[SIZE]; //ソート結果を記録
    for (i = 0; i < NUM_OF_GENES; i++) {
        rank[i] = i;
    }
    for (i = 0; i < NUM_OF_GENES; i++) {
        distance[i] = getTotalDistance(genes[i]);
    }
    int tmp;
    for (i = 0; i < NUM_OF_GENES; i++) {
        for (j = i + 1; j < NUM_OF_GENES - 1; j++) {
            if (distance[i] < distance[j]) {
                tmp = rank[i];
                rank[i] = rank[j];
                rank[j] = tmp;
            }
        }
    }
    
    //親を決める
    int winners[21];
    for (i = 0; i < 21; i++) {
        if (i < 6) {
            winners[i] = rank[0];
        } else if (i < 11) {
            winners[i] = rank[1];
        } else if (i < 15) {
            winners[i] = rank[2];
        } else if (i < 18) {
            winners[i] = rank[3];
        } else if (i < 20) {
            winners[i] = rank[4];
        } else {
            winners[i] = rank[5];
        }
    }
    int a, b;
    int flag;
    int parents[3][2];
    for (i = 0; i < 3; i++) {
        flag = 1;
        while (flag) {
            a = rand() % 21;
            b = rand() % 21;
            if (winners[a] == winners[b]) {
                continue;
            } else {
                parents[i][0] = winners[a];
                parents[i][1] = winners[b];
                flag = !flag;
            }
        }
    }
    //親を交配させる
    for (i = 0; i < NUM_OF_GENES; i++) {
        if (rand() % 2) {
            genes[NUM_OF_GENES][i] = genes[parents[0][0]][i];
            genes[NUM_OF_GENES - 1][i] = genes[parents[0][1]][i];
        } else {
            genes[NUM_OF_GENES][i] = genes[parents[0][1]][i];
            genes[NUM_OF_GENES - 1][i] = genes[parents[0][0]][i];
        }
    }
    for (i = 0; i < NUM_OF_GENES; i++) {
        if (rand() % 2) {
            genes[NUM_OF_GENES - 2][i] = genes[parents[1][0]][i];
            genes[NUM_OF_GENES - 3][i] = genes[parents[1][1]][i];
        } else {
            genes[NUM_OF_GENES - 2][i] = genes[parents[1][1]][i];
            genes[NUM_OF_GENES - 3][i] = genes[parents[1][0]][i];
        }
    }
    for (i = 0; i < NUM_OF_GENES; i++) {
        if (rand() % 2) {
            genes[NUM_OF_GENES - 4][i] = genes[parents[2][0]][i];
            genes[NUM_OF_GENES - 5][i] = genes[parents[2][1]][i];
        } else {
            genes[NUM_OF_GENES - 4][i] = genes[parents[2][1]][i];
            genes[NUM_OF_GENES - 5][i] = genes[parents[2][0]][i];
        }
    }
}

たいちう · #2

srand(0); とか、srand(1); とか、適当な値を直接入力して試してください。
同じ数値だと同じ実行結果になるはずですので、処理の早い時と遅い時を見つけて下さい。
これでデバッグがしやすくなると思います。

mikamika23 · #3

>たいちうさん
根本的なとこミスってました！ありがとうございます！！

連続ですみません(´; ω ;｀) コードの添削お願いします!!

連続ですみません(´; ω ;｀) コードの添削お願いします!!

Re: 連続ですみません(´; ω ;｀) コードの添削お願いします!!

Re: 連続ですみません(´; ω ;｀) コードの添削お願いします!!

		8月 2019
日	月	火	水	木	金	土
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31