- ベストアンサー
巡回セールスマン問題を使って・・・
kony0の回答
- kony0
- ベストアンサー率36% (175/474)
２．について、とりあえず答えを出したいだけだったら。。。 節点が１２個しかないですし、スタートとゴールの選び方はたかだか６６通り。 で、スタートとゴールの２点と距離０の枝で結ぶダミー節点をもうけて、そのダミーを出発点とする巡回セールスマン問題を解くというのを６６回やって、そのうちの最短なものを選べば、一応答えが出そうな気がします。 ＃アドバイスにもならないなぁ、こんな力業じゃ。^^;
関連するQ&A
- 巡回セールスマン問題の考え方を使って・・・。
以前、この場で巡回セールスマン問題の考え方を使って、ということで質問に答えていただきました。その節はありがとうございました。 建築の学生なのですが、卒論の対象地の一つの分析として次のようなことを行っております。 対象地に1４の交差点があって 「１４の交差点全てを一筆書きで、最短経路で通過したい。」 ということをやるようになってます。 これに関して数人の方の協力でプログラムを組んでもらいました。 現在のプログラムはスタートのみ固定して、１４それぞれ最短経路を探索し、ルートと最短距離を表示します。 今度はこれを、スタートとゴールともに固定して 「スタートが交差点１で、ゴールが交差点14のとき ルートは・・。最短距離は何ｍ。」 というふうに表示させたいのですが、プログラムに関して私はまったく素人でどのように変更すればよいかわかりません。 そこで、どのように改良すればよいか教えていただけないでしょうか。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 巡回セールスマン問題を使って・・・
以前、この場で巡回セールスマン問題の考え方を使って、ということで質問に答えていただきました。その節はありがとうございました。 建築の学生なのですが、卒論の対象地の一つの分析として次のようなことを行っております。 対象地に1４の交差点があって 「１４の交差点全てを一筆書きで、最短経路で通過したい。」 ということをやるようになってます。 これに関して数人の方の協力でプログラムを組んでもらいました。 現在のプログラムはスタートのみ固定して、１４それぞれ最短経路を探索し、ルートと最短距離を表示します。 今度はこれを、スタートとゴールともに固定して 「スタートが交差点１で、ゴールが交差点14のとき ルートは・・。最短距離は何ｍ。」 というふうに表示させたいのですが、プログラムに関して私はまったく素人でどのように変更すればよいかわかりません。 そこで、どのように改良すればよいか教えていただけないでしょうか。 よろしくお願いします。 文字数の関係で、プログラムをのせれないのでお答えになってくださったときにお礼の場でプログラムをお見せすることができます。
- 締切済み
- Visual Basic
- 巡回セールスマン問題の類似問題
卒業研究の題材で巡回セールスマン問題をあつかっていて、解法に困ってます。巡回セールスマン問題の定義は「完全グラフにおいて全ての都市を回り、始点にもどってくる最短経路を探す問題」だと思うのですが、私の研究室の教授が、完全グラフ（すべての都市に道が繋がっているグラフ）ではなく、道の決まってるグラフで、しかも始点に戻ってくる必要のないグラフで考えるようにいわれました。確かに現実問題として全ての家に道が繋がっているケースは考えられません。たとえば、世界の全ての空港を最短距離で巡ろうとしたとき、今いる国からいけるところといけないところがあるのと同じです。 ただ、この場合の解法として、巡回しなくてもよいといっても完全グラフではないのでひたすら最短の道を選んでいては解がえられず、ハミルトン経路のように同じ道を２度使ってはいけないという定義でもないので、これもつかえません。この問題はいったいどう定義したらいいものでしょうか？また、このような問題には、すでに解法があるのでしょうか？難しい問題だと思いますが、少しでも解る方、おねがいいたします。
- 締切済み
- 物理学
- 巡回セールスマン問題
このプログラミングを実際に視覚的（探索している状況など）に表したいんですが、どのようにすべきなのでしょうか？ いろいろ参考書を見たのですが、わかりませんでした。 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
- 巡回セールスマン問題
巡回セールスマン問題の解を求めるプログラムを作ったのですが、これでは全ての回路が表示されてしまいます。最小値だけでしかも順列の最初の値が０の回路だけを表示させるにはどうすればいいのでしょうか？どなたか教えてください。長くてすいません。 #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; /* 命令文を追加する */ } } } }
- 締切済み
- C・C++・C#
- 最短経路を計算するプログラム
下の図のようなものを用いて、スタート（S）からゴール（G）までいく最短経路を計算するプログラムをVisual Studio 2005のC++で作ったアルゴリズムが知りたいです。
- 締切済み
- C・C++・C#
- 最短距離を求める問題（ダイクストラ法）の原理
グラフ（経路）の情報があり、それを用いて最短距離を探索するアルゴリズムにダイクストラ法というものがあります。 このアルゴリズムでは常に正しい解を導けるということなのでしょうか。調べてみると負の距離があったらダメというのがありましたが、これは除外しての話ですが。 また、このアルゴリズムがなぜ正しいだろうと思えるのかについて理解できればなんとなくわかるような気がします。そこで、wikipediaを読んでみたのですが、さっぱり分かりませんでした。ちょっと引用します。 ”最短経路問題は、ビー玉と紐を用いて解くことが出来る。 まずビー玉を頂点、紐を辺にするグラフを工作する。 グラフを板の上に置き、スタートの頂点にあたるビー玉だけをつまむ。 グラフが置かれている板を取り除くと、グラフは自由落下を始めるが、 スタートにあたるビー玉を持っているので、スタート地点から近いビー玉から順に落下が止まる。 ゴールにあたるビー玉が止まったとき、ゴールにあたるビー玉はスタートにあたるビー玉まで紐で一直線で結ばれている。 この直線が最短経路である。” ビー玉が経路の構成点で紐が経路なのかなということはわかりますが、それを板の上にのせて板がを取り除く、あたりから何が何だかさっぱりわかりません。板は水平に置かれているなら板が消えたら全部落下するだけのように思えますし。でもこれが理解できるとアルゴリズムの思想が理解でき、その妥当性とか限界について予想がつくのだろうと思います。 他に何かイメージがつかみやすい説明があるでしょうか。 また、ダイクストラ法は情報処理としては初等的なものなのでしょうか。それとも結構アドバンスドなものなのでしょうか。 サンプルプログラムを調べてみたらC・C++が多いようなのでこちらにお尋ねしてみました。 よろしくお願いします。
- 締切済み
- C・C++・C#
- 経路探索
よろしくお願いします。 現在経路探索問題のプログラムを書いています。 そこでわからない点があったので教えてください。 以下のような(n行,m列)の経路があります。 (0,0)－(0,1)－(0,2)－(0,3) (1,0)－(1,1)－(1,2)－(1,3) (2,0)－(2,1)－(2,2)－(2,3) (3,0)－(3,1)－(3,2)－(3,3) (4,0)－(4,1)－(4,2)－(4,3) スタートを(4,3)としてゴール(0,0)にたどり着く全ての経路を求めたいです。 条件としてある点から 左(例えば(4,3)⇒(4,2)) 上(例えば(4,3)⇒(3,3)) 斜め(例えば(4,3)⇒(3,2)) にしか進むことはできません。 このような仕様のアルゴリズムはどのように書けばよいのでしょうか？？ ご解答要路しくお願いします。
- ベストアンサー
- C・C++・C#
- 巡回セールスマン問題
巡回セールスマン問題を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
- 巡回セールスマン問題について
巡回セールスマン問題のプログラムの作成をしたいのですが、どのように組めばいいのか、さっぱりわかりません。 解説付きで、そのまま実行も出来るプログラムが書いてあるページはないですか。教えてください。
- 締切済み
- C・C++・C#
お礼
kony0さんありがとうございます。 ダミー節点の話は、なんとなくはわかります。ありがとうございました。 お礼が遅くなってすいませんでした。 現在、身近にプログラムに詳しい人を頼りつつ、なんとか解決しようとしている日々です。 nintai