• 締切済み

巡回セールスマン問題について

巡回セールスマン問題のプログラムの作成をしたいのですが、どのように組めばいいのか、さっぱりわかりません。 解説付きで、そのまま実行も出来るプログラムが書いてあるページはないですか。教えてください。

みんなの回答

  • chie65535
  • ベストアンサー率43% (8514/19356)
回答No.1

参考にどうぞ http://www.e.yamagata-u.ac.jp/~sakai/HOME_PAGE/H8/mitsugi/SOTU/index.htm ネット検索すれば、もっと色々と見付かります。

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • 巡回セールスマン問題について

    巡回セールスマン問題のプログラムをＣ言語で作らないといけないのですが、どう作ればよくわかりません。 巡回セールスマン問題のＣ言語プログラムのソースがあるページを知っていたら教えてください。

  • 巡回セールスマン問題を解くプログラム

    インターネット上でTSP問題（巡回セールスマン問題)を解くプログラムを探しているんですが何かいいのないでしょうか？ おねがいします。

  • 巡回セールスマン問題

    研究室の教授に、「巡回セールスマン問題をC言語で書いてこい」と言われました。まったく何もわかりません。巡回セールスマン問題とは何か、と言うことは大体ネットなど使ってわかりました。C言語は基本的なことは書けます。初心者の僕は何から始めればいいでしょうか？？また、オススメの書籍などありましたら教えていただけませんか？よろしくお願いします。

  • 巡回セールスマン問題を使って・・・

    すいません。数学に関してまったくの素人です。 建築の学生なのですが、卒論の対象地の一つの分析として次のようなことを行っております。 「対象地に12の交差点があって １．この交差点全てを最短経路でまわりたい。（スタートとゴールがいっしょ。） ２．交差点全てを最短経路で通過したい。（スタートとゴールはちがう） ということをやるようになってます。 １．に関しては巡回セールスマン問題の分岐限定法でパズル的にとけばいいのでしょうか？ ２．に関してはまったくわかりません。そもそもどのようにスタートとゴールを設定すればいいのか・・・ また上記のような場合に適応できるプログラムは出回っているのでしょうか？もしくは自分で作れるものなのでしょうか？プログラムに関してもまったく素人です。 このように質問ばかりですいません。書いてあることでわからないことがあれば、言ってください。わかるかたご教授ください。お願いします。

  • 巡回セールスマン問題の考え方を使って・・・。

    以前、この場で巡回セールスマン問題の考え方を使って、ということで質問に答えていただきました。その節はありがとうございました。 建築の学生なのですが、卒論の対象地の一つの分析として次のようなことを行っております。 対象地に1４の交差点があって 「１４の交差点全てを一筆書きで、最短経路で通過したい。」 ということをやるようになってます。 これに関して数人の方の協力でプログラムを組んでもらいました。 　 現在のプログラムはスタートのみ固定して、１４それぞれ最短経路を探索し、ルートと最短距離を表示します。 今度はこれを、スタートとゴールともに固定して 「スタートが交差点１で、ゴールが交差点14のとき 　ルートは・・。最短距離は何ｍ。」 というふうに表示させたいのですが、プログラムに関して私はまったく素人でどのように変更すればよいかわかりません。 そこで、どのように改良すればよいか教えていただけないでしょうか。 よろしくお願いします。

  • 巡回セールスマン問題を使って・・・

    以前、この場で巡回セールスマン問題の考え方を使って、ということで質問に答えていただきました。その節はありがとうございました。 建築の学生なのですが、卒論の対象地の一つの分析として次のようなことを行っております。 対象地に1４の交差点があって 「１４の交差点全てを一筆書きで、最短経路で通過したい。」 ということをやるようになってます。 これに関して数人の方の協力でプログラムを組んでもらいました。 　 現在のプログラムはスタートのみ固定して、１４それぞれ最短経路を探索し、ルートと最短距離を表示します。 今度はこれを、スタートとゴールともに固定して 「スタートが交差点１で、ゴールが交差点14のとき 　ルートは・・。最短距離は何ｍ。」 というふうに表示させたいのですが、プログラムに関して私はまったく素人でどのように変更すればよいかわかりません。 そこで、どのように改良すればよいか教えていただけないでしょうか。 よろしくお願いします。 文字数の関係で、プログラムをのせれないのでお答えになってくださったときにお礼の場でプログラムをお見せすることができます。

  • 巡回セールスマン問題の類似問題

    卒業研究の題材で巡回セールスマン問題をあつかっていて、解法に困ってます。巡回セールスマン問題の定義は「完全グラフにおいて全ての都市を回り、始点にもどってくる最短経路を探す問題」だと思うのですが、私の研究室の教授が、完全グラフ（すべての都市に道が繋がっているグラフ）ではなく、道の決まってるグラフで、しかも始点に戻ってくる必要のないグラフで考えるようにいわれました。確かに現実問題として全ての家に道が繋がっているケースは考えられません。たとえば、世界の全ての空港を最短距離で巡ろうとしたとき、今いる国からいけるところといけないところがあるのと同じです。 ただ、この場合の解法として、巡回しなくてもよいといっても完全グラフではないのでひたすら最短の道を選んでいては解がえられず、ハミルトン経路のように同じ道を２度使ってはいけないという定義でもないので、これもつかえません。この問題はいったいどう定義したらいいものでしょうか？また、このような問題には、すでに解法があるのでしょうか？難しい問題だと思いますが、少しでも解る方、おねがいいたします。

  • 巡回セールスマン問題: NPについて

    　NP問題である巡回セールスマン問題について質問です． 　NP問題には，「非決定性チューリングマシンによって多項式時間で解くことができる決定問題」「証拠が与えられれば，その答えがYesであることを(問題の入力サイズに関する)多項式時間以内に確認することができる決定問題」などの定義があります．このふたつめの定義について質問です． 　巡回セールス問題における解を確かめる「証拠」とはいったいどのようなものなのでしょうか?

  • 巡回セールスマン問題

    巡回セールスマン問題をJavaで解きたいのですが、Nearest Neighbor法で初期解を求めるまではできたのですが、その後2-opt法を用いて再計算する段階がうまくいきません。（実行できるのですが、どのような都市配置でも経路変更されません。）　 できれば理由とコードを教えてください。 文字数の関係で2-optによる再計算の部分だけソースコードの載せさせていただきます。 補足：クラスは１つです。 　　　wayに現段階の巡回路(都市番号)が格納されています public ArrayList<Integer> revision(ArrayList<Integer> way){ for (int i = 1; i < way.size(); i++){ int a = way.get(i - 1); int b = way.get(i); for(int j = i+2; j < way.size(); j++){ int c = way.get(j - 1); int d = way.get(j); float before = distance[a][b] + distance[c][d]; float after = distance[a][c] + distance[b][d]; if ( after < before){ ArrayList<Integer> route = new ArrayList<Integer>(); for(int k = 0; k < i; k++){ route.add(way.get(k)); } for(int k = j - 1; k >= i; k--){ route.add(way.get(k)); } for(int k=j; k < way.size(); k++){ route.add(way.get(k)); } //revision(route); } } } System.out.println("更新後way = "+ way); return way; }

  • 巡回セールスマン問題

    巡回セールスマン問題の解を求めるプログラムを作ったのですが、これでは全ての回路が表示されてしまいます。最小値だけでしかも順列の最初の値が０の回路だけを表示させるにはどうすればいいのでしょうか？どなたか教えてください。長くてすいません。 #include<stdio.h> #define MAXN (100) #define YES (1) #define NO (0) void perm(int d); int n, a[MAXN], used[MAXN]; int dist[MAXN][MAXN]; int main(void) { int i; int j; // printf("Input n: "); scanf("%d", &n); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { scanf("%d", &dist[i][j]); } } if (n > MAXN) { printf("Change the value MAXN.\n"); exit(1); } else if (n < 0) { printf("Error!(Input nonnegative integer.)\n"); exit(1); } for (i = 0; i < n; i++) used[i] = NO; /* 始めはどの値も使っていない */ perm(0); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { printf("%2d ", dist[i][j]); } printf("\n"); } } /* 深さdの節点を根とする木を作成する関数 */ void perm(int d) { int i; if (d == n) { for(i = 0; i < n; i++) printf("%d", a[i]); printf("\n"); } else { for (i = 0; i < n; i++) { if (used[i] == NO) { a[d] = i; /* 配列のd番目にiを代入する */ used[i] = YES; /* iを使ったことを記憶する */ perm(d + 1); /* 再帰呼び出し */ used[i] = NO; /* 命令文を追加する */ } } } }

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する