問33
頻出度★★☆
地点Xから出発してA，B，Cの3地点の全てを経由して地点Yまで行きたい。各地点間の経路と所要時間が図及び表のとおりであるとき，地点Xから地点Yまで行く最短の時間は何分か。ここで，3地点A，B，Cはどのような順番で経由してもよいものとする。 単位 分
| 始点 ＼ 終点 | A | B | C | Y |
|---|---|---|---|---|
| X | 20 | 20 | 40 | 不可 |
| A | − | 40 | 30 | 不可 |
| B | 40 | − | 20 | 60 |
| C | 30 | 20 | − | 60 |
平成28年度 春期 ITパスポート試験 問33
テクノロジ系基礎理論 › 応用数学
This question's explanation and your answers so far.
解説
問 33
Incorrectア
110 minutes. The final edge entering Y always costs 60 minutes (B→Y or C→Y), and for the remaining three edges X→A→C→B there is no combination that keeps their total within 50 minutes. No matter how the points are ordered, the sum never falls below the shortest value of 130 minutes, so 110 minutes is an underestimate and does not hold.
- イ
正解 The table gives the required time (minutes) for each “start → end”. We compare the travel times by exhaustively trying all orderings of A, B, and C (6 in total) for a route that starts at X, passes through all of A, B, and C, and reaches Y. Here the only edges that lead directly into Y are B→Y=60 and C→Y=60 (X→Y and A→Y are marked N/A), so the last point visited must be either B or C. The shortest is the order X→A→C→B→Y: 20 (X→A) + 30 (A→C) + 20 (C→B) + 60 (B→Y) = 130 minutes. Therefore the correct answer is “イ”, 130 minutes.
Incorrectウ
140 minutes. This is the value of the route X→A→B→C→Y = 20+40+20+60. The route itself is valid but not the shortest. Swapping the order in which B and C are visited, giving X→A→C→B→Y, makes A→C=30 and C→B=20, so it takes only 130 minutes.
Incorrectエ
150 minutes. This is the value of the route X→B→A→C→Y = 20+40+30+60. Because it visits B first and then goes back to A (B→A=40), it takes a detour. It is a valid route but not the shortest.
ここがポイント
- A shortest-route problem that must pass through every point (a small-scale version of the Traveling Salesman Problem). Enumerate all orderings of the intermediate points A, B, and C, compare the sum of the segment times for each order, and pick the minimum.
- The only edges leading directly to Y are B→Y and C→Y (X→Y and A→Y are marked N/A), so the last point visited is narrowed down to B or C. Using this constraint reduces the number of orderings you need to check.
用語