最短経路の総数

スポンサーリンク
次のような横4区画,\ 縦3区画の道路がある.  AからBまで最短距離で行く道順の総数を計算で求める方法を考えよう.  どの道順を取るにせよ,\ →方向に4回,\ ↑方向に3回移動することになる.  よって,\ 道順の総数は,\ →4個と↑3個を並べる順列の総数に等しい.  結局,\ 「同じものを含む順列}」}の考え方を用いると,\ ${7!}{4!3!}$\ で計算できる.  これを一般化すると次の公式が得られる. ${縦m区画,\ 横n区画の最短経路の数}は  $(m個の→}とn個の↑}を並べる順列の数)$} { $[l} 例えば,\ 上図の経路は,\ ただ1つの文字列「↑→→↑→↑→」を意味する. 逆に,\ 文字列「↑→→↑→↑→」は,\ ただ1つの経路(上図)を意味する. このように考えると,\ 最短経路と矢印の並びは{1対1で対応}する. よって,\ 最短経路は,\ 計算が容易な「同じものを含む順列」の扱いで求めれば済む. 通常は同じものを含む順列として考えるので,\ 公式を覚える意味はない. 下図のような碁盤目の道路をAからBまで最短距離で行く. 次の道順は何通りあるか. AからBまで行く.   Pを通る.   Pを通らない. PもQも通る.    \ .1zw}PもQも通らない. 右へ1区画進むことを→},\ 上へ1区画進むことを↑}で表す. { }AからBまでの道順は,\ 6個の→}と4個の↑}の順列の総数に等しい. $ 求める道順は {10!}{6!4!={210\ (通り)}$}  AからP}までは→2個},\ ↑1個}の順列であるから ${3!}{2!1!=3\ (通り)$ { }PからB}までは→4個},\ ↑3個}の順列であるから ${7!}{4!3!=35\ (通り)$ $ 求める道順は 335}={105\ (通り)}$}  ,\ より $求める道順は 210-105}={95\ (通り)}$  より,\ AからP}までの道順は3通り. { }Qの左隣の交差点をQ$’$,\ 右隣の交差点をQ$”$}とする. { }PからQ$’$}までは→2個},\ ↑1個}の順列であるから ${3!}{2!1!=3\ (通り)$ { }Q$”$からB}までは→1個},\ ↑2個}の順列であるから ${3!}{1!2!=3\ (通り)$ $ 求める道順は 333}={27\ (通り)}$}  Pを通る}道順は,\ より105通り. { }Qを通る}道順は  { }PもQも通る}道順は,\ より27通り. $ 求める道順は 210-(105+45-27)}={87\ (通り)}$} AからPまでとPからB}までの道順をそれぞれ考えればよい. AからPまでの3通りのいずれに対しても,\ PからBまでは35通りある.} よって,\ 積の法則を適用する. 「Pを通らない」は,\ 総数から「Pを通る」を引くのが基本である. と同様に分割して求めればよいが,\ Q}が区画の中点にある. Q}を通る場合,\ {必ずQの両隣の交差点を通る}はずである. よって,\ Pから左隣の交差点Q}’までと右隣の交差点Q}”からB}までに分割する. 当然,\ Q}’からQ}”までは1通りである. {総数から「Pを通る」と「Qを通る」を引く.} しかし,\ 「Pを通る」と「Qを通る」}は{排反ではない.} よって,\ 2重に引かないように,\ 重複部分を引いた後で,\ 総数から引く. {排反ではない2つの条件は,\ ベン図を元に考える}とわかりやすい. 求めるのは,\ 図の色塗り部分である.           下図の碁盤目の道路をAからBまで最短距離で行く道順は何通りか.  どの道順も,\ 4つの交差点C,\ D,\ E,\ Fのうちの1つの交差点を必ず通る.} 最短経路問題の中で厄介なのは,\ {一部の道路が欠けているパターン}である. 1つは,\ 欠けた道路を復元し,\ 総数からその道路を通る場合を引く方法がある. 本問の場合,\ 欠けた2つの交差点P,\ Q}を通る場合を引けばよい. ただし,\ この方法は応用性に欠ける. 「Pを通る」と「Qを通る」}は排反ではないから,\ 前問のように求めることになる. しかし,\ 欠けた部分の大きさや形次第で複雑になり,\ 手に負えなくなる. そこで知っておきたいのが,\ {排反に場合分けして直接求める}方法である. {欠けた部分を中心に四角形の対角線で切断し,\ 通る交差点で場合分けする.} どの道順も,\ 交差点C,\ D,\ E,\ F}の1つを必ず通り,\ また複数を通ることはない. よって,\ 「Cを通る」「Dを通る」「Eを通る」「Fを通る」は排反である.} 後は,\ [ACB],\ [ADB],\ [AEB],\ [AFB]}の道順の総数をそれぞれ求めればよい.  さて,\ 最短経路問題には,\ ある意味最強の最終手段がある.  和の法則を利用して,\ 全て書き出して数える方法である.  ある交差点Pまでの道順の総数を考えるとする(左下図).  Pに到達するとき,\ 必ずSとTの一方を通ってくるはずである.  よって,\ 「S→P」と「T→P」は排反であり,\ 次の式が成立する. ${(Pまで道順の総数)}=(Sまでの道順の総数)}+(Tまでの道順の総数)$}  この式を適用して,\ 右下図のように順に書き込んでいけば確実に求まる.  つまり,\ 左の交差点と下の交差点の和を各交差点に書き込んでいく.  存在しない部分は0と考えればよい. 最短経路の確率は, 落とし穴に要注意!  \ \ 上と右を等確率${12}$で選ぶとき, 右上の図の経路を通る確率} 35通りの最短経路のうちの1つであるから ${1}{35}$ ← 間違い!}  \  \ 正解  最初の4回は↑と→から→を選ぶが, 残り3回は↑しか選べない}から   \  \ *要するに, 注意すべきことは35通りの最短経路は同じ確からしさで選ばれるわけではない}ということである.}
タイトルとURLをコピーしました