初めて質問させて頂きます。よろしくお願いします。
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);
}
}
/* 巡回列を入れ替えるために利用する2数のすべての組合わせ
* を変数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);
}
/*
* 2都市間の距離を計算
* 引数: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の処理ごとに移動距離が改善したかを、関数UpdateOrderで判定します。
経路変形のすべての方法を試して移動距離が一度でも改善した場合、
再び2-opt法をすべて変形方法で適応します。
経路変形のすべての方法を試しても移動距離が改善しない場合、
ループ処理を終了して終了時の移動距離を近似解とするようにします。
main関数中--[1]で経路変形方法を保管した配列nCrをprintしてみると,
セグメントエラー直前で中身がおかしくなり,
その値を関数TwoOptに渡すことによりセグメントエラーが発生していると思います。
そこで質問なのですが、なぜ配列nCrの中身がおかしな値になってしまったのでしょうか。
長いコードで読むのが大変だとは思いますが、どうかお助けください。
プログラムに利用する都市配置データを添付しておきます。
よろしくお願いします。
[環境]
OS : Windows vista
コンパイラ名 : Cygwin