巡回セールスマン問題　2-opt法

rxtfr039 · #1

現在大学に通っている学生です。
初めて質問させて頂きます。よろしくお願いします。

C言語を利用したプログラムに関する質問です。
巡回セールスマン問題を2-opt法による最降急下法で解く課題に取り組んでいるのですが、
セグメントエラーが発生して処理が途中で止まってしまい困っています。

[ソースコード]

コード:

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


/* 都市の座標構造体 */
struct City {
	int x, y;
};

/* 問題情報構造体 */
struct TSP {
    int N;                  /*都市数*/
    int nC2;                 /*2-opt法に利用する2数の組み合わせ総数*/
    struct City *city;	/* 都市の位置 */
    float CurrentCost;      /*変形前の移動距離*/
    float ChangedCost;	/*変形後の移動距離*/			
    int *CurrentOrder;    /* 変形前の巡回順を記録する*/
    int *ChangedOrder;    /*変形後の巡回順を記録する*/
    int *count;                
    int *nCr;                 /*2-opt法に利用する2数の組み合わせを保持する変数*/
    int *stock;

};

/* 関数の宣言 */
void ReadData(struct TSP *tsp);
void ShowData(struct TSP *tsp);
void TwoOpt(struct TSP *tsp, int x1, int x2);
int UpdateOrder(struct TSP *tsp);
float CalcDistance(struct City a, struct City b);
void SetOrder(struct TSP *tsp);
void CalcCost(struct TSP *tsp);
void calcNCR(struct TSP *tsp);
void ShowOrder(struct TSP *tsp);

/*
 * メイン関数
 */
int main()
{
    srand((unsigned int)time(NULL));   
    int count = 0;
    struct TSP tsp;
    ReadData(&tsp);
    ShowData(&tsp);
    SetOrder(&tsp);
    calcNCR(&tsp);
    while(1)
    {
        for(i = 0; i < (tsp.nC2)*2; i = i + 2)
        {
             printf("Start TwoOpt\n\n");
             printf("%d%d\n",tsp.nCr[i], tsp.nCr[i+1]);---------[1]
             TwoOpt(&tsp, tsp.nCr[i], tsp.nCr[i+1]);
             j = UpdateOrder(&tsp);

            if(j == 1)
           {
                  ShowCost(&tsp);
                 for(m = 0; m < tsp.N; m++)
              　 {
                       tsp.CurrentOrder[m] = tsp.ChangedOrder[m];
                 }
                　count++;
                　printf("Cost was Inpruved \n");
             }
             if(j == 0)
             {
                　ShowCost(&tsp);
                　printf("Not Inpruved\n");
             }
      }
       printf("finish\n");
       if(count == 0)break;
       else 
       {    
　　　　　  count = 0;
             i = 0;
        }
    }
　　　
    free(tsp.CurrentOrder);
    free(tsp.ChangedOrder);
    free(tsp.city);
    free(tsp.count);
    free(tsp.stock);
    free(tsp.nCr);

 
	return 0;
}

/*
 * 都市座標データ読み込み
 * 引数：struct TSP *tsp : TSPデータ
 */
void ReadData(struct TSP *tsp)
{
    FILE *fileSaveBox;
    char fileName[256];
    int i;

    printf("Input file Name");
    gets(fileName);
    printf("Input counts of city");
    scanf("%d", &tsp->N);

    fileSaveBox = fopen( fileName,"r");
    if(fileSaveBox == NULL) printf("Failed to open file");

   
    tsp->city = (struct City*)malloc(sizeof(struct City)*(tsp->N));

    tsp->CurrentOrder = (int*)malloc(sizeof(int)*(tsp->N + 1));

    tsp->ChangedOrder = (int*)malloc(sizeof(int)*(tsp->N + 1));
    
    tsp->count = (int*)malloc(sizeof(int)*(tsp->N));

    tsp->stock = (int*)malloc(sizeof(int)*(tsp->N));

    tsp->nC2 = factorial(tsp->N, tsp)/2 - tsp->N + 1;

    tsp->nCr = (int*)malloc(sizeof(int)*(tsp->nC2)*2 );

         
    for(i=0; i < tsp->N; i++)
    {
        fscanf(fileSaveBox, "%d,%d", &tsp->city[i].x, &tsp->city[i].y);
        
    }
}

/*　巡回列を入れ替えるために利用する２数のすべての組合わせ
 * を変数nCrへ入れる
 * 
 */
void calcNCR(struct TSP *tsp)
{
    int j;
    int i = 0;
    int m = 2;

    for(j = 0; j < tsp->N - 2; j++)
    {
        
        while(m + j  != tsp->N)
        {
            tsp->nCr[i] = j;
            tsp->nCr[i + 1] = j + m;
			
            i = i + 2;
            m++;
            
        }
       m = 2;
    }
    printf("i = %d\n", i);
    
}
/* 巡回路を変形する.
 * 現在の巡回順配列において,配列番号X1とx2の間の
 *　データを入れ替える
 */
void TwoOpt(struct TSP *tsp, int x1, int x2)
{
    int i = 0;
    printf("break1\n");
    while(1)
    {
        
        if(tsp->CurrentOrder[ x1 + i ] == tsp->CurrentOrder[ x2 - i ])
        {
            tsp->ChangedOrder[ x1 + i] = tsp->CurrentOrder[ x1 + i ];
            break;
        }

        else
        {
            
            tsp->ChangedOrder[ x2 - i] = tsp->CurrentOrder[ x1 + i ];
            tsp->ChangedOrder[ x1 + i] = tsp->CurrentOrder[ x2 - i ];
            i++;
        }
    }
    
    for(i = 1; i <= x1; i++)
    {
        tsp->ChangedOrder[x1 - i] = tsp->CurrentOrder[ x1 - i ];
    }
  
    for(i = 1; i <= tsp->N - x2 - 1; i++)
    {
        tsp->ChangedOrder[ x2 + i] = tsp->CurrentOrder[ x2 + i ];
    }
 
}

/* 巡回路変更後に移動距離の改善の
 *　有無を判定する
 *　引数：struct TSP *tsp
 */
int UpdateOrder(struct TSP *tsp)
{
    CalcCost(tsp);
    if( tsp->CurrentCost > tsp->ChangedCost ) return 1;
    else return 0;
}

/* 読み込んだデータを表示する
 *　引数；struct TSP *tsp
 */
        
void ShowData(struct TSP *tsp)
{
　　　　int i;
　　　　printf("Cities location:\n");
　　　　for (i = 0; i < tsp->N; i ++)
　　　 {
　　　　　　　　printf("C%-2d : %4d,%4d\n", 
	　　　　i + 1, tsp->city[i].x, tsp->city[i].y);
　　　　}
     
}

/*
 * ランダムに巡回順を設定する
 * 引数：struct TSP *tsp : TSPデータ
 */
void SetOrder(struct TSP *tsp)
{
    int j,k,n;
    int count = 0;

    for(j = 0; ; j++)
    {
        if(j == 0)
        {
            
            tsp->stock[count] = rand() % tsp->N;
            tsp->CurrentOrder[count] = tsp->stock[count];
        }

        if(j != 0)
        {
       
            k = rand() % tsp->N;
            for(n = 0; n <= count; n++)
              {
                   
                if(tsp->stock[n] == k) break;
                if(n == count)
                   {
                    count++;
                    tsp->CurrentOrder[count] = k;
                    tsp->stock[count] = k;
                   }

              }
            
            if(count == tsp->N - 1) break;
        }
    }

}
     
/*
 * 総移動距離を計算する
 * 引数：struct TSP *tsp : TSPデータ
 */
void CalcCost(struct TSP *tsp)
{
    int i;
    float mCost = 0;
    float *sCost = (float*)malloc(sizeof(float)*(tsp->N +1));

    for(i = 0; i < tsp->N; i++)
    {
        if(i == tsp->N-1)
        {
            sCost[i] = CalcDistance(tsp->city[tsp->CurrentOrder[i]], tsp->city[tsp->CurrentOrder[0]]);
            
            mCost = mCost + sCost[i];
        }
        else
        {
            sCost[i] = CalcDistance(tsp->city[tsp->CurrentOrder[i]], tsp->city[tsp->CurrentOrder[i+1]]);
           
            mCost = mCost + sCost[i];
        }

    }
    
    tsp->CurrentCost = mCost;
   
    mCost = 0;

    for(i = 0; i < tsp->N; i++)
    {
        if(i == tsp->N-1)
        {
            sCost[i] = CalcDistance(tsp->city[tsp->ChangedOrder[i]], tsp->city[tsp->ChangedOrder[0]]);
            
            mCost = mCost + sCost[i];
        }
        else
        {
            sCost[i] = CalcDistance(tsp->city[tsp->ChangedOrder[i]], tsp->city[tsp->ChangedOrder[i+1]]);
           
            mCost = mCost + sCost[i];
        }

    }
    
    tsp->ChangedCost = mCost;
    free(sCost);

}

/*
 * ２都市間の距離を計算
 * 引数：struct City a : 都市1
 * 引数：struct City b : 都市2
 * 戻り値：距離
 */
float CalcDistance(struct City a, struct City b)
{
     
        float sCost;

    	sCost = sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
       
        return sCost;

}

/*
 * 巡回順とコストを表示
 * 引数：struct TSP *tsp : TSPデータ
 */
void ShowCost(struct TSP *tsp)
{
    int i;
    printf("Current order\n");
    for (i = 0; i < tsp->N; i ++) {
        printf("C%-2d> ", tsp->CurrentOrder[i] + 1);
        }
    
    printf("C%-2d  cost=%7.1f\n", tsp->CurrentOrder[0] + 1, tsp->CurrentCost);

    printf("Changed order\n");
    for (i = 0; i < tsp->N; i ++) {
		printf("C%-2d> ", tsp->ChangedOrder[i] + 1);
	}
	
    printf("C%-2d  cost=%7.1f\n", tsp->ChangedOrder[0] + 1, tsp->ChangedCost);

}

[実行結果]

コード:

NEC-PCuser@NEC-PCuser-PC ~/cwork
$ ./a.exe
Input file Namecities06.csv
Input counts of city6
Cities location:
C1  :   93,  19
C2  :   25,  61
C3  :   18,   8
C4  :   67,  33
C5  :   94,  58
C6  :   56,   1
i = 20
Start TwoOpt

02
break1
Current order
C6 > C1 > C2 > C5 > C4 > C3 > C6   cost=  320.6
Changed order
C2 > C1 > C6 > C5 > C4 > C3 > C2   cost=  334.8
Not Inpruved
Start TwoOpt

03
break1
Current order
C6 > C1 > C2 > C5 > C4 > C3 > C6   cost=  320.6
Changed order
C5 > C2 > C1 > C6 > C4 > C3 > C5   cost=  370.0
Not Inpruved
Start TwoOpt

-5527346501629536776
break1
Segmentation fault (コアダンプ)

NEC-PCuser@NEC-PCuser-PC ~/cwork
$ ./a.exe
Input file Namecities06.csv
Input counts of city6
Cities location:
C1  :   93,  19
C2  :   25,  61
C3  :   18,   8
C4  :   67,  33
C5  :   94,  58
C6  :   56,   1
i = 20
Start TwoOpt

02
break1
Current order
C5 > C6 > C4 > C1 > C3 > C2 > C5   cost=  330.2
Changed order
C4 > C6 > C5 > C1 > C3 > C2 > C4   cost=  321.1
Cost was Inpruved
Start TwoOpt

03
break1
Current order
C4 > C6 > C5 > C1 > C3 > C2 > C4   cost=  321.1
Changed order
C1 > C5 > C6 > C4 > C3 > C2 > C1   cost=  329.8
Not Inpruved
Start TwoOpt

04
break1
Current order
C4 > C6 > C5 > C1 > C3 > C2 > C4   cost=  321.1
Changed order
C3 > C1 > C5 > C6 > C4 > C2 > C3   cost=  321.1
Not Inpruved
Start TwoOpt

05
break1
Current order
C4 > C6 > C5 > C1 > C3 > C2 > C4   cost=  321.1
Changed order
C2 > C3 > C1 > C5 > C6 > C4 > C2   cost=  321.1
Not Inpruved
Start TwoOpt

13
break1
Current order
C4 > C6 > C5 > C1 > C3 > C2 > C4   cost=  321.1
Changed order
C4 > C1 > C5 > C6 > C3 > C2 > C4   cost=  279.6
Cost was Inpruved
Start TwoOpt

14
break1
Current order
C4 > C1 > C5 > C6 > C3 > C2 > C4   cost=  279.6
Changed order
C4 > C3 > C6 > C5 > C1 > C2 > C4   cost=  331.6
Not Inpruved
Start TwoOpt

15
break1
Current order
C4 > C1 > C5 > C6 > C3 > C2 > C4   cost=  279.6
Changed order
C4 > C2 > C3 > C6 > C5 > C1 > C4   cost=  279.6
Not Inpruved
Start TwoOpt

24
break1
Current order
C4 > C1 > C5 > C6 > C3 > C2 > C4   cost=  279.6
Changed order
C4 > C1 > C3 > C6 > C5 > C2 > C4   cost=  332.0
Not Inpruved
Start TwoOpt

25
break1
Current order
C4 > C1 > C5 > C6 > C3 > C2 > C4   cost=  279.6
Changed order
C4 > C1 > C2 > C3 > C6 > C5 > C4   cost=  306.9
Not Inpruved
Start TwoOpt

35
break1
Current order
C4 > C1 > C5 > C6 > C3 > C2 > C4   cost=  279.6
Changed order
C4 > C1 > C5 > C2 > C3 > C6 > C4   cost=  263.5
Cost was Inpruved
finish
Start TwoOpt

02
break1
Current order
C4 > C1 > C5 > C2 > C3 > C6 > C4   cost=  263.5
Changed order
C5 > C1 > C4 > C2 > C3 > C6 > C5   cost=  279.6
Not Inpruved
Start TwoOpt

03
break1
Current order
C4 > C1 > C5 > C2 > C3 > C6 > C4   cost=  263.5
Changed order
C2 > C5 > C1 > C4 > C3 > C6 > C2   cost=  298.8
Not Inpruved
Start TwoOpt

-5527346501629536776
break1
Segmentation fault (コアダンプ)

関数TowOptに関数calcNCRで生成した経路変形方法のすべての組み合わせ配列nCrを順に渡し、
一回の関数TowOptの処理ごとに移動距離が改善したかを、関数UpdateOrderで判定します。

経路変形のすべての方法を試して移動距離が一度でも改善した場合、
再び2-opt法をすべて変形方法で適応します。
経路変形のすべての方法を試しても移動距離が改善しない場合、
ループ処理を終了して終了時の移動距離を近似解とするようにします。

main関数中--[1]で経路変形方法を保管した配列ｎCrをprintしてみると,
セグメントエラー直前で中身がおかしくなり,
その値を関数TwoOptに渡すことによりセグメントエラーが発生していると思います。

そこで質問なのですが、なぜ配列nCrの中身がおかしな値になってしまったのでしょうか。

長いコードで読むのが大変だとは思いますが、どうかお助けください。

プログラムに利用する都市配置データを添付しておきます。

よろしくお願いします。

[環境] 　
　OS ： Windows　vista
　コンパイラ名： Cygwin

へにっくす · #2

すみません
掲示したコードでは、コンパイルできませんね。
----[1]と書いてるところはコメントになっていないし
変数 i、j、mが定義されていないし、全角空白が混じっているし、
関数のShowCost、factorialが未定義ですし…
（ShowCostはプロトタイプ宣言の漏れですね）
（factorialはライブラリ関数かな？　もしそうだったとしても、式自体あやしいけどね）

そのまま張り付けてCygwinで通るのですか？
とてもそう思えないのですが…
検証してもらうのであれば、せめてコンパイルできるようにして張り付けてください。

Yunix · #3

コード:

tsp->nC2 = factorial(tsp->N, tsp)/2 - tsp->N + 1; //factorial()がどんなのかは知らないが、６の階乗をして計算すると、nC2 = 353
tsp->nCr = (int*)malloc(sizeof(int)*(tsp->nC2)*2 );//nCr[353*2]を確保

calcNCRではnCr[0]からnCr[19]まで数値を代入している(それ以降は何も行っていない、つまり、nCr[20]からはどんな数値が入っているのか不明)。
main関数のfor文ではnCr[0]からnCr[352*2 - 1]までループして使っている。
nCr[20]からはどんな数値が入っているのかは不明なので、たとえば-23423423などの数値が入っているとそれは予期せぬメモリへとアクセスをしちゃいます。

コード:

for(i = 0; i < (tsp.nC2)*2; i = i + 2)//nC2 = 353, i < 353*2までループ
        {
             printf("Start TwoOpt\n\n");
             printf("%d%d\n",tsp.nCr[i], tsp.nCr[i+1]);//---------[1] 
             TwoOpt(&tsp, tsp.nCr[i], tsp.nCr[i+1]);//i = 20 のとき、TwoOpt(nCr[20], nCr[21]);で変な数値が入りエラーとなる

多分こんな感じのエラーかと思います。