- ベストアンサー
巡回セールスマン問題の考え方を使って最短経路を求める方法について教えてください
stomachmanの回答
No.11訂正です。名前がだぶっちゃってますね。 > routeに沿った各交差点間の距離の表示をしたいのなら、routeのたとえば > 右隣に20行1列のエリア"road"を作り、関数putResultの末尾に > With Range("road") この"road"は全部別の名前、例えば"length"に訂正！！ （ひとりで10回以上回答してしまった。アホですね。）
関連するQ&A
- 巡回セールスマン問題を使って・・・
以前、この場で巡回セールスマン問題の考え方を使って、ということで質問に答えていただきました。その節はありがとうございました。 建築の学生なのですが、卒論の対象地の一つの分析として次のようなことを行っております。 対象地に1４の交差点があって 「１４の交差点全てを一筆書きで、最短経路で通過したい。」 ということをやるようになってます。 これに関して数人の方の協力でプログラムを組んでもらいました。 現在のプログラムはスタートのみ固定して、１４それぞれ最短経路を探索し、ルートと最短距離を表示します。 今度はこれを、スタートとゴールともに固定して 「スタートが交差点１で、ゴールが交差点14のとき ルートは・・。最短距離は何ｍ。」 というふうに表示させたいのですが、プログラムに関して私はまったく素人でどのように変更すればよいかわかりません。 そこで、どのように改良すればよいか教えていただけないでしょうか。 よろしくお願いします。 文字数の関係で、プログラムをのせれないのでお答えになってくださったときにお礼の場でプログラムをお見せすることができます。
- 締切済み
- Visual Basic
- 巡回セールスマン問題を使って・・・
すいません。数学に関してまったくの素人です。 建築の学生なのですが、卒論の対象地の一つの分析として次のようなことを行っております。 「対象地に12の交差点があって １．この交差点全てを最短経路でまわりたい。（スタートとゴールがいっしょ。） ２．交差点全てを最短経路で通過したい。（スタートとゴールはちがう） ということをやるようになってます。 １．に関しては巡回セールスマン問題の分岐限定法でパズル的にとけばいいのでしょうか？ ２．に関してはまったくわかりません。そもそもどのようにスタートとゴールを設定すればいいのか・・・ また上記のような場合に適応できるプログラムは出回っているのでしょうか？もしくは自分で作れるものなのでしょうか？プログラムに関してもまったく素人です。 このように質問ばかりですいません。書いてあることでわからないことがあれば、言ってください。わかるかたご教授ください。お願いします。
- ベストアンサー
- 数学・算数
- 巡回セールスマン問題の類似問題
卒業研究の題材で巡回セールスマン問題をあつかっていて、解法に困ってます。巡回セールスマン問題の定義は「完全グラフにおいて全ての都市を回り、始点にもどってくる最短経路を探す問題」だと思うのですが、私の研究室の教授が、完全グラフ（すべての都市に道が繋がっているグラフ）ではなく、道の決まってるグラフで、しかも始点に戻ってくる必要のないグラフで考えるようにいわれました。確かに現実問題として全ての家に道が繋がっているケースは考えられません。たとえば、世界の全ての空港を最短距離で巡ろうとしたとき、今いる国からいけるところといけないところがあるのと同じです。 ただ、この場合の解法として、巡回しなくてもよいといっても完全グラフではないのでひたすら最短の道を選んでいては解がえられず、ハミルトン経路のように同じ道を２度使ってはいけないという定義でもないので、これもつかえません。この問題はいったいどう定義したらいいものでしょうか？また、このような問題には、すでに解法があるのでしょうか？難しい問題だと思いますが、少しでも解る方、おねがいいたします。
- 締切済み
- 物理学
- 巡回セールスマン問題
このプログラミングを実際に視覚的（探索している状況など）に表したいんですが、どのようにすべきなのでしょうか？ いろいろ参考書を見たのですが、わかりませんでした。 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
- 最短距離を求める問題（ダイクストラ法）の原理
グラフ（経路）の情報があり、それを用いて最短距離を探索するアルゴリズムにダイクストラ法というものがあります。 このアルゴリズムでは常に正しい解を導けるということなのでしょうか。調べてみると負の距離があったらダメというのがありましたが、これは除外しての話ですが。 また、このアルゴリズムがなぜ正しいだろうと思えるのかについて理解できればなんとなくわかるような気がします。そこで、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#
- 最短経路を計算するプログラム
下の図のようなものを用いて、スタート（S）からゴール（G）までいく最短経路を計算するプログラムをVisual Studio 2005のC++で作ったアルゴリズムが知りたいです。
- 締切済み
- C・C++・C#
- プログラム仕様について
ダイクストラを用いて最短経路探索のプログラムをＪＡＶＡで作ろうとしているのですが、肝心なプログラム仕様書及びフローチャートが書けません。 どなたかお力おかしください
- 締切済み
- その他([技術者向] コンピューター)
- 最長経路探索
グラフの最長経路(クリティカルパス)を求めたいのですが、 ・閉路無し有向グラフ ・重み付きグラフ（辺ではなくノードの方に重みがある） ・スタートとゴールのノードが各々1つ与えられている ・スタートからどの経路を辿ってもゴールには辿り着く 以上のような条件の時に、どのようなアルゴリズムを用いれば良いのでしょうか？ 幅優先探索で求められそうな気がしたのですが、どうも上手くいきません。 言語はVBAで、そもそも詳しくないのですが、 考え方など教えて頂けないでしょうか。 お願い致します。
- ベストアンサー
- その他（プログラミング・開発）
お礼
stomachmanさん本当にありがとうございました。 卒論の作業でお礼をするのが遅くなってしまいました。