ITパスポート試験 過去問解説
最短経路とは？ITパスポート試験 2010年 (平成22年 秋期) 問72を解説
ITパスポート試験 2010年 (平成22年 秋期) 問72は、最短経路に関する理解を問う問題です。検索から入っても、問題文、選択肢、正解、解説、各選択肢がなぜ違うかをこのページだけで確認できます。
問題文
図1のA1地点からC2地点へ行くとき、通過する地点が最も少なくてすむ最短経路は、図2のように数えることによって3通りあることが分かる。A1地点から、C2地点を経由して、D4地点へ行く最短経路は何通りあるか。 図1: 4×4のグリッド上にA1(左下)、D4(右上)などの地点が配置されている。 図2: A1(1)→B1(1)、A1→A2(1)、B1→C1(1)、B1→B2(2)、A2→B2、C1→C2(3)、B2→C2。 ( )内数字は、A1からその地点までの最短経路の数を表す。
この問題の出題ポイント
- 最短経路の定義だけでなく、問題文中の条件がどの選択肢に当てはまるかを確認する。
- テクノロジ系分野では、用語の目的・主体・責任範囲の違いが選択肢で問われやすい。
- 関連タグ: 応用数学、場合の数、最短経路、計算問題、図表問題。
選択肢
- ア6
- イ9正解
- ウ12
- エ20
正解
イ: 9
解説
最短経路の場合分け問題.A1からC2は3通りと与えられている.C2からD4への最短経路数を計算し、A1→C2→D4の総数=A1→C2(3通り)×C2→D4(?通り)で求める.C2からD4は右に1区画・上に2区画移動で、組合せC(3,1)=3通り.合計3×3=9通り.混同注意として、合計問題は両区間の積を取る原則「経由点までの数×経由点からの数」を覚える.正解はイ.
なぜ他の選択肢が違うのか
ア
6通りはA1→C2(3通り)+C2→D4(3通り)と誤って加算した値.経路の組合せは順次的な経路選択であり、積で計算するのが正しいため誤答.
イ（正解）
正解.A1→C2が3通り、C2→D4が3通り(右1上2の組合せ).3×3=9通りが正答.経由点問題は両区間の経路数を掛ける.
ウ
12通りは中間経路数の誤算.正しくはC2→D4=C(3,1)=3通り、A1→C2=3通り、計9通り.12は数え過ぎ.
エ
20通りはA1→D4の総経路数(C(6,3)=20)に近い値だが、C2経由の条件を満たさない総経路数で誤り.C2必須経由を考慮していない.
解き方の整理
最短経路の問題では、選択肢のキーワードだけで判断せず、問題文が示す条件と正解選択肢の説明が一致しているかを見ます。誤答選択肢は、似た用語を混ぜる、主体を入れ替える、目的や範囲を広げすぎる、という形で作られることが多いため、選択肢別解説まで確認しておくと復習効率が上がります。
関連問題
前後の問題
2010年 (平成22年 秋期) の関連する問題
復習を続ける
間違えた問題、苦手タグ、模試履歴を保存して復習する導線を用意しています。広告なしPro、弱点分析、復習リマインダーは段階的に提供予定です。