新生活!引っ越してから困らないように注意すべきことは?>>

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

という問題です。


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

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

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

「最短経路の問題」の質問画像

このQ&Aに関連する最新のQ&A

A 回答 (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です。
    • good
    • 0
この回答へのお礼

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

お礼日時:2013/08/17 08:57
    • good
    • 0
この回答へのお礼

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

お礼日時:2013/08/17 08:57

片方の四辺形で考えれば簡単じゃないの ?


四角形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

四角形の場合、最短で戻るには、出発地点を含む対角線部分が重複されて、元に戻れるんでないかい ?
※添付画像が削除されました。
    • good
    • 0
この回答へのお礼

ご解答ありがとうございます。

私の場合は

X→B→A→X→C→B→C→D→E→X→D→X

あわせて

15+17+8+14+10+10+13+14+11+12+12=136m

なりますが...

お礼日時:2013/08/13 22:59

>X を出発して、すべての道を 1回以上通って


>直感で8+17+10+13+14+11=73になるかと思いますが

すべての道を1回以上通っていますか?
    • good
    • 0
この回答へのお礼

ご指摘、ありがとうございます。
すべての道を 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

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

お礼日時:2013/08/13 23:02

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q正十二面体の展開図の見方 

こんにちは。よろしくお願いします。
 
 写真のKの面と平行になる面はどれか。。
  
 という問題なのですがそもそも正十二面体の構造がいまひとつ
 理解できません。どうみれば平行面がわかるのか、又、
 なにかこれを覚えておくと便利だよ!というコツがあれば教えてください。
 よろしくお願いします^^

Aベストアンサー

正十二面体の平行になる面は、一番遠い面どうしで
反対の面になるのはわかりますよね。

AとLが平行で反対の位置なのはわかりますよね。

Lを底に置いたときAが真上でBCDEFが上側で
見える面、GHIJKが下側の面です。

Gの反対は、EFに接しているから上側で遠いCになります。

Kは、FBに接しているから、上側で遠いDが反対です。

↓正十二面体の立体の図
http://www.suriken.com/knowledge/glossary/positive-twelve-body.html

Q複数の点を最短距離で全て繋ぐアルゴリズム

C++で以下のようなプログラムを書こうと思うのですが、
効率的なアルゴリズムが思い浮かびません。
よい方法をご存知の方がおりましたら教えてください。

------------------------
xy平面上に複数の点があります。
それぞれの点の座標は全て分かっています。
今、原点から出発して全ての点を直線で結んでいくのですが
このとき引く直線の長さの総計が最小になるような
結び方を見つけたいのです。

全ての結び方をしらみつぶしに調べると
(点の数)! 通りの総直線距離を計算しなければならず
点が増えるとかなり苦しいことになります・・・

Aベストアンサー

> 具体的に細かなアルゴリズムの組み方まで示したページは
> なかなか見つからないですね・・・

こちら、GAの本なんかに載っているような標準的な方法ですが、図表なんかが多くて解説がわかりやすいです。
参考文献・資料も一緒に見ると良いとおもいます。

アルゴリズム入門 : 第 5 章 知識情報処理入門
http://www.microsoft.com/japan/msdn/academic/Articles/Algorithm/05/


#MSのサイト内ってのが灯台下暗しというか…。

参考URL:http://www.microsoft.com/japan/msdn/academic/Articles/Algorithm/05/

Q加重平均と平均の違い

加重平均と平均の違いってなんですか?
値が同じになることが多いような気がするんですけど・・・
わかりやす~い例で教えてください。

Aベストアンサー

例えば,テストをやって,A組の平均点80点,B組70点,C組60点だったとします.
全体の平均は70点!・・・これが単純な平均ですね.
クラスごとの人数が全く同じなら問題ないし,
わずかに違う程度なら誤差も少ないです.

ところが,A組100人,B組50人,C組10人だったら?
これで「平均70点」と言われたら,A組の生徒は文句を言いますよね.
そこで,クラスごとに重みをつけ,
(80×100+70×50+60×10)÷(100+50+10)=75.6
とやって求めるのが「加重平均」です.

Q「学生生活を通して得たこと」の添削お願い致します。

初めて、投稿させていただきます。

履歴書に書く「学生生活を通して得たこと」という欄にとても悩まされています。
添削、アドバイス等いただけると大変助かります。
拙い、文章ですがなにとぞよろしくお願いします。

私は学生生活を通して事前に計画を立てることの大切さを学びました。大学の授業で展示会をすることになり私はB2パネル4枚にボールペンでイラストを描くことにしました。約半年かけての制作だったためなんとかなるだろうと思い無計画に進めていました。しかし締め切りギリギリに利き手である右手の手首を骨折してしまいボールペンを握れる状態ではなく制作が出来なくなってしまいました。なんとか反対の手で描いていきましたが思い通りに書き進めていくことができず結果、未完成のまま展示することになってしまいました。もし、私が早い段階で計画的に進めていれば締め切りギリギリよりも前に描き終わらせることが出来たのではないかと思い自分の無計画さを悔やみました。この経験から事前に計画を立てることの大切さを学びました。

こういう感じで書き進めているのですが「計画を立てる」なんていうのは普通のことだとは思うのですが思いつかなくて.....。

本当にだめな文章だとは思いますが添削、アドバイス等何でも構いませんのでどうぞよろしくお願いします。

初めて、投稿させていただきます。

履歴書に書く「学生生活を通して得たこと」という欄にとても悩まされています。
添削、アドバイス等いただけると大変助かります。
拙い、文章ですがなにとぞよろしくお願いします。

私は学生生活を通して事前に計画を立てることの大切さを学びました。大学の授業で展示会をすることになり私はB2パネル4枚にボールペンでイラストを描くことにしました。約半年かけての制作だったためなんとかなるだろうと思い無計画に進めていました。しかし締め切りギリギリに利き手であ...続きを読む

Aベストアンサー

1番気になったこと。それは、
あなたは今回の経験で学んだことを、社会人としてまたは入社後、どのような場面でどのように活かしていこうと考えていますか?


こんにちは。
就活を終えた大学4年生です。
私の回答は全部で5部構成にしており、少々長いですが最後までお付き合いいただければ幸いです。


1.アドバイス

文章の最後を「大切さを学びました。」で終わらせていますが、この終わり方はあまり良くないですね。
この手の文章で最も重要なのは、"学びました"の次にくる一言です。

その一言とは、あなたは今回の経験で学んだことを社会人として、または入社後、どのような場面でどのように活かしていこうと考えていますか?ということ。

「~を経験し、~を学んだ。~が身に付いた」このような文章は誰でも書けます。
大事なのは、今後どうしていきたいのか。どうしていくべきなのか。というように、文末に将来を見据えた一言を入れることです。






2.添削

~~私は学生生活を通して事前に計画を立てることの大切さを学びました~~
ここで書くべき項目は"学生生活を通して得たこと"なのですから、最初の部分「私は~通して」は書かなくても大丈夫です。

~~大学の授業~~
大学なのですから、授業ではなく「講義」の方がいいでしょう。

~~ボールペンでイラストを描く~~
「ボールペン」は不要です。

~~約半年かけての制作~~
「約」などという曖昧な表現は絶対にダメです。
また、半年なら"6か月"、半月なら"15日"というように、数字で表現した方が説得力が増します。

~~ギリギリに利き手である右手の手首を骨折してしまい~~
「ギリギリ」は「直前」という言葉に替えましょう。
「利き手である右手」は不要ですね。書くとしても「利き手を骨折」だけで十分です。


~~もし、私が早い段階で計画的に~~
「もし、」というのは不要です。

**全体的に**
一文一文が長すぎる個所もあるので、句読点もっと意識した方がいいです。


3.文章構成について



文章構成の基本は「起承転結」です。

起:学生生活を通して得たことは何なのか。
承:具体例や経験談。
転:その後どうしたのか。
結:学生生活を通して得たことは何なのか。それを今後どう活かしていきたいのか。

ですが、今のあなたの文章は「起承  」になっています。
「結」もあるにはあるのですが、途中で終わってしまってします(1.アドバイス参照)。

あなたが書くべき「転」とは、悔しい思いをしたあと、二の舞を踏まないようにどのように行動したのか、その行動した結果はどうだったのか。ということです。




4.修正後の文章

1~3の項目を踏まえて、あなたの文章を書きかえてみました。修正する時の参考になれば幸いです。
上記に挙げたところ以外にも、ちょくちょく修正を入れています。


事前に計画を立てることの大切さを学びました。
大学の講義で展示会をすることになり、私はイラストを描くことにしました。この時の私は、6ケ月かけての制作だったため、なんとかなるだろうと思い無計画に進めていました。しかし、締切り直前に利き手骨折してしまい、イラストを描くことが出来なくなったため、未完成のまま展示することになってしまいました。この時、早い段階で計画的に進めていれば、締切り日から余裕をもって描き終えることが出来たのではないかと思い、自分の無計画さを悔やみました。

その後は同じ思いをしないために、出題される課題やレポートは締切りより2日前に終わらせることを目標にスケジュール表を作成し、計画的に物事を進めるように心がけました。その結果、最近は展示会で感じた悔しさを感じることはなくなりました。
私はこの経験から、学んだ「事前に計画を立てることの大切さ」を活かし、入社後は~~のようにしていきたいと考えています。




5.最後に

「計画を立てるなんていうのは普通のことだとは思うのですが思いつかなくて」

それでいいんです。
今は普通なことを「普通だ」と感じ、普通のことを普通にできる、普通な人のままでいいんですよ。
たかが大学生の歳で、人よりスバ抜けたことをアピールできる人なんてそうそういるもんじゃないです。「この人すごいな」と感じたら、それはその人が説明上手なだけで、元を正せばなんてことありませんよ。



今後あなたがとるべき行動は、
1.他の回答者様の意見も併せ、今の文章を修正する。
2.面接を受ける。そこでは質問されるので、質問内容を覚えておく。
3.同じ質問をされないように内容や表現を修正する。
4.面接を受ける。そこでは質問されるので、質問内容を覚えておく。
(以下、繰り返し)

書類審査のない企業も多々あるので、そのような企業にはバンバン書類を出してください。たとえ興味なくてもです。
面接を受け、上記リストを繰り返してください。そうすれば、文章は完成系へ近づき、面接などに場慣れすることもできます。
個人的にですが、就活で最も危機感を覚えるのは、面接や試験に場慣れした他の就活生がいることです。面接などに不慣れで緊張していると、自分の100%を出し切ることが難しくなってしまいます。しかし、場慣れ人たちは100%を出し切る方法を知っているので、いい印象を与えることができます。

面接を受けた後、次の日にでも選考辞退の旨を伝えれば、悪いことは何も言われません。
ここで受ける企業は本命ではないのですから、辞退することであなたの印象が悪くなろうと関係ありません。他の企業にあなたの評判が広まるなんてことはありえません。
堂々と選考辞退しちゃってください。


書類を出すだけでなく、興味のない企業でも説明会などには参加してください。たとえ本命とは他業他社でもです。得るモノがあるはずです。

私は建設業には毛頭興味はありません。ですが、友人の付き添いで建設系企業の説明会に行ったとき、人事の人が言った言葉があります。その言葉は「我々は建物に命を吹き込む仕事をしている」というのもでした。私はその言葉を少しアレンジし、本命の製造業向けに変えた言葉をESや履歴書に必ず入れていました。偶然か否か、その後の書類選考の通過率は高かったです。


「習うより慣れろ」です。

1番気になったこと。それは、
あなたは今回の経験で学んだことを、社会人としてまたは入社後、どのような場面でどのように活かしていこうと考えていますか?


こんにちは。
就活を終えた大学4年生です。
私の回答は全部で5部構成にしており、少々長いですが最後までお付き合いいただければ幸いです。


1.アドバイス

文章の最後を「大切さを学びました。」で終わらせていますが、この終わり方はあまり良くないですね。
この手の文章で最も重要なのは、"学びました"の次にくる一言です。

その一言とは、あなた...続きを読む


人気Q&Aランキング