平成22年度 秋期 ITパスポート試験 問72 解説 最短経路の数

最短経路の数を求めるには、経由地点を区切りとして「A1からC2までの経路数」と「C2からD4までの経路数」を別々に計算し、最後に掛け合わせます。

A1からC2までは問題文の通り3通りです。次にC2からD4まで行くには、右方向に2区画（C2→C3→C4）、上方向に1区画（C4→D4）進む必要があります。この区間の最短経路を数えると3通り（C2-C3-C4-D4、C2-C3-D3-D4、C2-D2-D3-D4）あります。

求める全体の経路数は、以下の計算式となります。 $3 \text{（通り）} \times 3 \text{（通り）} = 9 \text{（通り）}$

経路の数を数える考え方

この問題は、組み合わせの考え方に基づいています。格子状の道を移動する際、ある地点からある地点までの最短経路の数は、右に進む回数と上に進む回数の合計回数のうち、どちらの方向に何回進むかを選ぶ組み合わせで決まります。

例えばC2からD4までは、右へ2回、上へ1回進む必要があります。合計3回の手順のうち、どのタイミングで上へ進むかを1箇所選ぶ組み合わせは $_3C_1 = 3$ 通りとなります。このように、移動のステップを数えることで、複雑な網目状の経路も数学的に整理できます。

段階的な分解による解法の組み立て

試験でこの種の問題に出会ったときは、全体を一気に数えようとせず、必ず経由地で分割してください。

1. 到達すべき中間地点を見つける。
2. 出発点から中間地点までの経路数を数える。
3. 中間地点から終点までの経路数を数える。
4. それぞれの経路を掛け合わせる。

「AからBへ行って、次にCへ行く」という動作は、AからBへの各選択に対して、BからCへの各選択が対応するため、積の法則（掛け算）が適用されます。この構造を見抜くことが、最短経路問題の基本です。

実務での活用と教育的意図

この問題は、単なるパズルではなく、コンピュータ科学における探索アルゴリズムやネットワーク設計の基礎概念を問うものです。

システム開発の現場では、データがネットワーク内をどのように転送されるか（ルーティング）、あるいはプロジェクトの工程表でどの経路が最短の納期につながるか（クリティカルパス）を検討する際に、この経路探索の考え方が不可欠です。また、グラフ理論における「ノード（地点）」と「エッジ（道）」という概念を直感的に理解する訓練としても非常に優れています。試験を通じて、効率的なルートを見つけるロジックを養うことが、将来的なトラブルシューティングや設計スキルの土台となります。

参考リンク

• ITパスポート試験ドットコム（過去問解説）
• 【パズル】最短経路の個数を求める公式の導き方（YouTube）
• 組合せ（数学における定義と公式）