プロフィール

mathnegi

Author:mathnegi
ゆる~い人間です(*´ヮ`*)
宮城県在住~

カレンダー

07 | 2017/08 | 09
- - 1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31 - -

最新記事

全記事リスト

全ての記事を表示する

最新コメント

月別アーカイブ

カテゴリ

閲覧者数

検索フォーム

RSSリンクの表示

リンク

ブロとも申請フォーム

この人とブロともになる

QRコード

QR

電卓だよん♪

電 卓

お問い合わせはこちらまで~♪

名前:
メール:
件名:
本文:

受験ブログ 大学受験(指導・勉強法)へ

スポンサーサイト

--.--.-- --:--|スポンサー広告
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

最短経路の問題

2013.12.05 02:54|数学
どもども。


今回は高校数学の定番問題まとめシリーズとして
場合の数の問題の定番,最短経路問題について確認していきましょー 算数mini


 パターン1:基本形

a1_20131205011046272.jpg

いわゆる最短経路の問題というのは上図のような格子状の街路があって,
AからBまで遠回りせずに最短の経路でBまで移動する方法の総数を計算する類の問題ですねーー

まずは基本形のこのパターンの考察からスタートしましょう~ saboten.gif

AからBへの最短経路は,合計12区画分の移動で完了するもので,
それは具体的に「右右右右上上右上右右上上」のように
右へ1区画進む移動を7回,上へ1区画進む移動を5回するものです。

そのような移動の仕方の総数は,たとえば7個の「→」と5個の「↑」を1列に並べる
順列の総数
に相当することから792通りと求めることが出来ますね

b1_20131205011047371.jpg

これは,12回の移動のうち,何回目が上への移動なのかを選ぶ組合せの数に
相当するという考え方で求めることも可能です~ mikan01.gif


b2_20131205011047a40.jpg


ここまでは非常によく知られた定番手法ですが,
ここで,上2つの解き方と比べるとあまり一般認知度の高くない
ちょっと変わった方法を紹介することにします~ kinoko03(1).gif




下図のように点Cを取ってみます。

a14_20131205012554469.jpg


A→C の経路は,必ず下図の点D,Eのうちどちらか一方のみを通ります。

a15_2013120501255459d.jpg


D→C の経路, E→C の経路はそれぞれ1通りですよね。
よって, (A→C の経路の総数)=(A→D の経路の総数)+(A→E の経路の総数)
が成り立ちます hana14.gif

一方,下の図のような場所にCを取ってみると,


a17_2013120501255605a.jpg

(A→C の経路の総数)=(A→D の経路の総数)が成り立ちます。


Cが街路の中のA以外のどこの交差点にあっても同様の考察が出来るので,
CがBの位置にあるときも例外ではありません。
A→B の経路の総数を知るには,Bの1個手前(2ヶ所ありますねー)までの経路数の和で
求められます。更に,Bの1個手前までの経路数を知るには,
もう1個手前までの経路数が分かれば良いですね。
そうやってどんどん遡っていくとやがて始点Aに辿り着きます。

そこで,Aから各交差点までの経路数を始めの方から順に図に書き入れていけば
単純な足し算の連鎖だけで A→B の経路の総数が求められてしまうというわけです

b3_201312050110486dd.jpg


パスカルの三角形を使って (x+y)^n を展開したときの係数を求めていく作業になんとなく似てますね~
この方法の利点としては,作業が単純な足し算のみであることの他に,
街路の形状がどんな形であっても機械的に適用できるということが挙げられます hunayurei.gif
今の例では,街路の形状が単純なので,敢えてこの解法を取らなくても普通に順列計算したほうが
早いかもしれませんが,街路の形状が複雑な場合は非常に威力を発揮してくれます。
しかし,1ヶ所でも足し算を誤ると答えの数値も誤ってしまう欠点もありますね。
しかも,仮にどこかが誤ってることが分かったとしても,どこを間違ったのかを探すのも大変です。



 パターン2:特定の1点を通る

a2_201312050110490ca.jpg

次はちょっとだけ経路の選び方に制約を加えましょう~
特定の点を通る経路の数を考えてみます。図の点Pを取るような A→B の
経路の総数を考えてみましょう~

これはA→Bの経路を,A→PとP→Bの2つに分けて考えるといいですね。
それぞれの経路の出し方はパターン1の方法で出せます。
あとは積の法則で処理できます~

b4_20131205011050f33.jpg

これを各点までの経路数を書き込む方法でやるとこんな感じになります~

b5_20131205011254e74.jpg

空白になる部分が多いと作業が楽ですね hiyob_en.gif



 パターン3:特定の1点を通らない

a2_201312050110490ca.jpg

パターン2の余事象に当たりますね。
パターン2で出てきた点Pを通らない経路数を求めてみましょう~
消去法がオススメです。つまり,全体の経路数から点Pを通る経路数を引いてやればいいです hiyo_en2.gif

b6_201312050112560de.jpg

消去法ではなく,ガッツリと点Pを通らない経路を求めていきたいとしたら
場合分けして解いていくとよいでしょう。
点Pを通らないような経路は必ず下図のア,イ,ウ,エ,オのいずれか1つを通ります
したがって,この5パターンそれぞれの場合の数を求めて足してやればいいわけですな

b7_20131205011256051.jpg

消去法ではなく,正面から堂々と攻めていくような感じなので,敢えて正攻法とでも呼びましょうか。
消去法でいくのと正攻法でいくのと,どちらが簡単に答えが出せるか。
それは街路の形状,というか通ってはいけない点の個数によるので,
「~を通らない」系は必ず消去法のほうが有利,ということはありません

これを各点までの経路数を書き込む方法で解くとこんな感じです~

b8_20131205011257948.jpg


 パターン4:特定の2点を通る

a3_201312050112578a5.jpg


次は通らなければならない点が2個ある場合について考えていきましょう~
この辺りの問題が非常に試験に出やすいですよねー

上の点P,Qを通る経路数を考えてみましょう~
パターン2のときと同様で,A→BをA→P,P→Q,Q→Bの3つに分けてしまうといいですね kaeru_en2.gif
A→Pの経路数はパターン2で既に求めてあります。

b9_20131205011258985.jpg

各点までの経路数を書き込む方法ではこんな感じです。


b10_2013120511441055f.jpg



 パターン5:特定の2点を通らない

a3_201312050112578a5.jpg

今度はパターン4の逆です。通らない点が2個あります。
上の点P,Qを通らない経路数を求めてみましょう。
全体からPまたはQを通る経路数引いてやればいいです。
引くのは「P,Qを両方通る経路数」ではなく「少なくとも一方を通る経路数」なので
注意しなければなりません isona.gif
「少なくとも一方を通る経路数」は,単純にPを通る経路数とQを通る経路数の和ではありません。
それではP,Qの両方を通る経路数の分が2重にカウントされてしまいます。
よって,2回数えられた両方通る経路数(パターン4で求めてあります)を1回分引いてやれば
補正されますね。

このように通らない点の個数が複数になると,「引く場合の数」の計算がややこしくなります
それでも通らない点が2個くらいだと正攻法より消去法のほうが簡単かもしれません。

b11_201312050115554e5.jpg


正攻法でやってみましょう~
Pを通らないためには,ア~オのいずれか1つを通らなければなりません。
Qを通らないためには,カ~クのいずれか1つを通らなければなりません。
このため(ア,カ)を通るパターン,(イ,カ)を通るパターン,(ウ,カ)を通るパターン,
(ウ,キ)を通るパターン,……,(オ,ク)を通るパターンをそれぞれ求めて足す
という
面倒な作業をしなければいけません kitune.gif


b13_20131205011556277.jpg

   b141.jpg


各点までの経路数を書き込むやり方だとこうなります~

b12_20131205011555fb0.jpg


2点P,Qが与えられている場合は,ほかにも
少なくとも一方を通る経路数(さっき求めましたね)を問う設問や
Pは通るがQは通らない経路数を問う設問などもあり得るので注意です~


 パターン6:特定の通路を通らない


a4_20131205011558018.jpg

特定の「点」ではなく「通路」が通れないというパターンの出題も多いです。
上の図では1本だけ通路がありません。このような街路では経路数は幾つになるでしょうか。

この場合は,抜けている通路も実は存在していると仮定して架空の新街路を考えます。
その新街路の全体の経路数から本来は存在しない通路を通る経路数を引いてやるという
方法で求めるのがよいですね nakioni.gif

今の場合だと点aを通り,かつそこから右に進む経路数を引いてやります~

b142.jpg

もちろん正攻法でもいけます(省略します~)

各点までの経路数を書き込む方法ではこんな感じです。

b15_20131205011815448.jpg


 パターン7:特定の点を通る通路を通らない

a5_20131205011814204.jpg

今度はパターン6よりも抜けている通路が多いです~
パターン2,3で使った点Pに当たる点を通る4つの通路が抜けている街路を考えてみましょう~

この場合の経路数も,抜けている道を補充した新街路を考えて
全体の経路数から本来抜けている通路を取る経路数を引けばよいです。
今回は本来抜けている通路を通る経路というのは,つまり点Pを通る経路です。
したがって,全体から点Pを通る経路数を引いてやればいいので
パターン3と結果は一緒になりますよ~ ny_ozouni.gif




 パターン8:特定の2点を通る通路を通らない

a6_20131205011815a1b.jpg


次は上図のような,ある2点を通る通路が通れない街路を考えてみましょう~

やはり抜けている道を補充した新街路を想定して,全体から抜けてる道を通る経路数を
引いてやるのが良いですね~ oden.gif
抜けている2点のうち少なくとも一方を通る経路数を引くので,計算方法はパターン5と同様です~

b16_201312050118163e1.jpg

b17_2013120501181744c.jpg


各点までの経路数を書き込む方法だとこうです~
これくらい変な街路になってくると,あれこれ解法考えるのが面倒だから
この方法で済ませてしまうというのもアリだと思います~

b18_20131205011817f29.jpg


 パターン9:通れない通路が結構多い

a7_20131205012155b71.jpg

今度は空白地帯がさらに多くなってます~
交差点で言うと6個分抜けてます。
これくらいになってくると,抜けてる個数が多過ぎて
新街路を考えるこれまでの解法よりも正攻法でいったほうが早い気がします

下図のア~エのいずれか1つを通る経路を考えればよいですよ~

b19_2013120501215607d.jpg


各点までの経路数を書き込む方法だとこんな感じです~
あれこれ作戦考えてる暇があったらこの方法で攻めちゃったほうが早いかもしれないです。

b20_20131205012157da3.jpg


 パターン10:街路の外枠が長方形じゃない

a9_20131205012157cc9.jpg

次は図のような街路の外周が長方形ではないパターンを考えてみましょう~
こういう形の街路も案外出題されやすいです~

外周が長方形に近い場合は架空の長方形型新街路を考えてパターン7などのように考えると良いです。
今回は長方形型新街路を考えると抜けている点が12個にもなっちゃうので,
正攻法でいくほうが早いです。

下図のアを通る経路数とイを通る経路数を足せば良いです~ rabi_nomal.gif


b21_20131205012158957.jpg
b22_20131205012159766.jpg


各点までの経路数を書き込む方法だとこんな感じです~

b23_20131205012351c39.jpg


 パターン11:街路がU字状

a18_201312050123514ba.jpg


次はU字状の街路を考えてみましょう~
上図のような街路でA→Bの最短経路を考えるとどうなるでしょうか。

下図の点Pがある縦列より右側のゾーンを通る経路は最短経路にはなりません。
よって,最短経路は必ず点Pを通ります
A→P,P→Bの経路数をそれぞれ求めて積の法則です~

b24_201312050123523f1.jpg


各点までの経路数を書き込む方法だとこうなります~

b25_201312050123531c1.jpg



 パターン12:街路が階段状

a10_20131205012353f02.jpg


最後は上図のような階段状の街路を考えてみましょう~

このパターンも時々出題されることがありますが,実はなかなか面倒くさいですよ winkapa.gif
長方形型新街路を考えても,抜けてる点の個数が多くて厄介です。
正攻法で考えても場合分けが多くて厄介です。

とりあえず正攻法でやってみましょう~
下図のア~ウのうち1つとa~cのうち1つを通る経路を考えます。


b26_2013120501235402a.jpg


段数が5くらいだとこれで何とかなりますが,もっと段数が多かったら
正攻法でいくのも骨が折れそうですね。


実はこの階段状パターン,うまい方法があります
まずは長方形型新街路を考えてみます。

a12_201312050125028f9.jpg

このとき,全体の経路数から下図のP~Sのうち少なくとも1点を通る経路数を引けば良いわけですが,
そのまま考えるとその計算はなかなか面倒であるわけですよ。

a13_20131205012503276.jpg

ちょいと緑色部分の街路を追加で付け足してみます。
そして点Cを図の位置に取ります。
A→Pの経路は「↑」2個の順列で1通り,C→Pの経路も「→」2個の順列で1通りです。
A→Qの経路は「↑」3個,「→」1個の順列で4通り,C→Qの経路も「→」3個,「↑」1個の順列で4通りです。
R,Sに関しても同じです~
これらは線分PSに関する対称性によるものですが,ちょうどP~Sの少なくとも1つを通るA→Bの経路と
P~Sの少なくとも1つを通るC→Bの経路が1対1に対応
します~ win_snowman.gif
そしてよく見ると,C→Bのすべての経路はP~Sの少なくとも1つを通ります。

よって,全体の経路数から引かなければいけない経路数は
C→Bの全体の経路数と一致しまして,これは容易に求められてしまいます~

b28_201312050125031ae.jpg



さて,この132という数字,6番目のカタラン数(詳しくはリンク先参照)なんです teng.gif

今の街路は段数が5でしたが,段数が n の街路だと経路数は (n+1) 番目の
カタラン数になっています。
段数が5の街路は2本の通路を下図のように加えると6段の街路とみなすことも出来ますね。
この2本を加えても場合の数は132通りで変わらないことは明らかです。


b29_20131205012504f50.jpg


カタラン数の満たす二項係数を用いた関係式がリンク先にありますが,この2本の道を追加した
街路で上でやったのと同様の考え方で計算するとそれが得られます。

b30.jpg

5段と見ても6段と見てもどちらの考え方でもいけることは以下の式変形からもわかりますね。


b31.jpg
b32.jpg



上でやったような新街路を考える発想は,何も予備知識もない状態では
なかなか浮かばないと思います。
このような厄介な形の街路であっても,各点までの経路数を書き込む方法だと
機械的に処理できてしまうのが素敵です~ tanuki.gif



b27_2013120501250441d.jpg






それでは今回はこの辺にしておきます~ aicon_bbs18.gif





           
関連記事
スポンサーサイト

テーマ:算数・数学の学習
ジャンル:学校・教育

コメント

非公開コメント

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。