巡回セールスマン問題or-opt法について

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
46

巡回セールスマン問題or-opt法について

#1

投稿記事 by 46 » 6年前

巡回セールスマン問題をor-opt法のアルゴリズムを用いてとこうとしているのですが、振動してしまいうまくいきません。
コードは
void or_opt(void)
{
int temp,diff;
int i,j,k;
int t=0;
int i0,i1;
int j1;
length = 0;

for(i=0;i<n;i++){
length += Dis(tour,tour[i+1]);
}

or_opt:
for(i = t;i<t+n-1;i++){
for(j = i+2; j < t+n-2; j++){

i0 = i-1;
i1 = i+1;

if(i0 < 0) i0 = n-1;
if(i1 == n) i1=0;

for(j = i+2; j < t+n-2; j++){

j1 = j+1;
if(j1 == n) j1 = 0;

int ac = Dis(tour[i0 % n], tour[i1 % n]);
int cb = Dis(tour[i1 % n], tour[i % n]);
int ef = Dis(tour[j % n], tour[j1 % n]);
int ab = Dis(tour[i0 % n], tour[i % n]);
int ec = Dis(tour[j % n], tour[i1 % n]);
int cf = Dis(tour[i1 % n], tour[j1 % n]);

diff = (ac+cb+ef) - (ab+ec+cf);

if(diff < 0 && i!=j && i!=j1){
length = length - diff;
for(k = 0; k < (j-i)/2; k++){

temp = tour[(i+1+k) % n];
tour[(i+1+k) % n] = tour[(j-k) % n];
tour[(j-k) % n] = temp;
}
}else{
i++;
j++;
t++;
break;
}
t = i+1;
goto or_opt;
}
}
}
printf("After_or-opt_length=%d\n",length);
}

というふうに実装しています。
解答いただけるとありがたいです…

box
記事: 1745
登録日時: 9年前

Re: 巡回セールスマン問題or-opt法について

#2

投稿記事 by box » 6年前

46 さんが書きました:巡回セールスマン問題をor-opt法のアルゴリズムを用いてとこうとしているのですが、振動してしまいうまくいきません。
コードは
というふうに実装しています。
なにがしかの回答を得るためには、情報が不足しているようです。
提示されたコードだけでは、回答しようとする側の環境でビルドできません。
main関数など、ビルドするための他の情報が必要です。
また、提示された関数のコードにコメントがないため、
各変数の意味や処理の内容がすぐにはわかりません。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

46

Re: 巡回セールスマン問題or-opt法について

#3

投稿記事 by 46 » 6年前

コード数が多くなってしまうため、or-optを実際に行う関数のコードのみ記載しています。

box
記事: 1745
登録日時: 9年前

Re: 巡回セールスマン問題or-opt法について

#4

投稿記事 by box » 6年前

46 さんが書きました:コード数が多くなってしまうため、or-optを実際に行う関数のコードのみ記載しています。
だとすると、そもそも「振動してしまう」の意味がよくわかりませんし、
回答しようとする側での再現もできませんので、
的確な回答を得ることは残念ながらむずかしいと思います。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

アバター
usao
記事: 1566
登録日時: 6年前

Re: 巡回セールスマン問題or-opt法について

#5

投稿記事 by usao » 6年前

私はそのアルゴリズムを知りませんので,
「検索してみた感じだと経路が良くなる場合のみ更新する っぽい
 →本来振動し得ないだろうな
 →経路の評価をしている部分とかがなんかバグってるんだろうな」
くらいの感想しか抱けません.故にお役には立てませんが…

誰か他の方が有用な回答をできるようにするためには,

 あなたの現状コードを全部乗せると長いから無理 という場合でも,
 アルゴリズムの実装の部分が怪しいのであれば
 問題としている現象が再現される最低限のコードを作って投稿する(例えば,巡回先が非常に少数な例とか)

とか方法があると思います.

また,「何かのアルゴリズムを実装したコード」は,バブルソートくらい簡単なものでもない限り
他人にはそうそう読めないものと思いますので,
本当に他者に見てもらわなければならないのであれば,私だったら丁寧すぎるほどに注釈をつけます.

#そういった作業をやっているうちに,自己解決することもわりとありますしね

閉鎖

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