- 締切済み
巡回セールスマン問題
- みんなの回答 （3）
- 専門家の回答
みんなの回答
- wps_2005
- ベストアンサー率25% (5/20)
「巡回セールスマン問題をC言語で書いてこい」では教授の真意がよくわかりませんね。 巡回セールスマン問題が何なのかは勉強するとして、 ・6都市ぐらいをしらみつぶしで調べるものを書くことが課題? → これなら単なるC言語のプログラミングの課題ですね。 ・もっと大型の問題を解くための近似解算出アルゴリズムを調べることが課題? → こっちだったら、数多くの解法がありますから、プログラミング以前に調査してまとめなきゃいけないことがいろいろとありそうです。 講義での課題ならまだしも、研究室に配属になった方の、指導教官から与えられた課題から発せられた質問としてはどうかなあと思いますが。 巡回セールスマン問題を知りたいのなら、もっとも詳しいのは参考URLの書籍でしょう。
- tatsumi01
- ベストアンサー率30% (976/3185)
No. 1 のものですが補足します。 No. 1 の回答では、二つの都市Ａ、Ｂを結ぶ経路について、Ａ→ＢとＢ→Ａを結ぶコストが同じであることを前提にしていました。そうすると、No. 1 で書いたアルゴリズムはムダをしています（逆周りでも同じコストなのに計算している）。もっとも、この計算量は２倍程度ですから大したことはありません。 コストが非対称のとき（Ａ→ＢとＢ→Ａのコストが違うとき）に、No. 1 のアルゴリズムが成立しますが、(1) で読み込むコストの個数はＮ（Ｎ－１）になります。 問題集に掲載されている問題が対称か非対称かはわかりません。 なお、ホップフィールド型ニューラルネットワークで解く（近似）手法はコスト対称を前提にしていると思います。 また、このカテゴリで「巡回セールスマン」をキーにして検索すると以前の質問・回答が出てきます。中にはＣ言語のプログラムを示した質問もあります（間違っているという指摘もあるようですが）。
- tatsumi01
- ベストアンサー率30% (976/3185)
近似解でなく、厳密解を求められているのでしょうか。 厳密解は恐らく、全ての都市の順列についてコストを計算し最小値を求めるものでしょう。 どこから始めても同じですから、どこかの都市（Ａ）を固定し、Ａから始まる全ての都市の順列を作って、最後にＡに戻る経路を追加します。 (0) 都市数Ｎを入力する (1) 二つの都市を結ぶコスト（Ｎ（Ｎ－１）／２個あります）をファイルから読み込む (2) Ａから始まる都市の順列を一つづつ生成し、最後にＡを追加する (3) (2) で生成した順列で、隣り合う都市のコストを加算し、メモリに格納する (4) (2), (3) を全ての順列について計算し、最小値を求める (5) 最小値と、それを与える順路を出力する 以上で完了です。 なお、この方法だとＮ！のオーダーの計算時間がかかります。Ｎ＝２０程度になったら、１週間近くかかるのではないでしょうか。 また、巡回セールスマン問題については、標準的な問題集（都市数ごとに都市間のコストを書いたテーブル）があり、正解も掲載されているそうです。バグの検出のためには問題集をダウンロードすると良いでしょう。 なお、厳密解ではなくニューラルネットワークで近似解を求めよという問題だったらまた違うアルゴリズムになります。
関連するQ&A
- 巡回セールスマン問題について
巡回セールスマン問題のプログラムをＣ言語で作らないといけないのですが、どう作ればよくわかりません。 巡回セールスマン問題のＣ言語プログラムのソースがあるページを知っていたら教えてください。
- 締切済み
- C・C++・C#
- 巡回セールスマン問題の類似問題
卒業研究の題材で巡回セールスマン問題をあつかっていて、解法に困ってます。巡回セールスマン問題の定義は「完全グラフにおいて全ての都市を回り、始点にもどってくる最短経路を探す問題」だと思うのですが、私の研究室の教授が、完全グラフ（すべての都市に道が繋がっているグラフ）ではなく、道の決まってるグラフで、しかも始点に戻ってくる必要のないグラフで考えるようにいわれました。確かに現実問題として全ての家に道が繋がっているケースは考えられません。たとえば、世界の全ての空港を最短距離で巡ろうとしたとき、今いる国からいけるところといけないところがあるのと同じです。 ただ、この場合の解法として、巡回しなくてもよいといっても完全グラフではないのでひたすら最短の道を選んでいては解がえられず、ハミルトン経路のように同じ道を２度使ってはいけないという定義でもないので、これもつかえません。この問題はいったいどう定義したらいいものでしょうか？また、このような問題には、すでに解法があるのでしょうか？難しい問題だと思いますが、少しでも解る方、おねがいいたします。
- 締切済み
- 物理学
- 巡回セールスマン問題について
巡回セールスマン問題のプログラムの作成をしたいのですが、どのように組めばいいのか、さっぱりわかりません。 解説付きで、そのまま実行も出来るプログラムが書いてあるページはないですか。教えてください。
- 締切済み
- C・C++・C#
- 巡回セールスマン問題: NPについて
NP問題である巡回セールスマン問題について質問です． NP問題には，「非決定性チューリングマシンによって多項式時間で解くことができる決定問題」「証拠が与えられれば，その答えがYesであることを(問題の入力サイズに関する)多項式時間以内に確認することができる決定問題」などの定義があります．このふたつめの定義について質問です． 巡回セールス問題における解を確かめる「証拠」とはいったいどのようなものなのでしょうか?
- ベストアンサー
- 数学・算数
- 巡回セールスマン問題を使って・・・
すいません。数学に関してまったくの素人です。 建築の学生なのですが、卒論の対象地の一つの分析として次のようなことを行っております。 「対象地に12の交差点があって １．この交差点全てを最短経路でまわりたい。（スタートとゴールがいっしょ。） ２．交差点全てを最短経路で通過したい。（スタートとゴールはちがう） ということをやるようになってます。 １．に関しては巡回セールスマン問題の分岐限定法でパズル的にとけばいいのでしょうか？ ２．に関してはまったくわかりません。そもそもどのようにスタートとゴールを設定すればいいのか・・・ また上記のような場合に適応できるプログラムは出回っているのでしょうか？もしくは自分で作れるものなのでしょうか？プログラムに関してもまったく素人です。 このように質問ばかりですいません。書いてあることでわからないことがあれば、言ってください。わかるかたご教授ください。お願いします。
- ベストアンサー
- 数学・算数
- 巡回セールスマン問題の考え方を使って・・・。
以前、この場で巡回セールスマン問題の考え方を使って、ということで質問に答えていただきました。その節はありがとうございました。 建築の学生なのですが、卒論の対象地の一つの分析として次のようなことを行っております。 対象地に1４の交差点があって 「１４の交差点全てを一筆書きで、最短経路で通過したい。」 ということをやるようになってます。 これに関して数人の方の協力でプログラムを組んでもらいました。 現在のプログラムはスタートのみ固定して、１４それぞれ最短経路を探索し、ルートと最短距離を表示します。 今度はこれを、スタートとゴールともに固定して 「スタートが交差点１で、ゴールが交差点14のとき ルートは・・。最短距離は何ｍ。」 というふうに表示させたいのですが、プログラムに関して私はまったく素人でどのように変更すればよいかわかりません。 そこで、どのように改良すればよいか教えていただけないでしょうか。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 巡回セールスマン問題
巡回セールスマン問題を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
- 巡回セールスマン問題を使って・・・
以前、この場で巡回セールスマン問題の考え方を使って、ということで質問に答えていただきました。その節はありがとうございました。 建築の学生なのですが、卒論の対象地の一つの分析として次のようなことを行っております。 対象地に1４の交差点があって 「１４の交差点全てを一筆書きで、最短経路で通過したい。」 ということをやるようになってます。 これに関して数人の方の協力でプログラムを組んでもらいました。 現在のプログラムはスタートのみ固定して、１４それぞれ最短経路を探索し、ルートと最短距離を表示します。 今度はこれを、スタートとゴールともに固定して 「スタートが交差点１で、ゴールが交差点14のとき ルートは・・。最短距離は何ｍ。」 というふうに表示させたいのですが、プログラムに関して私はまったく素人でどのように変更すればよいかわかりません。 そこで、どのように改良すればよいか教えていただけないでしょうか。 よろしくお願いします。 文字数の関係で、プログラムをのせれないのでお答えになってくださったときにお礼の場でプログラムをお見せすることができます。
- 締切済み
- Visual Basic
- 言語別(C/C++,Java等)の計算速度の違いが知りたいです。
言語別(C/C++,Java等)の計算速度の違いが知りたいです。 巡回セールスマン問題を解く（よさそうな解を見つける）プログラムを書くことになったのですが、言語が自由です。 オブジェクト指向言語で組もうと思っているんですが、C++、C#、Javaなどの言語のうち、計算速度が早いのはどれでしょうか？ 順番も分かれば、教えてほしいです。 また、もしＣ言語で組めれば、やっぱりオブジェクト指向言語よりも早いのでしょうか？ 大体でもよいので、分かる方いたら教えてください。 よろしくお願いします。
- ベストアンサー
- C・C++・C#
