• 締切済み

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

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

みんなの回答

  • nana773
  • ベストアンサー率50% (9/18)
回答No.2

わかる方ではないですが１つの案を書きます。 巡回セールスマン問題を解く方法は全てのケースを当たる方法と遺伝的アルゴリズムに代表されるような準最適解を求める方法の２つに分けられます。 全ての可能性を探索するのであれば、最短路を探せば良いのではないでしょうか？道が決まっていると言っても、道がないのであれば最短路ではありません。 GAで解くのであれば、道がないのですから評価値を下げて自然淘汰されるようにすれば良いと思います。 全探索は、数が大きくなるとスーパーコンピュータを使っても解けません。 GAはその戦略によってプログラムの性能が大きく変わる可能性があります。 それと、以上のような問題は同じことをやってる人は多分いると思います。レベルは巡回セールスマン問題とたいして変わらないと思いますよ。 なんか、見当違いをしているような気もするので間違ってたらごめんなさい。

amerikenn
質問者

お礼

やはり形が変わっても、巡回セールスマン問題に近道なし！ってことですね！巡回セールスマン問題にいくつかの制限をあたえることによって、なんとか遂次法でとけないかと考えていたのですが、甘かったです。イロイロと試してみます！ありがとうございました！

  • stomachman
  • ベストアンサー率57% (1014/1775)
回答No.1

過去の質問に、同じ問題を（すごくいい加減ですけど）扱ったものがあります。（下記URL） 特に、同じ道を同じ向きに２度使う経路は最短経路ではない、という自明の定理を使いますと、総当たりが必要なNP問題(NP=nondeterministic polynomial)に帰着しそうですね。 しかし準最適解を求めるということでしたら、様々な工夫の余地が幾らでもある奥の深い問題でしょう。

参考URL：
http://oshiete1.goo.ne.jp/kotaeru.php3?q=147691
amerikenn
質問者

お礼

参考ＵＲＬを拝見させていただきました。なるほど、やはり一概には解けない問題なんですね。最適解をみつけるのは無理そうなので、いかに処理時間の短い、準最適解をみつけるかを考えてみます！ありがとうございました！

  1. カテゴリ
  2. 学問・教育
  3. 自然科学
  4. 物理学

関連するQ&A

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

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

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

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

  • 巡回セールスマン問題

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

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

    以前、この場で巡回セールスマン問題の考え方を使って、ということで質問に答えていただきました。その節はありがとうございました。 建築の学生なのですが、卒論の対象地の一つの分析として次のようなことを行っております。 対象地に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; /* 命令文を追加する */ } } } }

  • 最短路問題について

    はじめまして。 「データ構造とアルゴリズム」を独学で勉強中の学生です。 当方、周りより指導していただける環境が無く どうにも行き詰まってしまったのでここに書き込みをさせていただきました。 お聞きしたい問題なのですが 「最短路問題について問題の定義と解法(アルゴリズム)を説明せよ。次に図１においてpから全ての頂点への最短路を求めよ。」 というものです。 * 図１はhttp://www.geocities.co.jp/Hollywood-Stage/3151/g/g.gifにupしてあります。 最短路問題を解く方法としてダイクストラのアルゴリズムやFloydのアルゴリズムがありますが、これらは書籍などを参考にして理解しているつもりです。 しかし実際、問題を解く手順といいますか、解答を書くことができないのでどなたかおわかりになる方がいらっしゃいましたらご指導をいただきたいと思い書き込みをさせていただきました。 学習不足で怠慢な学生の質問で大変申し訳ありませんが ご指導のほどよろしくお願いいたします。

  • 数学Aの場合の数で最短経路の数を出す問題

    数学Aの場合の数で網目状の道の最短経路の数を出す問題が有りますよね。 ex)３×４の網目上の道で端っこから対角線上の端まで進む道は最短経路は何通りあるか求めろ みたいな問題です。 この問題の答えは 7C3=(7×6×5)/(3×2×1)=35通り と出すことができますが、なんで"C"をつかって出すことが出来るんですか？ rCnはｒ個ある物の中からn個の物を選ぶ時の場合の数 を求める式だったように記憶しているのですがどうでしょうか？ なんでか分かる方がいたら教えてください。お願いします。m(_ _)m

  • 数学の問題教えて下さい。

    問題 図のようにｐ、ｑが通れない道をAからBまで行くことを考える。最短経路の数はいくつあるか？ 解答 ｐを通ってAからBまで行く最短経路総数は、2C1×5C2=20 qを通ってAからBまで行く最短経路総数は、5C2×2C1=20 p,qを通ってAからBまで行く方法は、2C1×2C1×2C1=8 よってp,qの少なくとも一方を通ってAからBに行く方法は、 20＋20-8=32 p,qも通らないでAからBまで行く方法は、 56-32=24通り・・解答 質問は、 この解の時pだけ通る場合を考えないのは、何故ですか？ 教えてください。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

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

質問する