巡回セールスマン問題を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);
}
というふうに実装しています。
解答いただけるとありがたいです…
巡回セールスマン問題or-opt法について
Re: 巡回セールスマン問題or-opt法について
なにがしかの回答を得るためには、情報が不足しているようです。46 さんが書きました:巡回セールスマン問題をor-opt法のアルゴリズムを用いてとこうとしているのですが、振動してしまいうまくいきません。
コードは
というふうに実装しています。
提示されたコードだけでは、回答しようとする側の環境でビルドできません。
main関数など、ビルドするための他の情報が必要です。
また、提示された関数のコードにコメントがないため、
各変数の意味や処理の内容がすぐにはわかりません。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。
プログラムは思ったとおりには動かない。書いたとおりに動く。
Re: 巡回セールスマン問題or-opt法について
だとすると、そもそも「振動してしまう」の意味がよくわかりませんし、46 さんが書きました:コード数が多くなってしまうため、or-optを実際に行う関数のコードのみ記載しています。
回答しようとする側での再現もできませんので、
的確な回答を得ることは残念ながらむずかしいと思います。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。
プログラムは思ったとおりには動かない。書いたとおりに動く。
Re: 巡回セールスマン問題or-opt法について
私はそのアルゴリズムを知りませんので,
「検索してみた感じだと経路が良くなる場合のみ更新する っぽい
→本来振動し得ないだろうな
→経路の評価をしている部分とかがなんかバグってるんだろうな」
くらいの感想しか抱けません.故にお役には立てませんが…
誰か他の方が有用な回答をできるようにするためには,
あなたの現状コードを全部乗せると長いから無理 という場合でも,
アルゴリズムの実装の部分が怪しいのであれば
問題としている現象が再現される最低限のコードを作って投稿する(例えば,巡回先が非常に少数な例とか)
とか方法があると思います.
また,「何かのアルゴリズムを実装したコード」は,バブルソートくらい簡単なものでもない限り
他人にはそうそう読めないものと思いますので,
本当に他者に見てもらわなければならないのであれば,私だったら丁寧すぎるほどに注釈をつけます.
#そういった作業をやっているうちに,自己解決することもわりとありますしね
「検索してみた感じだと経路が良くなる場合のみ更新する っぽい
→本来振動し得ないだろうな
→経路の評価をしている部分とかがなんかバグってるんだろうな」
くらいの感想しか抱けません.故にお役には立てませんが…
誰か他の方が有用な回答をできるようにするためには,
あなたの現状コードを全部乗せると長いから無理 という場合でも,
アルゴリズムの実装の部分が怪しいのであれば
問題としている現象が再現される最低限のコードを作って投稿する(例えば,巡回先が非常に少数な例とか)
とか方法があると思います.
また,「何かのアルゴリズムを実装したコード」は,バブルソートくらい簡単なものでもない限り
他人にはそうそう読めないものと思いますので,
本当に他者に見てもらわなければならないのであれば,私だったら丁寧すぎるほどに注釈をつけます.
#そういった作業をやっているうちに,自己解決することもわりとありますしね