平成28年度 春期 ITパスポート試験 問33 解説 最短経路問題

この問題は、出発地Xから目的地Yまで、A、B、Cの全地点を1回ずつ経由する「全経路の合計時間」を計算し、その最小値を求める問題です。

最短経路の計算手順

すべての経由順序は全部で6通り（3の階乗）あります。各ルートの所要時間を表の数値から計算します。

1. X → A → B → C → Y: 20 + 40 + 20 + 60 = 140分
2. X → A → C → B → Y: 20 + 30 + 20 + 60 = 130分
3. X → B → A → C → Y: 20 + 40 + 30 + 60 = 150分
4. X → B → C → A → Y: 20 + 20 + 30 + 不可 = 測定不能
5. X → C → A → B → Y: 40 + 30 + 40 + 60 = 170分
6. X → C → B → A → Y: 40 + 20 + 40 + 不可 = 測定不能

この中で合計時間が最小となるのは「X → A → C → B → Y」の130分となります。

巡回セールスマン問題の考え方

この問題は、情報処理の分野では「巡回セールスマン問題（Traveling Salesperson Problem）」の簡略版といえます。すべての地点を一度ずつ訪れて戻ってくる（または終点に至る）ルートの中で、もっとも効率的な組み合わせを探すこの手法は、最適化問題の基礎にあたります。

試験ではこのように、各地点間の距離やコストを表形式で与え、総当たりで計算させる出題がよく見られます。ポイントは、すべてのパターンを漏れなく書き出すことです。まずは始点に近い場所から枝分かれするようにルートを整理すると、計算ミスを防ぐことができます。

実社会での活用場面

この「最短ルートを探す」という考え方は、現代のITシステムにおいて非常に重要です。

・物流配送システム: トラックが複数の配送先を最も短時間で回るための配送ルート策定。 ・ネットワークルーティング: インターネット上のデータ通信において、パケットが宛先に届くまでの最適経路の計算。 ・生産計画: 工場の機械が複数の工程を回る際、段取り時間を最小化するための順序決定。

これらは、AIやアルゴリズムを用いて自動化されていますが、根底にある考え方は本問のように「どの順番で経由地を回ればコストが最小になるか」を比較検討することにあります。ITパスポートでこの問題が出題されるのは、こうした最適化の論理的思考が、システム設計や業務効率化の基本となるからです。

参考リンク

• 【ITパスポート】計算問題の解き方解説！最短経路問題
• 巡回セールスマン問題をPythonで解いてみた - Qiita
• グラフ理論における最短経路問題（コトバンク）