最短経路(道順)を求める際のポイント(特定の通を通る場合):場合の数

  • 特定の通路を通る場合の、目的地までの最短経路を求める問題です。
  • 特定の通路の入り口までの進み方と、出口からの進み方で分けて考えます。
  • 特定の通路を通らない場合は、(すべての進み方)-(通る場合)で求められます。

スポンサーリンク

最短経路(道順)の問題

図のような格子状の道路がある。点Aから点Bまでの、通路Xを通らない最短経路を求めなさい。

最短経路の図

特定の通を通る場合の解法の手順

  1. 点Aから点Bまでの最短経路の総数を求めます。
  2. 点Aから通路Xの左側の点までの最短経路の総数を求めます。
  3. 通路Xの右側の点から点Bまでの最短経路の総数を求めます。
  4. (AからXの左側まで)×(Xの右側からBまで)で通路Xを通る場合の最短経路の総数を求めます。
  5. (すべての進み方)-(通る場合)で通らない場合の総数を求めます。

最短経路(道順)の問題の解説

特定の通路を通らない場合は、余事象の考え方を用いて全体から通る場合を引くことで求めます。
まず、最短経路の総数を求めます。
点Aから点Bまでの最短経路は、上に4回と右に5回進むことになるので、その総数は

となります。

次に、点Xを通る最短経路の総数を求めます。
通路Xを通る最短経路なので、点A→通路Xの左側の点→通路X→通路Xの右側の点→点B
の順に進むことになります。
点Aから通路Xの左側の点までの最短経路は、上に2回と右に1回進むことになるので、
総数は

であり、 通路Xの左側の点から通路Xを通って通路Xの右側の点に進む進み方は1通り、 通路Xの右側の点から点Bまでの最短経路は、上に2回と右に3回進むことになるので、

となります。

よって、通路Xを通る最短経路は

存在することになります。

以上より、通路Xを通らない最短経路は

存在することが求められます。
通らない場合を求めるときは、特に最後の引き算を忘れないように注意が必要です。

参考

チャート式 数研出版

スポンサーリンク