卒業研究の題材で巡回セールスマン問題をあつかっていて、解法に困ってます。巡回セールスマン問題の定義は「完全グラフにおいて全ての都市を回り、始点にもどってくる最短経路を探す問題」だと思うのですが、私の研究室の教授が、完全グラフ(すべての都市に道が繋がっているグラフ)ではなく、道の決まってるグラフで、しかも始点に戻ってくる必要のないグラフで考えるようにいわれました。確かに現実問題として全ての家に道が繋がっているケースは考えられません。たとえば、世界の全ての空港を最短距離で巡ろうとしたとき、今いる国からいけるところといけないところがあるのと同じです。
ただ、この場合の解法として、巡回しなくてもよいといっても完全グラフではないのでひたすら最短の道を選んでいては解がえられず、ハミルトン経路のように同じ道を2度使ってはいけないという定義でもないので、これもつかえません。この問題はいったいどう定義したらいいものでしょうか?また、このような問題には、すでに解法があるのでしょうか?難しい問題だと思いますが、少しでも解る方、おねがいいたします。
No.1ベストアンサー
- 回答日時:
過去の質問に、同じ問題を(すごくいい加減ですけど)扱ったものがあります。
(下記URL)特に、同じ道を同じ向きに2度使う経路は最短経路ではない、という自明の定理を使いますと、総当たりが必要なNP問題(NP=nondeterministic polynomial)に帰着しそうですね。
しかし準最適解を求めるということでしたら、様々な工夫の余地が幾らでもある奥の深い問題でしょう。
参考URL:http://oshiete1.goo.ne.jp/kotaeru.php3?q=147691
参考URLを拝見させていただきました。なるほど、やはり一概には解けない問題なんですね。最適解をみつけるのは無理そうなので、いかに処理時間の短い、準最適解をみつけるかを考えてみます!ありがとうございました!
No.2
- 回答日時:
わかる方ではないですが1つの案を書きます。
巡回セールスマン問題を解く方法は全てのケースを当たる方法と遺伝的アルゴリズムに代表されるような準最適解を求める方法の2つに分けられます。
全ての可能性を探索するのであれば、最短路を探せば良いのではないでしょうか?道が決まっていると言っても、道がないのであれば最短路ではありません。
GAで解くのであれば、道がないのですから評価値を下げて自然淘汰されるようにすれば良いと思います。
全探索は、数が大きくなるとスーパーコンピュータを使っても解けません。
GAはその戦略によってプログラムの性能が大きく変わる可能性があります。
それと、以上のような問題は同じことをやってる人は多分いると思います。レベルは巡回セールスマン問題とたいして変わらないと思いますよ。
なんか、見当違いをしているような気もするので間違ってたらごめんなさい。
やはり形が変わっても、巡回セールスマン問題に近道なし!ってことですね!巡回セールスマン問題にいくつかの制限をあたえることによって、なんとか遂次法でとけないかと考えていたのですが、甘かったです。イロイロと試してみます!ありがとうございました!
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 グラフ理論の数学の問題です。このタイプの問題は初めて見たので、どうやって解けばいいかわからないです。 1 2023/05/27 19:09
- 高校受験 数学の問題いくつか捨てても大丈夫?残り1ヶ月、点数が取れない教科ばっか勉強しても大丈夫? 高校受験 2 2023/01/07 17:55
- 数学 写真の(1)の問題についてですが、解説を見るとグラフを使って示しているのですが、解説の文章はグラフを 1 2023/02/09 17:48
- 環境・エネルギー資源 停車中の自動車のヘッドライト点灯 23 2023/03/01 10:14
- 大学受験 数学力補完計画 2 2022/07/30 23:59
- 中学校受験 中学受験 3 2022/11/13 21:17
- 数学 二次関数のグラフとx軸の共有点を求めよという問題でグラフを書く必要はありますか?数学の先生がほんっっ 5 2022/09/15 01:18
- 数学 共通テスト数学1A 相関係数の問題の解き方 4 2022/12/15 17:01
- 数学 『4色問題③』 2 2022/11/14 00:31
- 宅地建物取引主任者(宅建) 宅建業法で満点に近い高得点を取る勉強方法は? 4 2022/09/09 10:17
このQ&Aを見た人はこんなQ&Aも見ています
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
サンプル数の異なる2群間にお...
-
EXCELにてローパスフィルタを作...
-
下の対数表示のグラフから低域...
-
数Ⅲの問題です 数直線上を運動...
-
エクセルのグラフから半値幅を...
-
心理学の統計について
-
両側検定の読み方 両側検定の読...
-
高校 数学 aを実数の定数とする...
-
粘性率の定義について 写真のグ...
-
一元配置分散分析のp値が0になる
-
巡回セールスマン問題の類似問題
-
検定統計量の値がマイナス
-
エクセルの統計でχ二乗検定の結...
-
ナイキスト周波数の単位について
-
二次関数の問題です 二次関数 y...
-
最小二乗法を反比例の式を元に...
-
変化率のみで、有意差の検定は...
-
2つの数字の有意差
-
検量線の決定係数について
-
Rで重回帰分析をして、信頼区間...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
EXCELにてローパスフィルタを作...
-
サンプル数の異なる2群間にお...
-
下の対数表示のグラフから低域...
-
エクセルのグラフから半値幅を...
-
検量線の決定係数について
-
心理機能診断をしたのですが、...
-
統計について
-
エクセルの統計でχ二乗検定の結...
-
心理学の統計について
-
ノンパラメトリック検定の多重...
-
アスピリンの加水分解のPHプロ...
-
自由度(1,m)のF値は自由度mのt...
-
死傷者数と死者数の違いって何...
-
検定統計量の値がマイナス
-
極値をもつ時と持たない時、単...
-
最小二乗法を反比例の式を元に...
-
パイロットサンプルって何ですか?
-
【統計】有意に「高い」?「低...
-
対応のあるt検定の結果の書き方
-
片対数グラフで…
おすすめ情報