- ベストアンサー
最短経路の問題
- みんなの回答 (4)
- 専門家の回答
質問者が選んだベストアンサー
次のように考えたらいかがでしょうか。 仮に与えられたグラフについて、一筆書きが可能だとすれば、最短距離の経路はその一筆書きであることは明らかです。 一筆書きが可能なグラフは、すべての点についてその点を通る線分の数が偶数であるか(これを偶点と呼ぶことにします)、その点を通る線分の数が奇数の点(これを奇点と呼ぶことにします)が2つだけ存在するかです。前者の場合はすべての点について、その点を出発してその点に戻る一筆書きが可能ですが、後者の場合、可能な一筆書きは一方の奇点を出発してもう一方の奇点に戻るルートだけです。 しかし、問題のグラフには奇点がB、C、D、Xと4つ存在しますので、このままでは一筆書きはできません。またXを出発してXに戻るルートが指定されています。 そこで、奇点どうしを結ぶ線分を付け加えてその2点の間は往復してもよいことにし、すべての点を偶点にできれば、Xを出発してXに戻る”一筆書き”が可能です。 問題のグラフでは、奇点が4つなのでこの線分は最低2本必要ですが、求める"一筆書き"の経路を最短にするには、線分を付け加える2点間の距離ができるだけ短い2点を選ぶ必要があり、それはBC間(10m)とDX間(12m)です。 求める最短距離の経路はこのBCとDXを2回通るルートで、お礼に書かれたX→B→A→X→C→B→C→D→E→X→D→Xもその一つで、最短距離は136mです。 もちろん最短距離の経路はこれに限らず、例えばX→C→D→X→B→C→B→A→X→E→D→X なども条件を満たしますが距離はいずれも136mです。
その他の回答 (3)
片方の四辺形で考えれば簡単じゃないの ? 四角形X-C-B-Aで最短で戻るには、B-Xの部分が重複(=往復)されて元に戻れるんじゃない ? 詰まり、X→B→A→X→C→B→Xの場合だったら、B-X 部分、往復することになる。 もう一つの四角形X-C-D-Eも同じく考えて、D-Xが重復 2っつの四角形が合わさりますので、C-X部分が重複 詰まり、重複部分は3箇所在り、B-X、D-X、C-Xの部分。 従って、Xを出発して再びXに戻って来る為には、 (X-A)+(A-B)+(B-C)+(X-E)+(D-E)+(C-D)+2(X-B)+2(X-D)+2(X-C)=8+17+10+11+14+13+2×15+2×12+2×14 =155 m 四角形の場合、最短で戻るには、出発地点を含む対角線部分が重複されて、元に戻れるんでないかい ?
お礼
ご解答ありがとうございます。 私の場合は X→B→A→X→C→B→C→D→E→X→D→X あわせて 15+17+8+14+10+10+13+14+11+12+12=136m なりますが...
- asuncion
- ベストアンサー率33% (2126/6288)
>X を出発して、すべての道を 1回以上通って >直感で8+17+10+13+14+11=73になるかと思いますが すべての道を1回以上通っていますか?
お礼
ご指摘、ありがとうございます。 すべての道を 1回以上という文言に気づきませんでした。 失礼しました。 そうしたら私のやったところ X→B→A→X→C→B→C→D→E→X→D→X あわせて 15+17+8+14+10+10+13+14+11+12+12=136m なりますが、合っていますか。これもやはり直感です。 何かこの手の問題を解くために共通のやり方ってありますかな。
関連するQ&A
- JAVAで最短経路を求める
1、ある点からある点への、最短経路を求める方法 教えてください! 最初Cと間違えてて、いろいろ考えたけど 何か違うみたいで。。 点から点への道には、所要時間が設定してあります。 2、1とにてるんですけど、 すべての点を最短経路で通る方法。 同じく道には所要時間が設定してあります。 このときは出発点、到着点は気にしないです。 とにかくすべての点を通ればいいみたいです。 かなりさっぱりで困ってます。 どうか方法教えてください、よろしくお願いします。
- ベストアンサー
- Java
- この問題は最短経路の考え方でいいのでしょうか?
この問題は最短経路の考え方でいいのでしょうか? さいころを振って、xy平面上に置かれた駒を次の規則にしたがって動かす。 出た目が1または2ならばx軸方向に1だけ移動させ、 出た目が3または4ならばy軸方向に1だけ移動させ、 出た目が5または6ならば駒はその点にとどめる。 (1)OからAへの最短経路は全部で何通りあるか? (2)さいころを7回振ったとき駒が初めてAに到達する確率を求めよ。 (3)さいころを9回振ったとき駒が初めてAに到達する確率を求めよ。
- 締切済み
- 数学・算数
- 最短路問題について
はじめまして。 「データ構造とアルゴリズム」を独学で勉強中の学生です。 当方、周りより指導していただける環境が無く どうにも行き詰まってしまったのでここに書き込みをさせていただきました。 お聞きしたい問題なのですが 「最短路問題について問題の定義と解法(アルゴリズム)を説明せよ。次に図1においてpから全ての頂点への最短路を求めよ。」 というものです。 * 図1はhttp://www.geocities.co.jp/Hollywood-Stage/3151/g/g.gifにupしてあります。 最短路問題を解く方法としてダイクストラのアルゴリズムやFloydのアルゴリズムがありますが、これらは書籍などを参考にして理解しているつもりです。 しかし実際、問題を解く手順といいますか、解答を書くことができないのでどなたかおわかりになる方がいらっしゃいましたらご指導をいただきたいと思い書き込みをさせていただきました。 学習不足で怠慢な学生の質問で大変申し訳ありませんが ご指導のほどよろしくお願いいたします。
- ベストアンサー
- その他(学問・教育)
- 数学の最短経路の問題を教えてください。
横に4マス、縦に4マスの道路があります。 一番左下を地点A、一番右上を地点Bとして、地点Aから縦に2マス行ってから横に3マスいき、縦に2マスいき最後に横に1マス行くと地点Bに到着するとき。 (1)地点Aから地点Bへの長さの最短の道は何通りありますか? (2)地点Aから地点Bへの長さの最短の道で、左折の回数と右折の回数の和が多くとも3回であるものは何通りありますか? (注 左折、右折は進行方向に向かって考える。例えば、地点Aから縦に2マス行ってから横に3マスいき、縦に2マスいき最後に横に1マス行くと地点Bの道路は左折、右折の数はそれぞれい1、2回でその和は3となる。) という問題の答えが (1)8C4(縦に4回横に4回なので縦縦縦縦横横横横を並び替える)=8・7・6・5/4・3・2=70通り (2)1回→2通り 2回→3C1+3=6通り 3回→5C2×2+5C2=30通り 横 横 横 横 の隙間(場合によっては端にも)に縦を入れる感じのやり方 で38通りになったんですけどあっていますか? もしも、間違っていたり、もっといい考えなどがありましたら教えてください。
- ベストアンサー
- 数学・算数
- 最短経路の問題(場合の数・順列)
極めてオーソドックスな最短経路の問題なのですが、数学から離れて久しいので、問題や、解答の本質を忘れていて困っています。 例えば縦3横5の四角形があるとき、左下のA地点から、右上のB地点まで行く最短距離は、 8C3=8!/3!×5!となるとあるのですが、 (1)この分子の8!=8×7×・・・・・・・1はいったい何を意味しているんでしょうか。何故掛け算するのですか。この式だけで何を表しているのでしょうか。 (2)8C3とはどういう意味でしょうか。それが何故8!=3!×5!と同じ意味になるのですか。 (3)同じく分母の3!×5!は何を表していますか。また、分子を分母を除する意味は何ですか>< 以上どなたかわかりやすく教えていただければ幸いです。お願いします。
- ベストアンサー
- 数学・算数
- 最短距離を知りたい
自転車でツーリングを楽しんでいます。カーナビや駅スパートのように出発地点から目的地までの最短距離のルートを検索するHPをどなたかご存知ありませんか?
- ベストアンサー
- 自転車・マウンテンバイク
- 巡回セールスマン問題の類似問題
卒業研究の題材で巡回セールスマン問題をあつかっていて、解法に困ってます。巡回セールスマン問題の定義は「完全グラフにおいて全ての都市を回り、始点にもどってくる最短経路を探す問題」だと思うのですが、私の研究室の教授が、完全グラフ(すべての都市に道が繋がっているグラフ)ではなく、道の決まってるグラフで、しかも始点に戻ってくる必要のないグラフで考えるようにいわれました。確かに現実問題として全ての家に道が繋がっているケースは考えられません。たとえば、世界の全ての空港を最短距離で巡ろうとしたとき、今いる国からいけるところといけないところがあるのと同じです。 ただ、この場合の解法として、巡回しなくてもよいといっても完全グラフではないのでひたすら最短の道を選んでいては解がえられず、ハミルトン経路のように同じ道を2度使ってはいけないという定義でもないので、これもつかえません。この問題はいったいどう定義したらいいものでしょうか?また、このような問題には、すでに解法があるのでしょうか?難しい問題だと思いますが、少しでも解る方、おねがいいたします。
- 締切済み
- 物理学
- 最短時間のルート教えて下さい
千葉県市原市から茨木県水戸駅までの最短時間で着けるルートを教えて下さい。 ナビ通り行くのと、海ほたる経由で行くのとどちらが時間的に早く着けるか教えて下さい。 出発は3月23日で水戸駅に朝の8時に着きたいので高速料金より時間的に早く着けるルートを知りたいので。 Google等では当然最短距離のルートが早く着くことになるのですが、距離的にあまり変わらないときには海ほたるルートの方が早く着けることは知っているのですが、今回は20km以上の差があること、出発が早朝であることから渋滞もそれ程でも無いかと思いますので、どなたか詳しい方教えて下さい。
- ベストアンサー
- 関東地方
お礼
ありがとうございました。