最短経路の問題

質問

X を出発して、すべての道を 1回以上通って X に戻ってくるときの最短距離は
何メートルか。

という問題です。

直感で8+17+10+13+14+11=73になるかと思いますが
これで合っていますか。

合わなければこの手の問題はどういうふうに考えれば解けるのかを教えていただきたいです。

ご存知の方、ご指導のほどお願い致します。

回答No.4

staratras · ベストアンサー

次のように考えたらいかがでしょうか。

仮に与えられたグラフについて、一筆書きが可能だとすれば、最短距離の経路はその一筆書きであることは明らかです。

一筆書きが可能なグラフは、すべての点についてその点を通る線分の数が偶数であるか（これを偶点と呼ぶことにします）、その点を通る線分の数が奇数の点（これを奇点と呼ぶことにします）が2つだけ存在するかです。前者の場合はすべての点について、その点を出発してその点に戻る一筆書きが可能ですが、後者の場合、可能な一筆書きは一方の奇点を出発してもう一方の奇点に戻るルートだけです。

しかし、問題のグラフには奇点がB、C、D、Xと４つ存在しますので、このままでは一筆書きはできません。また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です。

お礼

ありがとうございました。

回答No.3

Tacosan

はい.

参考URL：

http://ja.wikipedia.org/wiki/%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E8%B7%AF

お礼

ありがとうございました。

回答No.2

noname#207589

片方の四辺形で考えれば簡単じゃないの ?
四角形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

なりますが...

回答No.1

asuncion

＞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

なりますが、合っていますか。これもやはり直感です。
何かこの手の問題を解くために共通のやり方ってありますかな。