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

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

スポンサーリンク

最短経路(道順)の問題

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

経路の図 特定の点を通る最短経路を求める際のポイント

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

  1. AからPまでの最短経路の総数を求めます。
  2. PからBまでの最短経路の総数を求めます。
  3. 積の法則より、(AからPまでの総数)× (BからPまでの総数)が求める最短経路の総数となります。

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

まず、点Aから点Pまでの進み方を考えます。
点Aから点Pに最短で進むには、右に4回と上に1回だけ進むことになります。
このような進み方は、同じものを含む順列の考え方から

\[\dfrac{5!}{4!1!}=5\]

となります。点Bから点Pへの進み方も同様に考えて、

\[\dfrac{4!}{3!1!}=4\]

となります。点Aから点Pへの進み方5通りすべてに関して点Pから点Bへの進み方は
同じように4通りずつ存在するので、積の法則より最短経路の総数は

\[5\times 4=20\]

と求められます。

参考

チャート式 数研出版

スポンサーリンク

シェアする

  • このエントリーをはてなブックマークに追加

フォローする

スポンサーリンク