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

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
kuu
記事: 6
登録日時: 3年前

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

#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) 

kuu
記事: 6
登録日時: 3年前

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

#2

投稿記事 by kuu » 3年前

実行結果にミスがありました。こちらです。
[実行結果]

コード:

 
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=3
changed order
C1  > C4  > C3  > C2  > C5  > C1  changed cost=    0.0
Program ended with exit code: 0 

Meta3

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

#3

投稿記事 by Meta3 » 3年前

cities05.csv データ提示すること!

コード:

c:\b>cl c1.c
Microsoft(R) C/C++ Optimizing Compiler Version 19.26.28806 for x86
Copyright (C) Microsoft Corporation.  All rights reserved.

c1.c
Microsoft (R) Incremental Linker Version 14.26.28806.0
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:c1.exe
c1.obj

c:\b>c1
Can't open data file.
Cities location:
C1  : 20445928,33925178
C2  : 20445944,20445936
C3  : 1966599572,3604928
C4  : 4000,   0
C5  : 20445960,3520986
current order
C1  > C2  > C3  > C4  > C5  > C1  current cost=    0.0
enter x1,x2
x1=

kuu
記事: 6
登録日時: 3年前

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

#4

投稿記事 by kuu » 3年前

申し訳ないのですが,csvファイルの添付方法がわかりません...。
追記:環境はmacOSのXcodeです。

Meta3

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

#5

投稿記事 by Meta3 » 3年前

普通に テキスト ファイルでいいですよ。コピペしてもらえば

エクセルでも開けるでしょう

kuu
記事: 6
登録日時: 3年前

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

#6

投稿記事 by kuu » 3年前

63 95
88 48
51 21
41 64
3 32
よろしくお願いいたします。

Meta3

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

#7

投稿記事 by Meta3 » 3年前

63 95
88 48
51 21
41 64
3 32

これは csv ではありませんね
,で区切られてないし
都市情報がないし
これが正しくないと動きがでたらめになります
csv をメモ帳のようなもので開いてみて

kuu
記事: 6
登録日時: 3年前

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

#8

投稿記事 by kuu » 3年前

添付できました。
添付ファイル
cities05.csv
(34 バイト) ダウンロード数: 103 回

Meta3

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

#9

投稿記事 by Meta3 » 3年前

63,95
88,48
51,21
41,64
3,32

が正しい値でした

kuu
記事: 6
登録日時: 3年前

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

#10

投稿記事 by kuu » 3年前

総移動距離が正しく計算、表示されない理由を教えていただけますでしょうか。

Meta3

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

#11

投稿記事 by Meta3 » 3年前

Windows10 VisualStudio2019ではこうなりました

コード:

c:\b>c

c:\b>cl c1.c
Microsoft(R) C/C++ Optimizing Compiler Version 19.26.28806 for x86
Copyright (C) Microsoft Corporation.  All rights reserved.

c1.c
Microsoft (R) Incremental Linker Version 14.26.28806.0
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:c1.exe
c1.obj

c:\b>
c:\b>c1
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=    0.0
enter x1,x2
x1=1
x2=3
changed order
C1  > C4  > C3  > C2  > C5  > C1  changed cost=    0.0

c:\b>
208行もあるのでエラーもないのでアルゴリズムからみるのはむつかしいですね
詳しいひとが回答くださるでしょう
(ところで自作されたならおかしい所が絞り込み1つずつ解決しないといけませんね)

返信

“C言語何でも質問掲示板” へ戻る