MENU
カテゴリー
おすすめプログラミングスクール紹介中! 一覧はこちらから

最短経路問題の応用(池がある場合)の解き方とは【わかりやすく解説】

こんにちは、ウチダです。

いつもお読みいただきましてありがとうございます。

さて、いきなりですが、最短経路問題(場合の数)は

  1. $A$ → $C$ → $B$
  2. $C$ を通らずに $A$ → $B$
  3. $C$ も $D$ も通らずに $A$ → $B$
  4. 池がある場合

以上、主に $4$ パターンの応用があります。

ただ、この中で特に「池がある場合」。

最短経路問題の悩み

この問題がかなり難しいのですが…

実はとっておきの解法があります!!

よって本記事では、最短経路問題の基本から応用まで

  • 東北大学理学部数学科卒
  • 教員採用試験に1発合格 → 高校教諭経験アリ
  • (専門は確率論でした。)

の僕がわかりやすく解説します。

スポンサーリンク
目次

最短経路問題のテクニカルな解き方とは【「和の法則」を使います】

具体的な問題は後で解くとして、いきなりですがテクニカルな解法をご紹介します。

最短経路問題のテクニカルな解き方とは【「和の法則」を使います】

このテクニカルな解法は、

  • $1$ 通りしか道順がないものに「 $1$ 」と記す。
  • 図のように、和の法則を使って求めていく。

以上 $2$ 点を守れば、意外と簡単に使えます。

よって、$B$ 地点までの最短経路の総数は「 $35$ 通り」と求まりました。

一応当たっているか、通常の解法で確認すると…

$$\frac{7!}{4!3!}={}_7{C}_{3}=\frac{7・6・5}{3・2・1}=35 (通り)$$

と、確かに一致してますね!

ウチダ
通常の解法というのは、「同じものを含む順列」の考え方を利用した方法になります。「通常の解法がよくわからない…」という方は、「同じものを含む順列と組合せは”同じ”です【問題4選もあわせて解説】」の記事からご覧いただくと、よりスムーズに理解できると思いますよ。

さて、一見すると「同じものを含む順列」の考え方を利用した解法の方がスマートな気がします。

しかし、繰り返しになりますが「池がある問題」。

これだけは、このテクニカルな解法が非常に役に立つんですね~。

スポンサーリンク

最短経路問題4選を実際に解いてみよう

ここからは、実際に最短経路問題を基本から発展まで解いていくことにします。

最初は基本のお話なので、もしすっ飛ばしたいという方がいらっしゃいましたら、以下のリンクをクリックしてください。

  • 1問目 …  $A$ → $C$ → $B$ (基本)
  • 2問目 …  $C$ を通らない(少し応用)
  • 3問目 …  $C$ も $D$ も通らない(まあ応用)
  • 4問目 …  池がある最短経路問題(発展)

※「 $〇$ 問目」の部分がリンクになっており、クリックすると問題にジャンプします。

A→C→Bの最短経路問題

問題1.下の図のような格子状の道路がある。このとき、以下の問いに答えよ。
(1) 交差点 $A$ から交差点 $B$ までの最短経路は何通りあるか。
(2) (1)の中で、交差点 $C$ を通る場合の数を求めよ。

(1)は先程もご紹介した、最も基本となる問題です。

(2)は少しテクニックがいりますね。

【解答】

(1) → $5$ 個、↑ $3$ 個の順列の総数を求めればよいので、$$\frac{8!}{5!3!}={}_8{C}_{3}=56 (通り)$$

(2) 以下の $2$ つに分けて求める。

  • ⅰ)… $A$ → $C$ の場合の数
  • ⅱ)… $C$ → $B$ の場合の数

そして、最後に積の法則を用いて掛け算すればOK。

ⅰ) $A$ → $C$ の場合の数

→ $3$ 個、↑ $1$ 個の順列の総数を求めればよいので、$\displaystyle \frac{4!}{3!}=4$ 通り。

ⅱ) $C$ → $B$ の場合の数

→ $2$ 個、↑ $2$ 個の順列の総数を求めればよいので、$\displaystyle \frac{4!}{2!2!}=6$ 通り。

A→C→Bの最短経路問題

したがってⅰ)ⅱ)より、$4×6=24$ 通りである。

(解答終了)

(2)は区画整理(?)をすればわかりやすくなりますね!

色付き以外の部分は考えなくていい、ということになります。

Cを通らない最短経路問題

問題2.下の図のような格子状の道路がある。このとき、交差点 $C$ を通らない場合の数を求めよ。

問題1と道路は同じです。

今度は、$C$ を“通らない”場合の数を求めてみましょう。

↓↓↓

【解答】

通らない場合の数は、全体の場合の数から通る場合の数を引けばOK。

よって、問題1.(1)(2)より、$56-24=32$ 通りである。

(解答終了)

基本的に、何かを否定している場合の数を求めるときは、

(全体の場合の数) $-$ (肯定の場合の数)

が最適な解法です。

ウチダ
以上 $2$ 問が、最短経路問題の必ず押さえたい基本になります。次からは少しレベルアップしますよ~。

CもDも通らない最短経路問題

問題3.下の図のような格子状の道路がある。このとき、交差点 $C$ も交差点 $D$ も通らない場合の数を求めよ。

さて、通らない交差点の数が $2$ つ以上になってしまうと、一気に難しくなってしまいます。

問題2と何が違うのか」ぜひ考えながら解答をご覧ください♪

↓↓↓

【解答】

問題2と同様に、全体の場合の数から引く方針で考える。

CもDも通らない最短経路問題

上のベン図より、「 $C$ を通る場合の数」と「 $D$ を通る場合の数」を引いたとき、「 $C$ かつ $D$ を通る場合の数」が $2$ 回引かれることになる。

つまり、$1$ 回分足さなくてはならない。

ⅰ)$C$ を通る場合の数

$A$ → $C$,$C$ → $B$ とそれぞれ求めた上で、積の法則を使うと、$$\frac{4!}{2!2!}×\frac{5!}{3!2!}=6×10=60 (通り)$$

ⅱ)$D$ を通る場合の数

$A$ → $D$,$D$ → $B$ とそれぞれ求めた上で、積の法則を使うと、$$\frac{6!}{3!3!}×\frac{3!}{2!}=20×3=60 (通り)$$

ⅲ)$C$ かつ $D$ を通る場合の数

$A$ → $C$,$C$ → $D$,$D$ → $B$ と分けて求める必要がある。

よって、積の法則より、$$\frac{4!}{2!2!}×2!×\frac{3!}{2!}=6×2×3=36 (通り)$$

したがってⅰ)~ⅲ)より、全体の場合の数が $\displaystyle \frac{9!}{5!4!}=126$ 通りなので、

$126-(60+60-36)=126-84=42$ 通りである。

(解答終了)

ウチダ
「 $2$ 点以上を通らない最短経路問題」を解くには、集合と命題の話の基礎理解が必須となります。解答がよく理解できなかった方は、「和集合・補集合の要素の個数~(後日書きます。)」の記事をご参考ください。

池がある最短経路問題

問題4.下の図のような格子状の道路があり、池がある部分の道路は使用できない。このとき、交差点 $A$ から交差点 $B$ までの最短経路は何通りあるか。

さて、いよいよやってまいりました「池がある最短経路問題」。

ここでは冒頭に紹介したテクニックを用いて、鮮やかに解いてみせます!

【解答】

  • $1$ 通りしかないところを先に埋めてしまう。
  • 和の法則を用いて、他すべてを埋めていく。

以上 $2$ 点を守り、最短経路の総数を求めていこう。

池がある最短経路問題

したがって図より、$14$ 通りである。

(解答終了)

いかがでしょう。

道が制限される → 場合の数が少なくなる → 数え上げが楽になる → 和の法則を用いたテクニカルな解法が役に立つ

こういった仕組みになっております。

一応、この問題を今まで通りに考えた解法も記しておきますね。

別解:今まで通りの解法

【別解】

図のように上手く対角線(分割線)を引くと、$3$ つの場合に分けられる。

池がある最短経路問題の別解

したがって、$5+4+5=14$ 通りである。

(解答終了)

そもそも場合分けをしなければいけないこと。

それから、それぞれの場合において同じものを含む順列の総数を求めなくてはいけないこと。

以上から、池がある最短経路問題では、”和の法則を利用したテクニカルな数え上げ“が最も有効な手段であることがわかります。

最短経路問題に関するまとめ

改めて、本記事のポイントを $2$ つにまとめます。

  1. 最短経路問題に必要な予備知識は、「同じものを含む順列」「和の法則・積の法則」「和集合・補集合の考え方」この $3$ つ。
  2. 道が制限されればされるほど、”和の法則を利用したテクニカルな数え上げ“が役に立つ。

「場合の数」全 12 記事をまとめました。こちらから次の記事をCHECK!!

あわせて読みたい
場合の数とは?【高校数学Aの解説記事総まとめ12選】 「場合の数」の総まとめ記事です。場合の数とは何か、基本的な部分に触れた後、場合の数の解説記事全12個をまとめています。「場合の数をしっかりマスターしたい」「場合の数を自分のものにしたい」方は必見です!!

以上、ウチダでした~。

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!
スポンサーリンク

コメントを残す

コメント一覧 (6件)

    • そうですね〜。問題がそもそも場合分けを問う問題なので、場合分け以外の解法は難しいかと思います、、

  • ありがとうございます。
    最短経路問題4についての質問です。池を囲むエリアを削除して左側に寄せた場合、6C2で15通りとなり、和の法則の数え上げでも15通りとなります。14通りにはならない理由がわかりません。教えて
    下さい

    • 新井様
      コメントありがとうございます。

      「池を囲むエリアを削除して左側に寄せた場合」とありますが、これをしてしまうと図形そのものが変わってしまうため、同じ問題になりません。
      そもそも、6C2と計算できる理由は、↑矢印2つと→矢印4つの重複順列とみなせるからであり、今回の問題のように真ん中に池がある場合、重複順列とはみなせないので、和の法則で地道に数えるしかありません。

      お役に立てていただければ幸いです。

  • コメント失礼致します。
    分かりやすい解説ありがとうございました。公務員試験問題の解説を探しており、こちらのサイトに辿り着きました。イラストなど入っておりとても分かりやすく拝見させていただきました。
    1点最短経路問題その4について質問なんですが、池が被っている最下列には数字の記入がないのに対して.上の段には池が被ってある箇所にも5が連続して記入している箇所の違いは何なんでしょうか。

    • 平山理彩 様
      コメントありがとうございます!

      たしかに、少しわかりづらかったですね汗
      一番下のルートは1通りしか進み方がないのに対し、一番上のルートは5通りの進み方がある、ということです。
      「5」と書かれた道は、そこにたどり着くまでに5通りの道順がある、という意味になります。

平山理彩 へ返信する コメントをキャンセル

CAPTCHA


目次