最短経路１ posted from フォト蔵
今日は,これからお出かけなので，詳しい解説を後回しにさせていただきます。この２枚の図を見て,Start地点から,Goal地点までの最短経路が何通りあるかお考え下さい。パスカルの三角形がこんなところで役立ちます。
最短経路２ posted from フォト蔵
答は，上の図をよく観察していただければ，暗算で出せます。
外出から戻りましたので，解説を始めたいと思います。
この最短経路の問題は，マス目の角（格子点）のところに,下の「パスカルの三角形」と呼ばれる数字の「回文（かいぶん）」を書いていくだけで解決できてしまいます。
１
１ １
１ ２ 1
１ ３ ３ １
１ ４ ６ ４ １
１ ５ 10 10 ５ １
１ ６ 15 20 15 ６ １
・・・・・・・・・・・・・・・・・・・・・
「パスカルの三角形」では,最上段と両脇に１を置き，両脇の１にはさまれた数は，自分の左上と右上の数を足した数になっています。
まず，できるだけ問題を簡単にして，「パスカルの三角形」をどのように使うかを説明していきます。「 問題をできるだけ単純化したり，簡単な場合で考える」ことによって，難しい問題を解く糸口が見つかることがあります。
①今，マス目が１個の道路の場合で考えるとしよう。
1┌─――┐P 2
｜ ｜
｜ ｜
A└――--┘1
上の図のマス目のカド付近に書いてある数字は，その地点までに行くための最短経路の数を表しています。P地点では，左からの来る来方が１通り，下からの来る来方が１通りありますから,A地点からP地点まで来る来方は,
１＋１
＝２
で,２通りと求めることができるわけです。
このように，マス目の頂点（これを格子点という）に目を付けて，格子点の位置に，その地点までの最短経路の数を順次書き込んでいけばよいことになります。
②マス目を４個に増やしてみよう。
3 6
1┌─――┬――--┐
｜ ｜ ｜
｜ ｜2 ｜
1├――--┼--――┤3
｜ ｜ ｜
｜ ｜ ｜
A└――--┴--――-┘
1 1
このように，この最短経路の問題では,それぞれの格子点で自分のすぐ左の数とすぐ下の数を合わせながら（つまり，「パスカルの三角形」を作りながら）数字を記入していけばよいことが分かります。
③結局，下の図に表示されているに順次,格子点に「パスカルの三角形」を書いていくことによって,求める最短経路の数は
２０＋１５
＝３５（通り）
３５通りあることが分かりました。
マス目が上手く描けませんでした。ご解読ください。
多くの方々に読んでいただきたいと思う記事を【ブログルポ】様に登録させていただいています。それぞれの記事へは，次のタイトルリストのリンクからジャンプしていくことができます。そして,それぞれの記事を最後まで読んでいただくと，記事ごとにお気に入りの度合いを評価していただくボタンが付いています。ご面倒でなかったら，各記事を評価していただければ,私にとって記事更新のエネルギーになります。何卒よろしくお願いいたします。
数学ブログランキング ブログベル
こちらからBloglinesでこのブログをＲＳＳ登録できます⇒
