Question

S

最短経路の問題です。障害物があるときの解き方が分かりません。方針を見ても領域の引き方が分かりません。結局、CからBを目指すときに↑か→に進むから、↑か→に障害物があるかどうかで場合わけしろってことでしょうか？

150 第5章 順列と組合せ

 

    
                                                                                                                                                                                                                                                             
  
  
 
   

最短経路

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

図のような市街路をA地点からB地点まで, 最短           B
経路で行く方法は何通りあるか, 以下の各場合につ          ]
いて替えよ。 ただし 妊線部分は池があって通行で       のみL|
きなをいものとする.                        のH
(1) C地点を通って行く場合.             T      ]
(2) C地点を通らないで行く場合。 。 (比導学園大) 人

 右図のような道路があるとき。  、
PからQまで,        1  東時で 1
を短距序で行く 方法が何通り                            es
iqみましょう                                 いくつかの 1 ] wtsz
の数と考える.
通行できない部分がある.
ょ

出発点を含お領域と到達点を名

なお1 2仙一3個を並べる
Pyh
.C。通りとしても求まりますし,     3
合計5 か所のうちつの3か所を     ュ
.C,通りとしても求まります.  SS
ところで. 通行できない部分があるときは次
のように考えるのが有効です.
有図で、A からBまで最短の経路で行くときに
ついて考えでてみましょう-
このとき,
Aを含む領域とBを含む領域に分ける
のです. しかも, 通行できない道(図の青いぃ道)
と婦差するように瞳界線 (点線) を引きます。 た
とえば, 右図のように蘭界線を引くと。 AからB
まで行くには
|      PP'、QQ. RR', SS TT'
。。。 のいずれかで春界線をま7
では,、CからBまでの経

革

 
 

 

 

  
 

ります.
ついて境界線を

 

2
() AからCまでの最短経路は

Hi!

|   あり, CからBまで行くには, 右図のようみ夫界
柳 (点閑) をLL。 MM NN' のいずれか1か所
5た
AーCーエーーBの大路は

  

   

!                 きり
xt    ニ63 (通り)          1
MM       は           0
ーBの経路             ンーBe

数学a

Answer 1

✨ ベストアンサー ✨

受験生

やり方だけの説明になりますが
まず、画像のように
1 通れない点に✕、
2 通れるが以降✕を通る可能性がある点に△、
3 通れて、以降✕を通らない点に○をつけます
4 △→○、△→✕間に印をうちます
その印を全て通る線が領域となります

S

分かりやすくまとめてくれてありがとうございます！
助かります！