最短経路問題　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　下図のような市街路において、ＡからＢへ遠回りをしないで行く方法の数を考える。

　　　　　　　　　

通常、この問題に対しては、次のように説明され解かれる。 　右図において、そのような道順の総数は、横３本、縦３本の 順列の数に等しいので、

　このような問題に対して、次のような裏技がある。この裏技は、上のような解法が困難な
場合に対しても万能であることを特に強調したいと思う。

左図において、ＡからQへ至る道順は １通りなので、 　　　Ｑ地点に　１ と書く。ＡからＰへ至る道順は、２通りな 　　　ので、Ｐ地点に ２ と書く。他も同様である。ところで、 　　　この ２ という数は、１＋１ という計算で求められる。 　　　このようにして計算したものが、左図の赤字である。 　　　したがって、ＡからＢへ遠回りをしないで行く方法の 　　　数は、２０通りであることが分かる。

　この裏技を、他の場合についても適用してみよう。

左図は、普通次のように解かれる。 　　　　　 　　　裏技を使えば、次の通り。

　次の左下図は、普通次のように解かれる。

　　

裏技を使えば、次の通り。

　読者のために、練習問題を置いておこう。

練習問題　　下図の市街路で、ＡからＢまで行く最短経路の場合の数を求めよ。ただし、
　　　　　　　地点Ｃおよび地点Ｄは通らないものとする。

　　

（解）　Ａ→Ｂの行き方は、　１２！/（７！５！）＝７９２（通り）

　Ａ→Ｃ→Ｂの行き方は、　５！/（３！２！）×７！/（４！３！）＝３５０（通り）

　Ａ→Ｄ→Ｂの行き方は、　８！/（５！３！）×４！/（２！２！）＝３３６（通り）

　Ａ→Ｃ→Ｄ→Ｂの行き方は、

　　５！/（３！２！）×３！/（２！１！）×４！/（２！２！）＝１８０（通り）

したがって、求める場合の数は、　７９２−３５０−３３６＋１８０＝２８６（通り）　　（終）


問題　　下図の市街路で、ＡからＢまで行く最短経路の場合の数を求めよ。

　　

　上記の練習問題のように、Ａ→Ｂの行き方の総数から、あり得ない行き方の総数を引いて
も出来ないことはないが、大変だろう。このような場合は、チェックポイント法が有効である。

（解）　下図において、

　　

　Ａ→Ｂの行き方は、必ず、Ｃ、Ｄ、Ｅ、Ｆの何れかを通る。（←　チェックポイント）

　Ａ→Ｃ→Ｂの行き方は、　６！/（１！５！）×１＝６（通り）

　Ａ→Ｄ→Ｂの行き方は、　６！/（２！４！）×６！/（５！１！）＝９０（通り）

　Ａ→Ｅ→Ｂの行き方は、　７！/（６！１！）×５！/（１！４！）＝３５（通り）

　Ａ→Ｆ→Ｂの行き方は、　１通り

したがって、求める場合の数は、　６＋９０＋３５＋１＝１３２（通り）　　（終）


　この問題についても、裏技を使えば、次の通り。

（別解）
　　　　　　（終）


　左下図のような場合、普通の解法では、少し工夫が必要になる。

下図のように、仮想の市街路を考える。

　ＡからＢへ遠回りをしないで行く方法のうち、黄緑の線を通るものは実際の道ではない。
そのような道順の総数は、Ａ’からＢへ遠回りをしないで行く方法の数に等しい。

　したがって、求める道順の総数は、　　である。

（　→　参考：「カタラン数」）


　この問題に対しても、裏技は特別な工夫なしで、次のように統一的に解かれる。

この裏技を会得された方は、最短経路の問題に対して、 　　向う所、敵なしであろう。塾生たちの今後の健闘に期待し 　　たいと思う。

（追記）　平成２６年３月５日付け

　北海道大学　前期理系（２０１４）入試で、最短経路問題が出題された。問題レベルは標準
である。

左図のような格子状の道路がある｡S地点を出発して、 　　遠回りをしないでG地点に到達する経路を考える｡ 　　　ただし、太い実線で描かれた区間ＡＢを通り抜けるの 　　に1分、二重線で描かれた区間ＣＤを通り抜けるのに8 　　分、それ以外の各区間を通り抜けるのに2分かかるも 　　のとする｡ 　　　このとき、次の問いに答えよ。

(1)　区間ＡＢを通り抜ける経路は何通りあるか｡

(2)　区間ＡＢを通り抜けずに区間ＣＤを通り抜ける経路は何通りあるか。

(3)　すべての経路から任意に1つ選んだとき、S地点からG地点に到達するのにかかる時間
　　の期待値を求めよ。

（解）　（１）　（２！/１！１！）×（５！/２！３！）＝２×１０＝２０（通り）

（２）　１×１×１＋２×１×１＋１×（４！/２！２！）×１＝１＋２＋６＝９（通り）

（３）　区間ＡＢ、区間ＣＤをともに通り抜ける場合（所要時間　１６−１＋６＝２１分）

　　　２×３＝６（通り）

　　区間ＡＢを通り抜けるが、区間ＣＤは通り抜けない場合（所要時間　１６−１＝１５分）

　　　２×（１×３＋２×２）＝１４（通り）

　　区間ＣＤを通り抜けるが、区間ＡＢは通り抜けない場合（所要時間　１６＋６＝２２分）

　　　上記の（１）の場合で、９通り

　　区間ＡＢ、区間ＣＤをともに通り抜けない場合（所要時間　１６分）

　　　８！/（４！４！）−６−１４−９＝７０−２９＝４１（通り）

　したがって、求める期待値は、

　（２１×６＋１５×１４＋２２×９＋１６×４１）/７０＝１１９０/７０＝１７（分）


（コメント）　最短経路問題に確率が絡んでくると、一瞬「ドキッ！」。平易な問題なので受験
　　　　　　生は確実に完答しなければならない。最後の期待値が整数になることに思わず
　　　　　　感動。相当に数値が工夫されていますね！作問者の受験生に対する愛情をひし
　　　　　　ひしと感じます。ただ、上記の解答はすべての経路が同様に確からしいとして計
　　　　　　算していますが、経路によって所要時間が異なるので、同様に確からしいと考え
　　　　　　ることにちょっと違和感を覚える！


（追記）　ＧＡＩ さんより、問題をいただきました。（平成２９年６月２８日付け）

　それぞれの経路の取り方は何通りでしょう？

[A]　(0,0)を出発点とし、座標平面上の格子点(5,5)をゴールとする格子点を経由していく散歩
　　道を考える。ただし、ある格子点から次の格子点への道の取り方は、

　　U（上の格子点へ向かう。　 (0,0)→(0,1)での進み方）
　　D（右の格子点へ向かう。　 (0,0)→(1,0)での進み方）
　　S（右上の格子点へ向かう。 (0,0)→(1,1)での進み方）

　のいずれかを選んで進んでいくものとする。

[B]　(0,0)を出発点とし、座標平面上の格子点(10,0)をゴールとする格子点を経由していく散
　　歩道を考える。ただし、ある格子点から次の格子点への道の取り方は、

　　S（右上の格子点へ向かう。　(0,0)→(1,1)での進み方）
　　T（右下の格子点へ向かう。　(0,0)→(1,-1)での進み方）
　　H（2つ右の格子点へ向かう。 (0,0)→(2,0)での進み方）

　のいずれかを選んで進んでいくものとする。


　らすかるさんからのコメントです。（平成２９年６月２８日付け）

[A]　右上が0回・上が5回・右が5回 → 10C0×10C5=252通り
　　右上が1回・上が4回・右が4回 → 9C1×8C4=630通り
　　右上が2回・上が3回・右が3回 → 8C2×6C3=560通り
　　右上が3回・上が2回・右が2回 → 7C3×4C2=210通り
　　右上が4回・上が1回・右が1回 → 6C4×2C1=30通り
　　右上が5回・上が0回・右が0回 → 5C5×0C0=1通り　　　計 1683通り

[B]　X=(x-y)/2　、Y=(x+y)/2　と座標変換すれば、[A]と全く同じ。


　ＧＡＩ さんからのコメントです。（平成２９年６月２８日付け）

＜問題出題の経緯＞　パスカルの三角形で、

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
･･････････　　　に対し、その平方数での

1
1 1
1 4 1
1 9 9 1
1 16 36 16 1
1 25 100 100 25 1
･･････････　　　　　　を作り出す母関数ってなんだろう？と疑問に感じ、いろいろ調べてたら

　　G(x,t)=1/sqrt(1-2*(1+t)*x+(1-t)^2*x^2)

なる不思議なものに出会った。計算機の助けを受けて展開させてみると、

G(x,t)= 1 +
　　(t + 1)*x +
　　(t^2 + 4*t + 1)*x^2 +
　　(t^3 + 9*t^2 + 9*t + 1)*x^3 +
　　(t^4 + 16*t^3 + 36*t^2 + 16*t + 1)*x^4 +
　　(t^5 + 25*t^4 + 100*t^3 + 100*t^2 + 25*t + 1)*x^5 +
　　(t^6 + 36*t^5 + 225*t^4 + 400*t^3 + 225*t^2 + 36*t + 1)*x^6 +
　　(t^7 + 49*t^6 + 441*t^5 + 1225*t^4 + 1225*t^3 + 441*t^2 + 49*t + 1)*x^7 +
　　　　･･････････

と、見事に、ｔ の多項式の係数にこの平方数が現れてくるではないか！しかも例えば３行目
の「1 9 9 1」の解釈は、(0,0)から(3,3)への格子路をドライブするとき右折する回数が0,1,2,3回
である経路数に相当する。

　そこで、この母関数にちょっといたずらをして、

　　G1(x,t)=1/sqrt(1-2*(2+t)*x+(2-t)^2*x^2)

とすれば何が起こるのだろう？と再び展開してみると、

G1(x,t) = 1 +
　　　(t + 2)*x +
　　　(t^2 + 8*t + 4)*x^2 +
　　　(t^3 + 18*t^2 + 36*t + 8)*x^3 +
　　　(t^4 + 32*t^3 + 144*t^2 + 128*t + 16)*x^4 +
　　　(t^5 + 50*t^4 + 400*t^3 + 800*t^2 + 400*t + 32)*x^5 +
　　　(t^6 + 72*t^5 + 900*t^4 + 3200*t^3 + 3600*t^2 + 1152*t + 64)*x^6 +
　　　(t^7 + 98*t^6 + 1764*t^5 + 9800*t^4 + 19600*t^3 + 14112*t^2 + 3136*t + 128)*x^7 +
　　　　　･･････････

なるものに変化した。そこで、これに対する t の係数を取り出すと、

1
1 2
1 8 4
1 18 36 8
1 32 144 12 16
1 50 400 800 400 32
1 72 900 3200 3600 1152 64
1 98 164 9800 19600 14112 3136 128
･････････････

を調べてみたら、「A133214」がヒットし、その数字の解釈を見ていたら、出題問題[B]に対応
する総数を与えることがわかった。ただし、S、T または H を用いた個数を、i (i=0,1,2,･･･,n)と
したときの行き方が列に並ぶ数を与えている。

　行は、n:0,1,2,3,4,5,･･･

　これを、n=5 の行で見てみると経路の総数は、　1+50+400+800+400+32=1683(通り)　となる
ことになる。

　そこで、各行での総和を計算させてみたら、

1
3
13
63
321
1683
8989
48639
･･･

　これは、また、「A001850」がヒットして、その部分のいろいろな解釈を読んでいたら、これは
出題問題の[A]の経路を与えることが述べられていた。

　従って、この２つの経路では全く同じ総数が発生することを示すことを意味していた。これ
は面白いと感じ出題していたのでした。

　それを、らすかるさんは、いとも簡単にそれを計算することなく見破られていることにびっく
りです。でも、最後の X=(x-y)/2、Y=(x+y)/2 と座標変換すれば、[A]と全く同じが解釈できま
せん。これをもう少し解説して頂けませんか？


　らすかるさんからのコメントです。（平成２９年６月２８日付け）

　 X=(x-y)/2、Y=(x+y)/2と座標変換すれば[A]と全く同じ
(0,0)を出発点とし、座標平面上の格子点(10,0)をゴールとする

(x,y)=(0,0)のとき、(X,Y)=(0,0)
(x,y)=(10,0)のとき、(X,Y)=(5,5)

　S（右上の格子点へ向かう。　(0,0)→(1,1)での進み方）

(x,y)=(1,1)のとき、(X,Y)=(0,1)

　 T（右下の格子点へ向かう。　(0,0)→(1,-1)での進み方）

(x,y)=(1,-1)のとき、(X,Y)=(1,0)

　 H（2つ右の格子点へ向かう。 (0,0)→(2,0)での進み方）

(x,y)=(2,0)のとき、(X,Y)=(1,1)

　従って、出発点が(x,y)=(0,0)、ゴールが(x,y)=(10,0)で進み方が

(1) (x,y)=(+1,+1)　、(2) (x,y)=(+1,-1)　、(3) (x,y)=(+2,0)

である経路は、出発点が(X,Y)=(0,0)、ゴールが(X,Y)=(5,5)で進み方が

(1) (X,Y)=(0,+1)　、(2) (X,Y)=(+1,0)　、(3) (X,Y)=(+1,+1)

である経路と同じですね。

[B]の座標平面の上に、

　X軸がy=-xで原点が共通、(1,-1)がX=1、(2,-2)がX=2、…
　Y軸がy=xで原点が共通、(1,1)がY=1、(2,2)がY=2、…

となるように、XY座標軸を重ねて描けば、XY座標では[A]の動きになります。
（つまり、45°右に傾いた格子点間隔が倍の座標平面）

# 座標平面を変えるだけで全く同じ問題になる、というのを見破るのがこの問題の主旨だと
　思っていました。