最短経路の問題の解き方は3通り:自分に合う解法を例題で見つけよう!

難易度:★☆☆☆
頻出度:★★☆☆

「場合の数・確率」分野の最短経路を数える問題は、中学入試でも見られる設定なので得意な方も多いのではないでしょうか。

実は最短経路の問題の解き方には主に3通りあり、自分に合った、納得できる解法をいつも使うようにすれば正答率も上がります。

他の解法を検算に使うこともできるので、3通りを全て知っておくと何かと便利で勉強になります。

今回は3通りの解法を紹介した後、それぞれの解法で例題を解いてみます。

スポンサーリンク

最短経路の問題

最短経路の問題は次のようなものです。

最短経路の問題の解き方の解説

非常に簡単な設定ですが、この例で3通りの解法を説明していきます。

【解法①】「同じものを含む順列」の公式を使う

1つ目の解法は、先日当ブログでも取り上げた「同じものを含む順列の公式を使う方法です。

公式・考え方の確認をしたい方は次のリンクをご利用ください。

次の図をご覧になりながら後の説明を読んでいただきたいと思います。

最短経路の問題の解き方①(同じものを含む順列)

AからBまで行くのに、横方向()には2回、縦方向()には3回、計5回移動する必要があります。

その移動順により、経路が決まるのです。

具体的には、5回のうち何回目と何回目で横に行くか、ということです。

なので2個のと3個のを一直線に並べ、できた配列をコマンドと捉え、そのコマンドの通りに進むと考えます。

コマンドの配列が何通りあるかを数えれば、それは経路数そのものとなります。

このコマンドの数え方に「同じものを含む順列の公式を適用することができます。

それぞれ同じものである2個のと3個ので構成される全部で5個の矢印を並べるので、5の階乗(5!)を2の階乗(2!)と3の階乗(3!)で割ればOKです。

便利な公式を使ってスマートに解けるので、個人的にはこの方法が1番オススメです。

【解法②】組み合わせでコマンドをつくる

2つ目は組み合わせを使う方法です。

表面上は①の解法と異なるように見えますが、本質的には「同じものを含む順列」を違った計算方法で求めているだけです。

次の図をご覧ください。

最短経路の問題の解き方②(組み合わせ)

①同様、でコマンドをつくることを考えます。

矢印の順列を数えることは、ブランク5か所にを入れる場合の数を数えるのと同じことです。

5か所から2か所選んでを入れ、残りの3か所にを入れるので、combination, C を用いて上図内の式を立式できます。

【解法③】数字書き込み式

3つ目は中学入試組の方々にはお馴染みの解法です。

特に名称が決まっているわけではないので、ここでは「数字書き込み式」と呼びます。

次の図で説明します。

(便宜上、T字路も交差点と呼んでいます。)

最短経路の問題の解き方③(数字書き込み式)

各交差点はその1つ前の2か所の交差点からしか到達できません。

(A-C間、A-D間は一直線なので例外です。)

よって各交差点までの経路数は、1つ前の2か所の交差点までの経路数の和になります。

右上の図ではこのことを言っています。

A から C、A から D まではずっと1通りなので、スタートの A から順々に各交差点までの経路数を計算し書き込んでいくことができます。

ゴールの B まで続ければ、B に書き込まれた数字が答えです。

この方法は派手さこそありませんが、計算は足し算だけで済みますし、慣れればかなり早く答えまでたどり着けます。

①か②の方法をメインに据え、この方法は検算用としておくと良いでしょう。

以上が最短経路を求める3通りの方法です!

問題に挑戦!

それでは実際に、以上3通りの解法で標準的な例題を解いてみましょう。

定期テストや入試でよく見かける、通らない箇所がある最短経路の問題です。

お手元に紙と書くものがある方は、是非実際に手を動かして考えてみてください。

もちろん解答をご覧になるだけでも効果アリです!

順列で考える最短経路の問題(通らないケース)

難しい設定の問題ではないですが、3通りそれぞれの計算方法を確認することが目的です。

<解法>

通らない経路の数を直接求めるのは困難です。

そこで余事象的に、「(全経路数)-(BC を通る経路数)」を計算することで、BC を通らない経路数を求めます。

解法①~③、それぞれを用いた解答を示しますので、参考にしてください。

<①同じものを含む順列の公式を使った解答>

特に注意点はありません。

順列で考える最短経路の問題(通らないケース)の解答①(同じものを含む順列)

<②組み合わせを使った解答>

こちらも特に注意点はありません。

順列で考える最短経路の問題(通らないケース)の解答②(組み合わせ)

<③数字書き込み式を使った解答>

C から D の経路数を数えるときは、C から D の区間を抜き出して別個に数える必要があります。

A から D までの経路を数えた図に書き込んだ数字を使ってはいけません。

順列で考える最短経路の問題(通らないケース)の解答③(数字書き込み式)

まとめ

最後に今回のテーマのまとめです。

最短経路の求め方には3通りありますが、個人的なオススメは①の「同じものを含む順列の公式の使用です。

この公式は汎用性が高く、使い慣れておくと様々な場面で強力な武器になるからです。

(②は①と本質的には同じ、と理解しておきましょう。)

また、テストなどで時間が余ったら③の数字書き込み式で検算すると良いでしょう。

ということで次のように単語カードにまとめておきます。

(カードには2つの解法しか書いていないので、③数字書き込み式を新しく②としました。)

最短経路の問題の解き方のまとめ(1)

最短経路の問題の解き方のまとめ(2)

いつものようにいろいろとコメントしてしまいましたが、少しでも読者の皆さんの参考になれば幸いです。

今回も最後まで読んでいただきありがとうございました!