#1
by kuu » 3年前
現在大学に通っている学生です。
初めて質問させて頂きます。よろしくお願いいたします。
C言語を利用したプログラムに関する質問です。C言語に関しては本格的に始めてから3ヶ月ほどです。
巡回セールスマン問題を2-opt法による最降急下法で解く課題に取り組んでいるのですが、その準備段階として
2-opt法のパラメータを与えることで巡回路の改善または維持を判断・出力する関数 UpdateOrder()を作成する課題がに取り組んでおります。巡回順は正しく処理されているのにもかかわらず距離が正しく計算されていない理由がわかりません。また,UpdateOrderの関数も処理されていない原因がわかりません。お助けください。
[ソースコード]
コード:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define N 5 /* 都市数 */
/* 都市の座標構造体 */
struct City {
int x, y;
};
/* 問題情報構造体 */
struct TSP {
struct City city[N]; /* 都市の位置 */
int currentOrder[N];
int changedOrder[N]; /* 巡回順 */
float currentCost;
float changedCost; /* 総移動距離 */
};
/* 関数の宣言 */
void ReadData(struct TSP *tsp);
void ShowData(struct TSP *tsp);
void TwoOpt(const int currentOrder[N], int changedOrder[N], int x1, int x2);
float CalcDistance(struct City a, struct City b);
void currentOrder(struct TSP *tsp);
void CalcCost(struct TSP *tsp);
int UpdateOrder(struct TSP *tsp, int x1, int x2);
void ShowCost(struct TSP *tsp);
/* メイン関数 */
int main()
{
struct TSP tsp;
ReadData(&tsp);
ShowData(&tsp);
currentOrder(&tsp);
ShowCost(&tsp);
return 0;
}
/*
* 都市座標データ読み込み
* 引数:struct TSP *tsp : TSPデータ
*/
void ReadData(struct TSP *tsp)
{
FILE *fp = fopen("cities05.csv", "r");
if (fp == NULL){
printf("Can't open data file.\n");
return;
}
/* read data */
int i;
for(i=0;i<N;i++){
fscanf(fp,"%d,%d",&tsp->city[i].x,&tsp->city[i].y);
}
/* ending */
fclose(fp);
}
/*
* 都市座標データ表示
* 引数:struct TSP *tsp : TSPデータ
*/
void ShowData(struct TSP *tsp)
{
int i;
/* データ表示 */
printf("Cities location:\n");
for (i = 0; i < N; i ++) {
printf("C%-2d : %4d,%4d\n",
i + 1, tsp->city[i].x, tsp->city[i].y);
}
}
/*2-opt関数
* currentorderの配列番号X1とx2の間のデータを入れ替える
*/
void TwoOpt(const int currentOrder[N], int changedOrder[N], int x1, int x2)
{
int i=0;
while(1)
{
if(currentOrder[x1+i] == currentOrder[x2-i])
{
changedOrder[x1+i] = currentOrder[x1+i];
break;
}
else
{
changedOrder[x2-i] = currentOrder[x1+i];
changedOrder[x1+i] = currentOrder[x2-i];
i++;
}
}
for(i=1;i<=x1;i++)
{
changedOrder[x1-i] = currentOrder[x1-i];
}
for(i=1;i<=N-x2-1;i++)
{
changedOrder[x2+i] = currentOrder[x2+i];
}
}
/*UpdateOrder関数
*巡回路変更後に移動距離の改善の有無を判定する
* 引数:struct TSP *tsp
*/
int UpdateOrder(struct TSP *tsp, int x1, int x2)
{
CalcCost(tsp);
if( tsp->currentCost > tsp->changedCost)
return 1;
else
return 0;
}
/*currentOrder
*引数:struct TSP *tsp : TSPデータ
*/
void currentOrder(struct TSP *tsp)
{
printf("current order\n");
int currentOrder[N];
int i;
for(i=0;i<N;i++){
currentOrder[i]=i;
}
}
/*
* 総移動距離を計算する
* 引数:struct TSP *tsp : TSPデータ
*/
void CalcCost(struct TSP *tsp)
{
int i;
tsp->currentCost=0;
for(i=0;i<N;i++){
if(i==N-1){
tsp->currentCost+= CalcDistance(tsp->city[tsp->currentOrder[i]],tsp->city[tsp->currentOrder[0]]);
}
else{
tsp->currentCost+= CalcDistance(tsp->city[tsp->currentOrder[i]],tsp->city[tsp->currentOrder[i+1]]);
}
}
tsp->changedCost=0;
for(i=0;i<N;i++){
if(i==N-1){
tsp->changedCost+= CalcDistance(tsp->city[tsp->changedOrder[i]],tsp->city[tsp->changedOrder[0]]);
}
else{
tsp->changedCost+= CalcDistance(tsp->city[tsp->changedOrder[i]],tsp->city[tsp->changedOrder[i+1]]);
}
}
}
/*
* 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 currentOrder[N];
int changedOrder[N];
int i;
int x1,x2;
/* 変形前の(現在の)巡回路を表示 */
for(i=0;i<N;i++){
printf("C%-2d > ",currentOrder[i]+1);
}
printf("C%-2d current cost=%7.1f\n",currentOrder[0]+1,tsp->currentCost);
/* x1,x2をキーボードから入力 */
printf("enter x1,x2\n");
printf("x1=");scanf("%d",&x1);
printf("x2=");scanf("%d",&x2);
/* TwoOpt関数の呼び出し */
TwoOpt(currentOrder,changedOrder, x1,x2);
/* 変形後の巡回路を表示 */
printf("changed order\n");
for(i=0;i<N;i++){
printf("C%-2d > ",changedOrder[i]+1);
}
printf("C%-2d changed cost=%7.1f\n",changedOrder[0]+1,tsp->changedCost);
/* UpdateOrder関数の呼び出し */
UpdateOrder(tsp,x1,x2);
}
[実行結果]
コード:
Cities location:
C1 : 63, 95
C2 : 88, 48
C3 : 51, 21
C4 : 41, 64
C5 : 3, 32
current order
C1 > C2 > C3 > C4 > C5 > C1 current cost=-118815798519092436377119227904.0
enter x1,x2
x1=1
x2=4
(lldb)
現在大学に通っている学生です。
初めて質問させて頂きます。よろしくお願いいたします。
C言語を利用したプログラムに関する質問です。C言語に関しては本格的に始めてから3ヶ月ほどです。
巡回セールスマン問題を2-opt法による最降急下法で解く課題に取り組んでいるのですが、その準備段階として
2-opt法のパラメータを与えることで巡回路の改善または維持を判断・出力する関数 UpdateOrder()を作成する課題がに取り組んでおります。巡回順は正しく処理されているのにもかかわらず距離が正しく計算されていない理由がわかりません。また,UpdateOrderの関数も処理されていない原因がわかりません。お助けください。
[ソースコード]
[code]#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define N 5 /* 都市数 */
/* 都市の座標構造体 */
struct City {
int x, y;
};
/* 問題情報構造体 */
struct TSP {
struct City city[N]; /* 都市の位置 */
int currentOrder[N];
int changedOrder[N]; /* 巡回順 */
float currentCost;
float changedCost; /* 総移動距離 */
};
/* 関数の宣言 */
void ReadData(struct TSP *tsp);
void ShowData(struct TSP *tsp);
void TwoOpt(const int currentOrder[N], int changedOrder[N], int x1, int x2);
float CalcDistance(struct City a, struct City b);
void currentOrder(struct TSP *tsp);
void CalcCost(struct TSP *tsp);
int UpdateOrder(struct TSP *tsp, int x1, int x2);
void ShowCost(struct TSP *tsp);
/* メイン関数 */
int main()
{
struct TSP tsp;
ReadData(&tsp);
ShowData(&tsp);
currentOrder(&tsp);
ShowCost(&tsp);
return 0;
}
/*
* 都市座標データ読み込み
* 引数:struct TSP *tsp : TSPデータ
*/
void ReadData(struct TSP *tsp)
{
FILE *fp = fopen("cities05.csv", "r");
if (fp == NULL){
printf("Can't open data file.\n");
return;
}
/* read data */
int i;
for(i=0;i<N;i++){
fscanf(fp,"%d,%d",&tsp->city[i].x,&tsp->city[i].y);
}
/* ending */
fclose(fp);
}
/*
* 都市座標データ表示
* 引数:struct TSP *tsp : TSPデータ
*/
void ShowData(struct TSP *tsp)
{
int i;
/* データ表示 */
printf("Cities location:\n");
for (i = 0; i < N; i ++) {
printf("C%-2d : %4d,%4d\n",
i + 1, tsp->city[i].x, tsp->city[i].y);
}
}
/*2-opt関数
* currentorderの配列番号X1とx2の間のデータを入れ替える
*/
void TwoOpt(const int currentOrder[N], int changedOrder[N], int x1, int x2)
{
int i=0;
while(1)
{
if(currentOrder[x1+i] == currentOrder[x2-i])
{
changedOrder[x1+i] = currentOrder[x1+i];
break;
}
else
{
changedOrder[x2-i] = currentOrder[x1+i];
changedOrder[x1+i] = currentOrder[x2-i];
i++;
}
}
for(i=1;i<=x1;i++)
{
changedOrder[x1-i] = currentOrder[x1-i];
}
for(i=1;i<=N-x2-1;i++)
{
changedOrder[x2+i] = currentOrder[x2+i];
}
}
/*UpdateOrder関数
*巡回路変更後に移動距離の改善の有無を判定する
* 引数:struct TSP *tsp
*/
int UpdateOrder(struct TSP *tsp, int x1, int x2)
{
CalcCost(tsp);
if( tsp->currentCost > tsp->changedCost)
return 1;
else
return 0;
}
/*currentOrder
*引数:struct TSP *tsp : TSPデータ
*/
void currentOrder(struct TSP *tsp)
{
printf("current order\n");
int currentOrder[N];
int i;
for(i=0;i<N;i++){
currentOrder[i]=i;
}
}
/*
* 総移動距離を計算する
* 引数:struct TSP *tsp : TSPデータ
*/
void CalcCost(struct TSP *tsp)
{
int i;
tsp->currentCost=0;
for(i=0;i<N;i++){
if(i==N-1){
tsp->currentCost+= CalcDistance(tsp->city[tsp->currentOrder[i]],tsp->city[tsp->currentOrder[0]]);
}
else{
tsp->currentCost+= CalcDistance(tsp->city[tsp->currentOrder[i]],tsp->city[tsp->currentOrder[i+1]]);
}
}
tsp->changedCost=0;
for(i=0;i<N;i++){
if(i==N-1){
tsp->changedCost+= CalcDistance(tsp->city[tsp->changedOrder[i]],tsp->city[tsp->changedOrder[0]]);
}
else{
tsp->changedCost+= CalcDistance(tsp->city[tsp->changedOrder[i]],tsp->city[tsp->changedOrder[i+1]]);
}
}
}
/*
* 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 currentOrder[N];
int changedOrder[N];
int i;
int x1,x2;
/* 変形前の(現在の)巡回路を表示 */
for(i=0;i<N;i++){
printf("C%-2d > ",currentOrder[i]+1);
}
printf("C%-2d current cost=%7.1f\n",currentOrder[0]+1,tsp->currentCost);
/* x1,x2をキーボードから入力 */
printf("enter x1,x2\n");
printf("x1=");scanf("%d",&x1);
printf("x2=");scanf("%d",&x2);
/* TwoOpt関数の呼び出し */
TwoOpt(currentOrder,changedOrder, x1,x2);
/* 変形後の巡回路を表示 */
printf("changed order\n");
for(i=0;i<N;i++){
printf("C%-2d > ",changedOrder[i]+1);
}
printf("C%-2d changed cost=%7.1f\n",changedOrder[0]+1,tsp->changedCost);
/* UpdateOrder関数の呼び出し */
UpdateOrder(tsp,x1,x2);
}
[/code]
[実行結果]
[code]
Cities location:
C1 : 63, 95
C2 : 88, 48
C3 : 51, 21
C4 : 41, 64
C5 : 3, 32
current order
C1 > C2 > C3 > C4 > C5 > C1 current cost=-118815798519092436377119227904.0
enter x1,x2
x1=1
x2=4
(lldb)
[/code]