図の線上を、点Pから点Rを通って、点Qに至る最短経路は何通りあるか。
| ア | 16 | イ | 24 | ウ | 32 | エ | 60 |
【キーワード】
・最短経路探索
- 最短経路探索
地点Sから地点Gへの移動距離を最も小さくする経路を探す方法です。
問題の2次元正方格子上の場合は、各交差点からの移動は縦・横の移動しかなく(図の線の上しか移動できない。)、各交差点間の移動距離は1である。
答え エ
【解説】
点Pから点Rの経路は4回の移動で上に2回、右に2回であり、その組合せは(右，右，上，上)(右，上，右，上)(右，上，上，右)(上，右，右，上)(上，右，上，右)(上，上，右，右)になる。
これを組合せの式表すと
4C2=4!÷(2!×2!)=(4×3×2×1)÷((2×1)×(2×1))=6 …(1)
である。
同様に、点Rから点Qの経路は5回の移動で上に2回、右に3回の移動であり、これを組合せの式で表すと
5C2(5C3)=5!÷(3!×2!)=(5×4×3×2×1)÷((3×2×1)×(2×1))=10 …(2)
である。
したがって、点Pから点Qまでの経路は
(1)×(2)=6×10=60
(エ)になります。
また、この問題はパスカルの三角形の考えを応用することでも解くことが可能です。
パスカルの三角形
パスカルの三角形を変形した下の図では左下の点(黒点)から、交点までの経路の数が書いてあり
点Pから点Rまでの経路は、青点までなので6 …(3)
点Rから点Qまでの経路は、赤点までなので10 …(4)
なので、点Pから点Qまでの経路は
(3)×(4)=6×10=60
(エ)になります。
なお、パスカルの三角形を用いると点Pから点R、点Rから点Qと分けないで最短経路の数を求めることも可能です。
この問題は点Pから点Rまでの経路と、点Rから点Qまでの経路を数えその積で解く方法があります。
点Pから点Rまでの経路を数えると6 …(5)
点Rから点Qまでの経路を数えると10 …(6)
なので、点Pから点Qまでの経路は
(5)×(6)=6×10=60
(エ)になります。
(この問題程度の経路数であれば、実際に図に経路を書きながら数える方法でもいいと思います。)
戻る
一覧へ