【(高卒)国家一般職・平成25年度・No.18】(経路問題の元祖)格子状道路を通る最短経路問題【行政・高卒区分】

この記事は約2分で読めます。

YouTube講義はこちら

【(高卒)国家一般職・平成25年度・No.18】(経路問題の元祖)格子状道路を通る最短経路問題【行政・高卒区分】

平成25年度・国家一般職(高卒区分)No.18の問題です。
経路問題の元祖ともいうべき問題であり、『格子状道路』を通る最短経路の組合せの数が問われています。

経路問題の基礎を固める上で非常に重要な問題ですので、しっかりと理解するようにしてください。

経路を分割して考える(A→B)

問題で問われているのは『A→B→C→D→A』と戻ってくる最短経路の組合せですが、まず最初に『A→B』の組合せを考えてみます。

格子状道路の問題における必須テクニックですが、まず最初にAと直線でつながっている格子点に1を書き、その後は『左と下の数字を足した数』を左下から右上へと順次記入していくことで、最短経路のパターン数を数えることができます。

YouTube講義の中では時間を割いて説明していますが、必ず『記入している数字の意味』理解するようにしてください。
Aと直線で結ばれた地点については最短経路のパターンは『1通り』、それ以外の地点については『向かってくる経路のパターン数の和』が、その地点までの最短経路のパターン数となります。

B→Cの間の最短経路数

『B』から『C』までの最短経路数については、BとCの位置関係がAとBの位置関係と全く同じであることから、10通りであることが分かります。

C→Dの間の最短経路数

AB間と同様の方法で最短経路数を数えてみると4通りであることが分かります。

D→Aの間の最短経路数

同様に8通りと求めることができます。

『A→B→C→D→A』の最短経路の数

上図のとおり、これまでに求めてきた区間ごとの最短経路数を掛け合わせることによって、3200通りと求めることができます。(正解肢4

YouTube講義

コメント

タイトルとURLをコピーしました