質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.44%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

0回答

456閲覧

2opt法で経路順が変わらない

RTG143

総合スコア0

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

0グッド

0クリップ

投稿2022/11/28 08:08

前提

TSPにおいて2opt法を用いて解きます。
NN法で出力した経路順で2opt法を適応します。

発生している問題・エラーメッセージ

->13->4->3->10->11->2->1->5->7->8->12->9->14->6-> path length= 3.795572 8->7->5->1->2->11->10->3->4->13->0->6->14->9->12-> path length= 3.795572

上の順列がNN法
下が2opt法です。

これをプロットしても同じグラフで,改良されていません。

該当のソースコード

C

1void two_opt(int p[], double d[N][N], int n) 2{ 3 int i, j, k, dif, temp; 4 5 6 7 for (i = 1; i < n+1; i++) { 8 for (j = i+2; j <i + n-1 ; j++) { 9 dif = ( d[p[i%n]][p[(i+1)%n]] + d[p[j%n]][p[(j+1)%n]] ) 10 - (d[p[i%n]][p[j%n]] + d[p[(i+1)%n]][p[(j+1)%n]]); 11 if (dif > 0) { 12 13 for (k = 0; k <(j-i)/2; k++) { 14 15 temp = p[(i+1+k)%n]; 16 p[(i+1+k)%n] = p[(j-k)%n]; 17 p[(j-k)%n] = temp; 18 } return; 19 20 } 21 } 22 } 23} 24 25void NN(int p[], double d[N][N], int n){ 26 27 28int min_ind,visited[n]; 29int i,j; 30 31for(i=0; i < n; i++){ 32 visited[i] = 0; //初期化 33 } 34 int k = 0; 35 36for(i=0; i < n; i++){ 37 p[i] = k; // 38 visited[k] = 1; //訪問済み 39 double min = 10000;//十分に大きい値 40 for(j=0; j < n; j++){ 41 if (visited[j] == 0 && d[k][j] < min) { 42 min = d[k][j]; 43 min_ind = j; 44 } 45 } k = min_ind; 46 } 47}

http://aok.blue.coocan.jp/joho/sw18apm2.html
こちらのサイトを参考にかいてみました。
2opt法のアルゴリズムも理解しているつもりなのですが,どこが間違っているのか教えていただきたいです。
ノード数を増やしての実行も行いましたが、改良されていなかったです。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

jimbe

2022/11/28 09:33

前の質問はどうなったのでしょうか。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだ回答がついていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.44%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問