(1)問題概要
ある地点からある地点へ最短経路で行く場合の確率を求める問題。
(2)ポイント
まず、最短経路の場合の数を求める問題との違いを確認しましょう。
参考:最短経路
最短経路の総数を求める問題は、場合の数の総数なので、各々の経路の確率が同じである必要はありません。
しかし、確率を求めるときは、分母・分子どちらの場合の数も「同様に確からしく」ないといけません。
では、なぜ最短経路は同様に確からしくない(各々の経路の確率が等しくない)のでしょうか。
それは、端があるからです。
つまり、「最短経路を行く」という条件がある場合、上端に達したら、右に行くしかなくなり、右の道を選ぶ確率は1となります。右端に達しても同様に、上の道を選ぶ確率が1になります(上端と右端以外は、上と右の½で道を選ぶことができる)
そのため、最短経路の確率を求めるときは、
上端または右端に達するタイミングで場合分けをする
必要があります。
(3)必要な知識
(4)理解すべきコア