题目
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| A | - | 43 | 52 | 47 | 59 | 53 | 55 |
| B | 43 | - | 59 | 45 | 46 | 52 | 47 |
| C | 52 | 59 | - | 51 | 50 | 55 | 51 |
| D | 47 | 45 | 51 | - | 52 | 49 | 55 |
| E | 59 | 46 | 50 | 52 | - | 57 | 48 |
| F | 53 | 52 | 55 | 49 | 57 | - | 55 |
| G | 55 | 47 | 51 | 55 | 48 | 55 | - |
The table above shows the least distances, in metres, between seven classrooms, A, B, C, D, E, F and G. A teacher needs to visit each classroom, starting and finishing at A, and wishes to minimise the total distance travelled.
(a) Show that there are two nearest neighbour routes that start from A. State these routes and their corresponding lengths.
(b) Starting by deleting A, and all of its arcs, find a lower bound for the length of the teacher’s route.
(c) Use your results to write down the smallest interval which you can be confident contains the optimal length of the teacher’s route.
题目中文翻译
上表显示了七个教室 A、B、C、D、E、F 和 G 之间的最小距离（单位：米）。一位教师需要访问每个教室，从 A 出发并回到 A，希望最小化旅行总距离。
(a) 证明从 A 出发有两条最近邻路线。写出这些路线及其对应的长度。
(b) 通过删除 A 及其所有弧，找到教师路线长度的下界。
(c) 使用你的结果写出你确信包含教师路线最优长度的最小区间。
解答
(a)
解法一
思路
展开
从 A 开始，每一步都前往尚未访问的最近教室。路线到达 F 时，F 到尚未访问的 C 和 G 都是 55 米，因此出现两种选择；分别继续应用最近邻规则并回到 A，即得两条路线。
答题过程
展开
The nearest-neighbour choices begin
At , both and are 55 m away, so there are two routes.
If is chosen next, the route is
with length
If is chosen next, the route is
with length
(b)
解法一
思路
展开
删除 A 及与 A 相连的所有边后，对 B、C、D、E、F、G 使用 Kruskal 算法求最小生成树。随后把与 A 相连的两条最短边加回；任何经过 A 的完整巡回都必须有两条边与 A 相接，因此这样得到下界。
答题过程
展开
After deleting , Kruskal’s algorithm selects
Hence the weight of the residual minimum spanning tree is
The two least arcs incident to are and . Therefore a lower bound is
(c)
解法一
思路
展开
(b) 给出最优长度的下界 327；(a) 中较短的可行巡回长度 342 给出上界。把两者合并即可得到能确定包含最优值的最小区间。
答题过程
展开
Using the lower bound from (b) and the shorter nearest-neighbour route from (a),