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

タイトルにあるプログラムを書いたときに，予期せぬ結果になってしまうので，
どこがどのように違うのか，どうすればよいのかを教えていただきたいです．
申し訳ないのですが見ていただけたら嬉しいです．

コンパイルでエラーはでません．
文字数が足りないので，求める結果と現在の結果は補足に載せます．

以下，ソースコード

#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;
}

/*
* 都市座標データ読み込み
*/
void ReadData(struct TSP *tsp)
{
/* ファイルオープン */
FILE* fp = fopen("cities05.csv", "r");
if (fp == NULL) {
printf("Can't open data file.\n");
}

/* データ読み込み */
int i;
for (i = 0; i < N; i++) {
fscanf(fp, "%d,%d\n", &tsp->city[i].x, &tsp->city[i].y);
}
fclose(fp);
}

/*
* 都市座標データ表示
*/
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関数
*/
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];
}
}

/*
*現在の巡回順
*/
void currentOrder(struct TSP *tsp)
{
int currentOrder[N];
int i;
for (i = 0; i < N; i++) {
currentOrder[i] = i;
}
}

/*
* 総移動距離を計算する
*/
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]]);
}
}
}

/*
* ２都市間の距離を計算
* 引数：struct City a : 都市1
* 引数：struct City b : 都市2
* 戻り値：距離
*/
float CalcDistance(struct City a, struct City b)
{
float distance;
distance += sqrt(pow((a.x - b.x), 2) + pow((a.y - b.y), 2));
return distance;
}

/*
* 巡回順と総移動距離を表示
*/
void ShowCost(struct TSP *tsp)
{
int i;
int x1, x2;
int currentOrder[N], changedOrder[N];

/* x1, x2 のキーボード入力 */
printf("Please enter x1 and x2\n");
printf("x1 = ");
scanf("%d", &x1);
printf("x2 = ");
scanf("%d", &x2);

printf("Current order: ");
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);

TwoOpt(currentOrder, changedOrder, x1, x2);

printf("Changed order: ");
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);
}

質問者からの補足コメント

• 以下，現在の実行結果
  
  Cities location:
  C1 : 63, 95
  C2 : 88, 48
  C3 : 51, 21
  C4 : 41, 64
  C5 : 3, 32
  Please enter x1 and x2
  x1 = 2
  x2 = 4
  Current order: C-2051296927> C32622> C-524644367> C32768> C1 > C-2051296927 Current cost = -107548773851374551040.0
  Changed order: C-2051296927> C32622> C1 > C32768> C-524644367> C-2051296927 Changed cost = 0.0
  Segmentation fault (core dumped)

    補足日時：2021/01/31 13:11

• 以下，求める実行結果
  Current order: , Changed order: のところは，全ての都市を一回ずつ回るようにしたいです．
  
  Cities location:
  C1 : 63, 95
  C2 : 88, 48
  C3 : 51, 21
  C4 : 41, 64
  C5 : 3, 32
  Please enter x1 and x2
  x1 = 2
  x2 = 4
  Current order: C1> C2> C3> C4> C5 > C1 Current cost= 279.9
  Changed order: C1> C4> C5 > C3> C2> C1 Changed cost = 236.0

    補足日時：2021/01/31 13:48

No.5 回答者： Tacosan 回答日時： 2021/02/02 00:28

「２つ目」の方はちょくちょくやらかすやつがいる. ただ, 冷静になって考えてほしいんだが,

tsp->currentOrder[N]
ってなにかおかしいと思わない?

「１つ目」は正直
なにをどう考えてそう書いたのか
がわかんない. そういう書き方, どこにありました?

あ, TSP って構造体のメンバー, どういう意味を持たせてます?

No.4 回答者： Tacosan 回答日時： 2021/01/31 23:48

その関数についてはそんなふう. 他にも直すべきところはあるけどね.

この回答へのお礼

なるほど！ありがとうございます．
早速直してみたのですが，コンパイルしたとき，３つエラーが出る場所がありました．
どう改善すればよいのかわからなかったので，申し訳ないのですが教えていただけないでしょうか．

1つ目のは，全く見当がつきません．

２つ目は，
void ShowCost
の部分の
TwoOpt
の()内の始め2つの引数の型が違うと言われていると思っています．
tsp.currentOrder[N]
など試したのですが，
どう変えればいいのか教えていただけませんか．

以下，エラー内容になります．

１つ目
error: expected ‘;’, ‘,’ or ‘)’ before ‘->’ token
void TwoOpt(const int tsp->currentOrder[N], int tsp->changedOrder[N], int x1, int x2)

２つ目
In function ‘ShowCost’:
warning: passing argument 1 of ‘TwoOpt’ makes pointer from integer without a cast [-Wint-conversion]
TwoOpt(tsp->currentOrder[N], tsp->changedOrder[N], x1, x2);
| ~~~~~~~~~~~~~~
| |
| int
note: expected ‘const int *’ but argument is of type ‘int’

void TwoOpt(const int currentOrder[N], int changedOrder[N], int x1, int x2);

３つめは２つ目に似ていて，次数が足りないので省略させていただきます．

恐れ入りますが，お返事いただければ幸いです．

お礼日時：2021/02/01 00:53

No.3 回答者： Tacosan 回答日時： 2021/01/31 23:28

そんなことは聞いていない.

「引数」がなにか, わかっていますか?

ちなみに同じようなミスを他にも数カ所でしてる.

この回答へのお礼

お返事ありがとうございます。

引数についてですが、以下のプログラムだとしたら、
*tspの部分で、
関数内で*tspが出てきたら、他の関数からこの部分を代入(？)する、という感じだと思っています。

void currentOrder(struct TSP *tsp)
{
int currentOrder[N];
int i;
for (i = 0; i < N; i++) {
currentOrder[i] = i;
}
}

考えてみたのですが、以下のようにする、ということでしょうか。

void currentOrder(struct TSP *tsp)
{
int i;
for (i = 0; i < N; i++) {
tsp->currentOrder[i] = i;
}
}

お礼日時：2021/01/31 23:40

No.2 回答者： Tacosan 回答日時： 2021/01/31 19:08

「だと思います」ってどういうこと? 誰かに作ってもらっただけで, あなたは関与していないと?

その関数, どこで引数を使ってる?

この回答へのお礼

迅速なご返信ありがとうございます。
すみません、言い方に関してはそんなに意識をしていませんでした。
学校の課題で、プログラムの型のようなものを渡されて、そこに自分で書き加える、という形なのですが、
自分がそのような認識であるという意味でした。

どこで使う、というのは、この関数が他のどの関数内で使われているか、ということでしょうか。

お礼日時：2021/01/31 19:13

No.1 回答者： Tacosan 回答日時： 2021/01/31 18:18

その currentOrder って関数, なにしてるの?

この回答へのお礼

ご返信ありがとうございます！

最初の巡回順が
C1>C2>C3>C4>C5>C1
になるようにしている関数だと思います！

お礼日時：2021/01/31 18:43