最短経路の確率(場合の数と区別する)

(1)問題概要

ある地点からある地点へ最短経路で行く場合の確率を求める問題。

(2)ポイント

まず、最短経路の場合の数を求める問題との違いを確認しましょう。

参考:最短経路

最短経路の総数を求める問題は、場合の数の総数なので、各々の経路の確率が同じである必要はありません。

しかし、確率を求めるときは、分母・分子どちらの場合の数も「同様に確からしく」ないといけません。

では、なぜ最短経路は同様に確からしくない(各々の経路の確率が等しくない)のでしょうか。

それは、端があるからです。

つまり、「最短経路を行く」という条件がある場合、上端に達したら、右に行くしかなくなり、右の道を選ぶ確率は1となります。右端に達しても同様に、上の道を選ぶ確率が1になります(上端と右端以外は、上と右の½で道を選ぶことができる)

そのため、最短経路の確率を求めるときは、

上端または右端に達するタイミングで場合分けをする

必要があります。

(3)必要な知識

(4)理解すべきコア