人に聞けない痔の悩み、これでスッキリ >>

『点Aから点Bまで最短経路で。進む時、点線上の4点C,F,Q,Kのうちのいずれか1点を通り、かつ1点を通る。』とあるのですが、それはなぜですか?説明して頂きたいです。

「『点Aから点Bまで最短経路で。進む時、点」の質問画像

A 回答 (2件)

A, B の座標が A(0,0), B(5,5) となるような座標系を考えます。


A から B への最短経路は → または ↑ の移動のみからなるので、
所在地の座標 (x,y) について x+y は一歩進むごとに +1 されます。
盤上で x+y=7 となる点は C, F, Q, K だけですから、
x+y=0 である A から x+y=10 である B へ行く途中で
C, F, Q, K の中のひとつだけを必ず通ることになります。
    • good
    • 0

まずは 「かつ1点を通る」について


例えばQを通った場合、最短経路で進むのだから後戻りしてはいけません!
でもQを通ったのちにC,F,Dを通るのは、後戻りですから最短経路とはならないのです
従ってQを通るルートでは C,F,Dを通らないQの1点のみを通るルートが最短です
C,F,Kについても同様

次に、「4点C,F,Q,Kのうちのいずれか1点を通り」 について
これは考えるまでもないくらい当然のことです
AからBに至る途中、C-F-Q-Kのどれ1つも通らないというのは不可能ですから
かならずC,F,Q,Kのどれかは通らなければならないのです

回答のメインは前半部分ですからよく理解してください^-^
    • good
    • 0

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

このQ&Aを見た人はこんなQ&Aも見ています


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング