巡回セールスマン問題

概要

組み合わせ最適化問題の一つである、巡回セールスマン問題を①ランダム法②山登り法③シミュレーティド・アニーリング法で解くようなプログラムである。
疑似乱数の発生にはメルセンヌツイスターを用いている。
tspsolve.cを実行するディレクトリと同じディレクトリに実行したいTSP問題を置いておく。以下からダウンロードできる。
http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/
以下のように打ち込みコンパイルする
gcc -o tspsolve tspsolve.c -lm
以下のように打ち込むと実行できる
./tspsolve eil51.tsp random
eil51.tspは任意のtsp問題のファイル名にし、randomはrandom、hill-climbing、SA、ASCで任意の方法が選択できる。

tspsolve.c

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <math.h>
# include <time.h>

# define A 3
//RANDOMでランダム交換、2OPTで2-opt近傍を選択できる
# define NEIGHBOR_MODE "2OPT"

//メルセンヌ・ツイスター
//genrand()で乱数を発生できる

/* Period parameters */  
# define N 624
# define M 397
# define MATRIX_A 0x9908b0df   /* constant vector a */
# define UPPER_MASK 0x80000000 /* most significant w-r bits */
# define LOWER_MASK 0x7fffffff /* least significant r bits */

/* Tempering parameters */   
# define TEMPERING_MASK_B 0x9d2c5680
# define TEMPERING_MASK_C 0xefc60000
# define TEMPERING_SHIFT_U(y)  (y >> 11)
# define TEMPERING_SHIFT_S(y)  (y << 7)
# define TEMPERING_SHIFT_T(y)  (y << 15)
# define TEMPERING_SHIFT_L(y)  (y >> 18)

static unsigned long mt[N]; /* the array for the state vector  */
static int mti=N+1; /* mti==N+1 means mt[N] is not initialized */

/* initializing the array with a NONZERO seed */
void
sgenrand(seed)
    unsigned long seed;	
{
    /* setting initial seeds to mt[N] using         */
    /* the generator Line 25 of Table 1 in          */
    /* [KNUTH 1981, The Art of Computer Programming */
    /*    Vol. 2 (2nd Ed.), pp102]                  */
    mt[0]= seed & 0xffffffff;
    for (mti=1; mti<N; mti++)
        mt[mti] = (69069 * mt[mti-1]) & 0xffffffff;
}

double /* generating reals */
/* unsigned long */ /* for integer generation */
genrand()
{
    unsigned long y;
    static unsigned long mag01[2]={0x0, MATRIX_A};
    /* mag01[x] = x * MATRIX_A  for x=0,1 */

    if (mti >= N) { /* generate N words at one time */
        int kk;

        if (mti == N+1)   /* if sgenrand() has not been called, */
            sgenrand(4357); /* a default initial seed is used   */

        for (kk=0;kk<N-M;kk++) {
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
            mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1];
        }
        for (;kk<N-1;kk++) {
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
            mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1];
        }
        y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
        mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1];

        mti = 0;
    }
  
    y = mt[mti++];
    y ^= TEMPERING_SHIFT_U(y);
    y ^= TEMPERING_SHIFT_S(y) & TEMPERING_MASK_B;
    y ^= TEMPERING_SHIFT_T(y) & TEMPERING_MASK_C;
    y ^= TEMPERING_SHIFT_L(y);

    return ( (double)y * 2.3283064370807974e-10 ); /* reals */
    /* return y; */ /* for integer generation */
}

//ランダム解の生成
int makecoord(int n, int *bestcost, int **cost, int **besttour){
    int tmp, tmpcost=0;
    int check[n];
    int randtour[n];

    //0は未訪問、1は訪問済みとしてcheckの初期化
    for(int i=0; i<n; i++){
        check[i] = 0;
    }

    for(int i=0; i<n; i++){
        //0~50までの乱数を発生
        tmp = (int)(genrand()*51);
        //未訪問の行き先に出会えるまでtmpを更新
        while(check[tmp] != 0){
            tmp = (int)(genrand()*51);
        }
        randtour[i] = tmp;
        check[tmp] = 1;
    }

    //コストの計算
    for(int i=0; i<n-1; i++){
        tmpcost += cost[randtour[i]][randtour[i+1]];
    }
    tmpcost += cost[randtour[n-1]][randtour[0]];

    //コピー
    for(int i=0; i<n; i++){
        *besttour[i] = randtour[i];
    }
    *bestcost = tmpcost;

    //探索路の表示
    //for(int i=0; i<n; i++){
    //    printf("%d ", *besttour[i]);
    //}
    //printf("\n");
    //printf("%d\n", *bestcost);

}

//単純巡回路のコスト計算と表示
int costASC(int n, int **cost){
    int ASC=0;

    for(int i=0; i<n-1; i++){
        ASC += cost[i][i+1];
    }

    ASC += cost[n-1][0];

    printf("%d\n", ASC);
}


//ランダム巡回路の作成と比較
int sortRAND(int n, int *bestcost, int **cost, int **besttour){
    int tmp, tmpcost=0;
    int check[n];
    int randtour[n];

    //0は未訪問、1は訪問済みとしてcheckの初期化
    for(int i=0; i<n; i++){
        check[i] = 0;
    }

    for(int i=0; i<n; i++){
        //0~50までの乱数を発生
        tmp = (int)(genrand()*51);
        //未訪問の行き先に出会えるまでtmpを更新
        while(check[tmp] != 0){
            tmp = (int)(genrand()*51);
        }
        randtour[i] = tmp;
        check[tmp] = 1;
    }

    //探索路の表示
    //for(int i=0; i<n; i++){
    //    printf("%d ", randtour[i]);
    //}
    //printf("\n");

    //コストの計算
    for(int i=0; i<n-1; i++){
        tmpcost += cost[randtour[i]][randtour[i+1]];
    }
    tmpcost += cost[randtour[n-1]][randtour[0]];
    //printf("%d\n", tmpcost);

    //bestcostとbesttourの更新
    if(*bestcost > tmpcost){
        *bestcost = tmpcost;
        for(int i=0; i<n; i++){
            *besttour[i] = randtour[i];
        }
    }
}


//ランダム巡回路のファイル出力
int randplot(int t, int **coord, int **besttour, int n, int *bestcost, double rtime){
    char filename[30];
    FILE *fp;
    int i;
    int iteration = t+1;

    //追記モードのaを選択している    
    for(i=1; i<iteration; i++){
        if(i%t == 0){
            sprintf(filename, "random-%d.dat", i);
            if((fp=fopen(filename, "a")) == NULL){
                printf("File Open Error: %s\n", filename);
                exit(1);
            }
        }
    }

    //ファイルへの書き込み
    fprintf(fp, "#問題:eil51.tsp\n");
    fprintf(fp, "#解放:random\n");
    fprintf(fp, "#繰り返し回数:%d\n", t);
    fprintf(fp, "#暫定解:%d\n", *bestcost);
    fprintf(fp, "#実行時間:%lf\n", rtime);
    for(i=0; i<n; i++){
        fprintf(fp, "%d %d\n", coord[*besttour[i]][1], coord[*besttour[i]][2]);
    }
    fprintf(fp, "%d %d\n", coord[*besttour[0]][1], coord[*besttour[0]][2]);

    fclose(fp);
}

//解のみを出力する関数
int randcostplot(int t, int *bestcost){
    char filename[30];
    FILE *fp;

    //excelでグラフにするため、テキスト形式での出力
    sprintf(filename, "random%d.txt", t);
    if((fp=fopen(filename, "a"))==NULL){
        printf("File Open Error: %s\n", filename);
        exit(1);
    }

    fprintf(fp, "%d\n", *bestcost);
    fclose(fp);
}


//ランダム巡回路のコストの計算と表示
int costRAND(int n, int **cost, int **coord, int **besttour, int *bestcost){
    int tmp, t, i, j;
    double rtime;
    clock_t start, end;

    //実行回数をtに格納
    scanf("%d", &t);
    
    start = clock();

    //sgenrand()の値をプログラム実行ごとに変更しなければならない
    //今回はプログラム冒頭にAを定義してあるので、実行ごとに数を増やしていく
    sgenrand(A);

    //課題1に対応するため、1回を複数回繰り返すようにしている
    //whileの条件文の数を変えることで何回繰り返すか決められる
    //実行時には、以前同様な条件で実行した場合の.datと.txtを削除しておくかディレクトリから移動させておかないと追記されてしまう
    j=0;
    while(j != 200){
        //t回探索路の作成とコストの計算
        //都度bestcostに最良コストが格納される
        i=0;
        while(i!=t){
            //課題1でなければmakecoordは不要
            makecoord(n, bestcost, cost, besttour);
            sortRAND(n, bestcost, cost, besttour);
            i++;
        }

        //最良巡回路の表示
        //printf("BESTCOST is %d\n", *bestcost);
        //printf("BESTTOUR is ");
        //for(i=0; i<n; i++){
        //    printf("%d ", *besttour[i] + 1);
        //}
        //printf("\n");

        end = clock();
        rtime = (double)(end - start) / CLOCKS_PER_SEC;

        //最良巡回路のファイル出力
        randplot(t, coord, besttour, n, bestcost, rtime);
        //解のみの出力
        randcostplot(t, bestcost);
        j++;
    }
    
    printf("Complete!\n");
}

//山登り法のファイル出力
int MCplot(int t, int **coord, int **besttour, int n, int *bestcost, double rtime){
    char filename[30];
    FILE *fp;
    int i;
    int iteration = t+1;

    for(i=1; i<iteration; i++){
        if(i%t == 0){
            sprintf(filename, " hill-climbing-%d.dat", i);
            if((fp=fopen(filename, "w"))==NULL){
                printf("File Open Error: %s\n", filename);
                exit(1);
            }
        }
    }
    fprintf(fp, "#問題:eil51.tsp\n");
    fprintf(fp, "#解放:hill-climbing\n");
    fprintf(fp, "#近傍:%s\n", NEIGHBOR_MODE);
    fprintf(fp, "#繰り返し回数:%d\n", t);
    fprintf(fp, "#暫定解:%d\n", *bestcost);
    fprintf(fp, "#実行時間:%lf\n", rtime);
    for(i=0; i<n; i++){
        fprintf(fp, "%d %d\n", coord[*besttour[i]][1], coord[*besttour[i]][2]);
    }
    fprintf(fp, "%d %d\n", coord[*besttour[0]][1], coord[*besttour[0]][2]);
    printf("Complete!\n");
    fclose(fp);
}

//ランダム交換
//近傍解はgoodcostとgoodtourに保存される
int randomchange(int *goodcost, int **goodtour, int n, int **cost){
    int rctour[n];
    int rccost, tmp;

    //コピー
    for(int i=0; i<n; i++){
        rctour[i] = *goodtour[i];
    }

    //入れ替えとコストの計算、比較
    for(int i=0; i<n-1; i++){
        for(int j=i+1; j<n; j++){

            //入れ替え
            tmp = rctour[i];
            rctour[i] = rctour[j];
            rctour[j] = tmp;


            //コストの計算
            rccost = 0;
            for(int k=0; k<n-1; k++){
                rccost += cost[rctour[k]][rctour[k+1]];
            }
            rccost += cost[rctour[n-1]][rctour[0]];

            //goodcostとの比較と更新
            if(*goodcost > rccost){
                *goodcost = rccost;
                for(int k=0; k<n; k++){
                    *goodtour[k] = rctour[k];
                }
            }
            //入れ替えたものを元に戻す
            tmp = rctour[i];
            rctour[i] = rctour[j];
            rctour[j] = tmp;

        }
    }

    //近傍解の表示
    //for(int i=0; i<n; i++){
    //    printf("%d ", *goodtour[i]);
    //}
    //printf("\n");
    //printf("%d\n", *goodcost);

}


//2-opt近傍
int opt(int *goodcost, int **goodtour, int n, int **cost){
    int opttour[n];
    int optcost, tmp, curcost;

    //コピー
    for(int i=0; i<n; i++){
        opttour[i] = *goodtour[i];
    }

    //入れ替えとコストの計算、比較
    for(int i=0; i<n-1; i++){
        for(int j=i+1; j<n; j++){
            optcost = 0;
            curcost = 0;
            
            //iとjがどちらも端でない場合
            if(i != 0 && j!= n-1){
                optcost += cost[opttour[i-1]][opttour[j]];
                optcost += cost[opttour[i]][opttour[j+1]];
                curcost += cost[opttour[i-1]][opttour[i]];
                curcost += cost[opttour[j]][opttour[j+1]];
            }
            //iが左端かつjが右端でない場合
            else if(i == 0 && j != n-1){
                optcost += cost[opttour[i]][opttour[j+1]];
                curcost += cost[opttour[j]][opttour[j+1]];
            }
            //iが左端でなくかつjが右端の場合
            else if(i != 0 && j == n-1){
                optcost += cost[opttour[i-1]][opttour[j]];
                curcost += cost[opttour[i-1]][opttour[i]];
            }
            //iもjも端の場合、optcostとcurcostは同一になる
            //簡単のため、量端から一つ内側に入るコストを計算して両方に同じ値を入れる
            else{
                optcost += cost[opttour[i]][opttour[i+1]];
                optcost += cost[opttour[j-1]][opttour[j]];
                curcost = optcost;
            }

            //curcostとoptcostの比較と交換
            if(curcost > optcost){
                //goodtourの更新
                if(i != 0){
                    for(int k=0; k<=i-1; k++){
                        tmp = opttour[k];
                        *goodtour[k] = tmp;
                    }
                }
                for(int k=i; k<j+1; k++){
                    tmp = opttour[j-k+i];
                    *goodtour[k] = tmp;
                }
                if(j != n-1){
                    for(int k=j+1; k<n; k++){
                        tmp = opttour[k];
                        *goodtour[k] = tmp;
                    }
                }
                //goodcostの更新
                *goodcost = 0;
                for(int k=0; k<n-1; k++){
                    *goodcost += cost[*goodtour[k]][*goodtour[k+1]];
                }
                *goodcost += cost[*goodtour[n-1]][*goodtour[0]];
            }
        }
    }

}

//山登り法の再帰部分
int costMCloop(int n, int *bestcost, int **besttour, int **cost){
    int **goodtour, *goodcost;
    int tmp1, check=0;

    //goodtourとgoodcostはrandomchange()とopt()が近傍回を保持するためのもの
    tmp1 = __INT_MAX__;
    goodcost = &tmp1;
    goodtour = (int**)malloc(n*sizeof(int*));
    for(int i=0; i<n; i++){
        goodtour[i] = (int*)malloc(sizeof(int));
    }

    //コピー
    *goodcost = *bestcost;
    for(int i=0; i<n; i++){
        *goodtour[i] = *besttour[i];
    }

    //近傍を作成して最も良いものを選出
    if(strcmp(NEIGHBOR_MODE, "RANDOM") == 0){
        randomchange(goodcost, goodtour, n, cost);
    }
    if(strcmp(NEIGHBOR_MODE, "2OPT") == 0){
        opt(goodcost, goodtour, n, cost);
    }

    //bestcostと近傍解(goodcost)の比較と更新
    if(*bestcost > *goodcost){
        *bestcost = *goodcost;
        for(int i=0; i<n; i++){
            *besttour[i] = *goodtour[i];
        }
        check = 1;
    }

    if(check == 1){
        costMCloop(n, bestcost, besttour, cost);
    }

}


//山登り法
int costMC(int n, int *bestcost, int **cost, int **besttour, int **coord){
    int t, i, tmp;
    int *MCcost;
    int **MCtour;
    double rtime;
    clock_t start, end;

    //実行回数をtに格納
    scanf("%d", &t);

    start = clock();

    //sgenrand()の値をプログラム実行ごとに変更しなければならない
    //今回はプログラム冒頭にAを定義してあるので、実行ごとに数を増やしていく
    sgenrand(A);

    //全体を通じて最も良い回路
    //本来はbestcostを充てるべきだが、誤ってプログラムを作成してしまったため、新たに作成した
    tmp = __INT_MAX__;
    MCcost = &tmp;

    MCtour = (int**)malloc(n*sizeof(int*));
    for(i=0; i<n; i++){
        MCtour[i] = (int*)malloc(sizeof(int));
    }

    //t回探索路の作成とコストの計算
    //bestcostには、各繰り返しの中で最良な探索路が格納されている
    i=0;
    while(i != t){
        //初期解の作成
        makecoord(n, bestcost, cost, besttour);

        //再帰の開始
        costMCloop(n, bestcost, besttour, cost);

        //初回のみbestをMCへコピー、それ以外は比較して格納
        if(i==0){
            *MCcost = *bestcost;
            for(int j=0; j<n; j++){
                *MCtour[j] = *besttour[j];
            }
        }
        else{
            if(*MCcost > *bestcost){
                *MCcost = *bestcost;
                for(int j=0; j<n; j++){
                    *MCtour[j] = *besttour[j];
                }
            }
        }
        i++;
    }

    //最良巡回路の表示
    //printf("BESTCOST is %d\n", *MCcost);
    //printf("BESTTOUR is ");
    //for(i=0; i<n; i++){
    //    printf("%d ", *MCtour[i] + 1);
    //}
    //printf("\n");

    end = clock();
    rtime = (double)(end - start) / CLOCKS_PER_SEC;

    //出力
    MCplot(t, coord, MCtour, n, MCcost, rtime);
}

//SA方の出力
int SAplot(int n, double t, int r, double a, double b, int r1, int **coord, int **besttour, int *bestcost, double rtime){
    char filename[30];
    FILE *fp;
    int i;
    int iteration = r1+1;

    for(i=1; i<iteration; i++){
        if(i%r1 == 0){
            sprintf(filename, "simulated-annealing-%d.dat", i);
            if((fp=fopen(filename, "w"))==NULL){
                printf("File Open Error; %s\n", filename);
                exit(1);
            }
        }
    }
    fprintf(fp, "#問題:eil51.tsp\n");
    fprintf(fp, "#解放:simulated-annealing\n");
    fprintf(fp, "#近傍:%s\n", NEIGHBOR_MODE);
    fprintf(fp, "#初期温度:%lf\n", t);
    fprintf(fp, "#初期反復回数:%d\n", r);
    fprintf(fp, "#温度減少率(α):%lf\n", a);
    fprintf(fp, "#反復回数減少率:%lf\n", b);
    fprintf(fp, "#繰り返し回数:%d\n", r1);
    fprintf(fp, "#暫定解:%d\n", *bestcost);
    fprintf(fp, "#実行時間:%lf\n", rtime);
    for(i=0; i<n; i++){
        fprintf(fp, "%d %d\n", coord[*besttour[i]][1], coord[*besttour[i]][2]);
    }
    fprintf(fp, "%d %d\n", coord[*besttour[0]][1], coord[*besttour[0]][2]);

    printf("Complete!\n");
    fclose(fp);
}

//SimulatedAnnealing
int costSA(int n, int *bestcost, int **cost, int **besttour, int **coord){
    double t, a, b, d, ft, rtime;
    int r, fr, r1, i, check, ytour[n], ycost, tmp, tmp1, tmp2, ycopy[n];
    clock_t start, end;

    start = clock();

    //反復回数
    r = 100;
    fr = r;

    //温度
    t = 1.0;
    ft = t;

    //温度減少率
    a = 0.99;

    //反復回数減少率
    b = 1.0;
    
    sgenrand(A);

    //近傍解を入れておくytourとycostの初期化
    for(i=0; i<n; i++){
        ytour[i] = 0;
    }
    ycost = 0;

    r1 = 0;
    while(1){
        check = 0;
        i=0;
        //r回繰り返す
        while(i != r){
            //初期解の生成
            makecoord(n, bestcost, cost, besttour);
            //bestcostをyにコピー
            for(int j=0; j<n; j++){
                ytour[j] = *besttour[j];
            }
            //0~51のランダムな数から近傍を作成
            if(strcmp(NEIGHBOR_MODE, "RANDOM") == 0){
                //tmp1とtmp2に0~51の別々の数を充てる
                tmp1 = (int)(genrand()*n);
                tmp2 = tmp1;
                while(tmp1 == tmp2){
                    tmp2 = (int)(genrand()*n);
                }
                //tmp1とtmp2の位置にある点を交換
                tmp = ytour[tmp1];
                ytour[tmp1] = ytour[tmp2];
                ytour[tmp2] = tmp;
                //コストの更新
                ycost = 0;
                for(int j=0; j<n-1; j++){
                    ycost += cost[ytour[j]][ytour[j+1]];
                }
                ycost += cost[ytour[n-1]][ytour[0]];
            }
            else if(strcmp(NEIGHBOR_MODE, "2OPT") == 0){
                //tmp1とtmp2に0~50の別々の数を充てる
                tmp1 = (int)(genrand()*n);
                tmp2 = tmp1;
                while(tmp1 == tmp2){
                    tmp2 = (int)(genrand()*n);
                }
                //ycopyの作成
                for(int j=0; j<n; j++){
                    ycopy[j] = ytour[j];
                }
                //tmp1からtmp2の位置にある点を逆順にする
                if(tmp1>tmp2){
                    tmp = tmp1;
                    tmp1 = tmp2;
                    tmp2 = tmp;
                }
                for(int j=tmp1; j<=tmp2; j++){
                    ytour[j] = ycopy[tmp1+tmp2-j];
                }
                //コストの更新
                ycost = 0;
                for(int j=0; j<n-1; j++){
                    ycost += cost[ytour[j]][ytour[j+1]];
                }
                ycost += cost[ytour[n-1]][ytour[0]];
            }
            else{
                printf("Please change NEIGHBOR_MODE with \"RANDOM\" or \"2OPT\".\n");
            }

            //bestとyの比較と交換
            d = ycost - *bestcost;
            tmp = genrand();
            if(d<=0){
                for(int j=0; j<n; j++){
                    *besttour[j] = ytour[j];
                }
                *bestcost = ycost;
                check = 1;
            }
            else if(exp(-d/t)>=tmp){
                for(int j=0; j<n; j++){
                    *besttour[j] = ytour[j];
                }
                *bestcost = ycost;
                check = 1;
            }
            i++;
        }
        

        //Tの更新
        t *= a;

        //Rの更新
        r *= b;


        //終了条件:解の改善が行われなくなったら終了とした
        //if(check == 0){
        //    break;
        //}
        
        //終了条件:温度が0.01以下になったら終了
        if(t<0.001){
            break;
        }
        r1++;
    }

    //解の表示
    //printf("BESTTOUR is ");
    //for(int j=0; j<n; j++){
    //    printf("%d ", *besttour[j]);
    //}
    //printf("\n");
    //printf("BESTCOST is %d\n", *bestcost);

    end = clock();
    rtime = (double)(end - start) / CLOCKS_PER_SEC;

    //プロット
    SAplot(n, ft, fr, a, b, r1, coord, besttour, bestcost, rtime);
}

//コストを計算して二次元配列に格納
int costCAL(int n, int **coord, int **cost){
    double temp;

    //コストの計算
    //sqrt()やpow()はdouble型でなければならないので、一度double型で計算してから四捨五入して配列に格納する
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            temp = sqrt(pow((coord[i][1] - coord[j][1]),2) + pow((coord[i][2] - coord[j][2]),2));
            //intへのキャストは切り捨てなので0.5を足すことで四捨五入を行う
            temp += 0.5;
            cost[i][j] = (int)temp;
        }
    }

    //コストの表示
    //for(int i=0; i<n; i++){
    //    for(int j=0; j<n; j++){
    //        printf("%d ", cost[i][j]);
    //    }
    //    printf("\n");
    //}

}

//座標の読み込み
//座標数とargv[]を引数として渡す
int coordinateR(int n, char *argv[], int **coord){
    
    FILE *fp;
    char temp[100];
    int temporary;

    //fileopen
    if((fp = fopen(argv[1], "r")) == NULL){
        printf("file open error!\n");
        exit(1);
    }    

    //読み込むのはNODE_COORD_SECTIONの次からなので、DIMENSIONと同様に空読みをする
    do{
        fscanf(fp, "%s", temp);
        if(strcmp("NODE_COORD_SECTION", temp) == 0){
            fscanf(fp, "%s", temp);
            break;
        }
    }while(1);

    //座標情報を配列へ書き込む
    //なぜか上記のように空読みするとNODE_COORD_SECTIONの次の1が飛ばされてしまうため、手動で入力した
    coord[0][0] = 1;

    //0行目
    for(int i=1; i<3; i++){
        fscanf(fp, "%d", &coord[0][i]);
    }
    
    //1行目以降
    for(int i=1; i<n; i++){
        for(int j=0; j<3; j++){
            fscanf(fp, "%d", &coord[i][j]);
        }
    }

    //確認のため表示
    //for(int i=0; i<n; i++){
    //    for(int j=0; j<3; j++){
    //        printf("%d ", coord[i][j]);
    //    }
    //    printf("\n");
    //}


    fclose(fp);

}



//argcはコマンドライン引数の個数（プログラム名自身も含む）？？？
//argv[0]は「C:\Users\palu\Desktop\ensyu\tspsolve.exe」
//argv[1]はeil51.tsp
//となりましためでたし
//argcの数=argv[]の要素数なのかなあ
int main(int argc, char *argv[]){
    int n, **cost, **coord;
    FILE *fp;
    char temp[100];
    int **besttour;
    int *bestcost;
    int tmp;

    //何が入っているかの確認
    //printf("%d\n", argc);
    //printf("%s\n", argv[0]);
    //printf("%s\n", argv[1]);


    if(argc != 3){
        printf("Usage: sample <input_filename>\n");
        exit(1);
    }

    if((fp = fopen(argv[1], "r")) == NULL){
        printf("file open error!\n");
        exit(1);
    }

    do{
        fscanf(fp, "%s", temp);
        if(strcmp("DIMENSION", temp) == 0){
            fscanf(fp, "%s", temp);
            break;
        }
        if(strcmp("DIMENSION:", temp) == 0){
            break;
        }
    }while(1);

    fscanf(fp, "%d", &n);
    fclose(fp);

    //座標を保存しておくためのn*3の2次元配列
    coord = (int**)malloc(n*sizeof(int*));
    for(int i = 0; i < n; i++){
        coord[i] = (int*)malloc(3*sizeof(int));
    }

    //コストはn*nの2次元配列
    cost = (int**)malloc(n*sizeof(int*));
    for(int i=0; i<n; i++){
       cost[i] = (int*)malloc(n*sizeof(int));
    }

    //座標軸の読み込み
    coordinateR(n, argv, coord);
    //コストの計算
    costCAL(n, coord, cost);

    //bestcostとbesttourの初期化
    //最良巡回路のコストと巡回路を格納
    tmp = __INT_MAX__;
    bestcost = &tmp;

    besttour = (int**)malloc(n*sizeof(int*));
    for(int i=0; i<n; i++){
        besttour[i] = (int*)malloc(sizeof(int));
    }



    //argv[2]の値によってランダム法と山登り法、シミュレーティド・アニーリング法、単純巡回路法を選択するか選べる
    if(strcmp(argv[2], "random") == 0){
        costRAND(n, cost, coord, besttour, bestcost);
    }
    else if(strcmp(argv[2], "hill-climbing") == 0){
        costMC(n, bestcost, cost, besttour, coord);
    }
    else if(strcmp(argv[2], "SA") == 0){
        costSA(n, bestcost, cost, besttour, coord);
    }
    else if(strcmp(argv[2], "ASC") == 0){
        costASC(n, cost);
    }
    else{
        printf("Try again. Please type \"random\" or \"hill-climbing\" or \"SA\" or \"ASC\".\n");
    }


}