問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
テクノロジ系基礎理論 › 応用数学
这道题的解析和你的作答记录。
解説
問 33经过全部地点的最短路径问题（旅行商问题的小规模版本）
错误ア
110分钟。进入 Y 的最后一条边必然要花60分钟（B→Y 或 C→Y），而在剩下的 X→A→C→B 这3条边上，不存在能把合计压到50分钟以内的组合。无论如何排列，总和都不会低于最短的130分钟，110分钟属于低估，不成立。
- イ
正解 表格表示「起点→终点」的所需时间（分钟）。把从 X 出发、经过 A、B、C 全部后到达 Y 的路径，按 A、B、C 的排列（共6种）逐一穷举来比较所需时间。这里能直接进入 Y 的边只有 B→Y＝60、C→Y＝60（X→Y 和 A→Y 为「不可达」），因此最后经过的点只能是 B 或 C。最短是 X→A→C→B→Y 的顺序，20（X→A）＋30（A→C）＋20（C→B）＋60（B→Y）＝130 分钟。因此正确答案是「イ」的130分钟。
错误ウ
140分钟。这是 X→A→B→C→Y ＝20＋40＋20＋60 这条路径的值，路径本身有效，但并非最短。把 B 与 C 的经过顺序对调，改成 X→A→C→B→Y，则 A→C＝30、C→B＝20，只需130分钟。
错误エ
150分钟。这是 X→B→A→C→Y ＝20＋40＋30＋60 这条路径的值，因为先经过 B 再折回 A（B→A＝40），多绕了一段路。虽是有效路径，但并非最短。
ここがポイント
- 经过全部地点的最短路径问题（旅行商问题的小规模版本）。把经过点 A、B、C 的排列全部列举出来，比较每种顺序各区间所需时间的合计，选出最小值。
- 能直接前往 Y 的边只有 B→Y 和 C→Y（X→Y、A→Y 为「不可达」），因此最后经过的点只能锁定为 B 或 C。利用这个约束可以减少需要检查的排列。
用語