- ベストアンサー
巡回セールスマン問題を解くプログラム
インターネット上でTSP問題（巡回セールスマン問題)を解くプログラムを探しているんですが何かいいのないでしょうか？ おねがいします。
- god_god_god
- お礼率42% (14/33)
- 数学・算数
- 回答数1
- ありがとう数4
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
アルゴリズムは何でも良いのでしょうか？ 遺伝的アルゴリズム(GA)を利用するものですと、MSのサイトにサンプルがあります。図表も多く、結構分かりやすいです。 アルゴリズム入門 : 第 5 章 知識情報処理入門 http://www.microsoft.com/japan/msdn/academic/Articles/Algorithm/05/
関連するQ&A
- 巡回セールスマン問題について
巡回セールスマン問題のプログラムをＣ言語で作らないといけないのですが、どう作ればよくわかりません。 巡回セールスマン問題のＣ言語プログラムのソースがあるページを知っていたら教えてください。
- 締切済み
- C・C++・C#
- 巡回セールスマン問題について
巡回セールスマン問題のプログラムの作成をしたいのですが、どのように組めばいいのか、さっぱりわかりません。 解説付きで、そのまま実行も出来るプログラムが書いてあるページはないですか。教えてください。
- 締切済み
- C・C++・C#
- 巡回セールスマン問題
研究室の教授に、「巡回セールスマン問題をC言語で書いてこい」と言われました。まったく何もわかりません。巡回セールスマン問題とは何か、と言うことは大体ネットなど使ってわかりました。C言語は基本的なことは書けます。初心者の僕は何から始めればいいでしょうか？？また、オススメの書籍などありましたら教えていただけませんか？よろしくお願いします。
- 締切済み
- C・C++・C#
- 巡回セールスマン問題を使って・・・
すいません。数学に関してまったくの素人です。 建築の学生なのですが、卒論の対象地の一つの分析として次のようなことを行っております。 「対象地に12の交差点があって １．この交差点全てを最短経路でまわりたい。（スタートとゴールがいっしょ。） ２．交差点全てを最短経路で通過したい。（スタートとゴールはちがう） ということをやるようになってます。 １．に関しては巡回セールスマン問題の分岐限定法でパズル的にとけばいいのでしょうか？ ２．に関してはまったくわかりません。そもそもどのようにスタートとゴールを設定すればいいのか・・・ また上記のような場合に適応できるプログラムは出回っているのでしょうか？もしくは自分で作れるものなのでしょうか？プログラムに関してもまったく素人です。 このように質問ばかりですいません。書いてあることでわからないことがあれば、言ってください。わかるかたご教授ください。お願いします。
- ベストアンサー
- 数学・算数
- 巡回セールスマン問題の考え方を使って・・・。
以前、この場で巡回セールスマン問題の考え方を使って、ということで質問に答えていただきました。その節はありがとうございました。 建築の学生なのですが、卒論の対象地の一つの分析として次のようなことを行っております。 対象地に1４の交差点があって 「１４の交差点全てを一筆書きで、最短経路で通過したい。」 ということをやるようになってます。 これに関して数人の方の協力でプログラムを組んでもらいました。 現在のプログラムはスタートのみ固定して、１４それぞれ最短経路を探索し、ルートと最短距離を表示します。 今度はこれを、スタートとゴールともに固定して 「スタートが交差点１で、ゴールが交差点14のとき ルートは・・。最短距離は何ｍ。」 というふうに表示させたいのですが、プログラムに関して私はまったく素人でどのように変更すればよいかわかりません。 そこで、どのように改良すればよいか教えていただけないでしょうか。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 巡回セールスマン問題を使って・・・
以前、この場で巡回セールスマン問題の考え方を使って、ということで質問に答えていただきました。その節はありがとうございました。 建築の学生なのですが、卒論の対象地の一つの分析として次のようなことを行っております。 対象地に1４の交差点があって 「１４の交差点全てを一筆書きで、最短経路で通過したい。」 ということをやるようになってます。 これに関して数人の方の協力でプログラムを組んでもらいました。 現在のプログラムはスタートのみ固定して、１４それぞれ最短経路を探索し、ルートと最短距離を表示します。 今度はこれを、スタートとゴールともに固定して 「スタートが交差点１で、ゴールが交差点14のとき ルートは・・。最短距離は何ｍ。」 というふうに表示させたいのですが、プログラムに関して私はまったく素人でどのように変更すればよいかわかりません。 そこで、どのように改良すればよいか教えていただけないでしょうか。 よろしくお願いします。 文字数の関係で、プログラムをのせれないのでお答えになってくださったときにお礼の場でプログラムをお見せすることができます。
- 締切済み
- Visual Basic
- 巡回セールスマン問題の類似問題
卒業研究の題材で巡回セールスマン問題をあつかっていて、解法に困ってます。巡回セールスマン問題の定義は「完全グラフにおいて全ての都市を回り、始点にもどってくる最短経路を探す問題」だと思うのですが、私の研究室の教授が、完全グラフ（すべての都市に道が繋がっているグラフ）ではなく、道の決まってるグラフで、しかも始点に戻ってくる必要のないグラフで考えるようにいわれました。確かに現実問題として全ての家に道が繋がっているケースは考えられません。たとえば、世界の全ての空港を最短距離で巡ろうとしたとき、今いる国からいけるところといけないところがあるのと同じです。 ただ、この場合の解法として、巡回しなくてもよいといっても完全グラフではないのでひたすら最短の道を選んでいては解がえられず、ハミルトン経路のように同じ道を２度使ってはいけないという定義でもないので、これもつかえません。この問題はいったいどう定義したらいいものでしょうか？また、このような問題には、すでに解法があるのでしょうか？難しい問題だと思いますが、少しでも解る方、おねがいいたします。
- 締切済み
- 物理学
- 巡回セールスマン問題: 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; }
- 締切済み
- Java
- 巡回セールスマン問題
このプログラミングを実際に視覚的（探索している状況など）に表したいんですが、どのようにすべきなのでしょうか？ いろいろ参考書を見たのですが、わかりませんでした。 import java.io.*; public class TSP { public static void main(String[] args) { TSP instance = new TSP(); TspPoint[] points = new TspPoint[5]; //コンポーネントの作成 points[0] = new TspPoint("A", 5, 10); points[1] = new TspPoint("B", 4, 2); points[2] = new TspPoint("C", 6, 3); points[3] = new TspPoint("D", 3, 4); points[4] = new TspPoint("E", 2, 7); instance.setPoints(points); instance.traveling(); instance.dispResult(); } private TspPoint[] points; private double min_distance; private int[] min_route; public void setPoints(TspPoint[] points) { this.points = points; } public void traveling() { min_distance = Double.MAX_VALUE; min_route = new int[points.length]; int p1, p2, p3, p4, p5; p1 = 0; for (p2 = 1; p2 < 5; p2++) { for (p3 = 1; p3 < 5; p3++) { for (p4 = 1; p4 < 5; p4++) { for (p5 = 1; p5 < 5; p5++) { if (p1 == p2 || p1 == p3 || p1 == p4 || p1 == p5 || p2 == p3 || p2 == p4 || p2 == p5 || p3 == p4 || p3 == p5 || p4 == p5) { // 重複する地点は対象外 } else { // p1→p2→p3→p4→p5→p1への巡回経路長を求める double distance = 0.0; distance += calcDistance(points[p1], points[p2]); distance += calcDistance(points[p2], points[p3]); distance += calcDistance(points[p3], points[p4]); distance += calcDistance(points[p4], points[p5]); distance += calcDistance(points[p5], points[p1]); if (distance < min_distance) { // 現在のところの最短経路を覚えておく min_route[0] = p1; min_route[1] = p2; min_route[2] = p3; min_route[3] = p4; min_route[4] = p5; // 最短距離を記憶する min_distance = distance; } } } } } } } public void dispResult() { System.out.print("最小の巡回経路は "); for (int i = 0; i < 5; i++) { System.out.print(points[min_route[i]].toString() + " → "); } System.out.println(points[min_route[0]].toString()); System.out.println("巡回経路長は " + min_distance); } public double calcDistance(TspPoint a, TspPoint b) { double temp; temp = (a.getX() - b.getX()) * (a.getX() - b.getX()) + (a.getY() - b.getY()) * (a.getY() - b.getY()); return Math.sqrt(temp); //平方根を返す } } class TspPoint { private String name; private int x; private int y; public TspPoint(String name, int x, int y) { this.name = name; this.x = x; this.y = y; } public String getName() { return name; } public int getX() { return x; } public int getY() { return y; } public String toString() { return name + "(" + x + "," + y + ")"; } }
- 締切済み
- Java
お礼
ありがとうございます！わかりやすいです。 探してたもんです