题目
Figure 5 models a network of roads. The number on each edge gives the length, in km, of the corresponding road. The vertices, A, B, C, D, E, F, G and H, represent eight towns. Bronwen needs to visit each town. She will start and finish at A and wishes to minimise the total distance travelled.
(a) By applying Dijkstra’s algorithm, starting at A, complete the table of least distances in the answer book.
(b) Starting at A, use the nearest neighbour algorithm to find an upper bound for the length of Bronwen’s route. Write down the route that gives this upper bound.
A reduced network is formed by deleting A and all arcs that are directly joined to A.
(c) (i) Use Prim’s algorithm, starting at C, to construct a minimum spanning tree for the reduced network. You must clearly state the order in which you select the arcs of your tree.
(ii) Hence, calculate a lower bound for the length of Bronwen’s route.
(d) Using only the results from (b) and (c), write down the smallest interval that you can be confident contains the length of Bronwen’s optimal route.
题目中文翻译
图 5 模拟了一个道路网络。每条边上的数字表示对应道路的长度（单位：km）。顶点 A、B、C、D、E、F、G 和 H 代表八个城镇。Bronwen 需要访问每个城镇。她将从 A 出发并回到 A，并希望最小化旅行总距离。
(a) 通过应用 Dijkstra 算法，从 A 开始，完成答案本中的最短距离表。
(b) 从 A 开始，使用最近邻算法找到 Bronwen 路线长度的上界。写出给出此上界的路线。
通过删除 A 及其所有直接相连的弧，形成一个简化网络。
(c) (i) 使用 Prim 算法，从 C 开始，为简化网络构建最小生成树。必须清楚说明选择树弧的顺序。
(ii) 由此计算 Bronwen 路线长度的下界。
(d) 仅使用 (b) 和 (c) 的结果，写出你确信包含 Bronwen 最优路线长度的最小区间。
解答
(a)
解法一
思路
展开
Dijkstra 算法从 A 的永久标号 0 开始。每次固定当前最小的暂定标号，再用该顶点更新所有尚未固定的相邻顶点。工作值必须按实际产生的先后次序记录；即使某个候选值没有改善当前标号，也可保留在记录中以清楚展示检查过程。
答题过程
展开
Applying Dijkstra’s algorithm from gives:
| Vertex | Order of labelling | Working values | Final value |
|---|---|---|---|
| 1 | 0 | ||
| 2 | 7 | ||
| 3 | 8 | ||
| 4 | 9 | ||
| 5 | 11 | ||
| 6 | 18 | ||
| 7 | 25 | ||
| 8 | 26 |
For example, the tentative label at is successively improved by
The completed table of least distances is therefore
| A | B | C | D | E | F | G | H | |
|---|---|---|---|---|---|---|---|---|
| A | - | 7 | 8 | 9 | 11 | 18 | 25 | 26 |
| B | 7 | - | 14 | 2 | 4 | 11 | 18 | 19 |
| C | 8 | 14 | - | 12 | 10 | 15 | 22 | 23 |
| D | 9 | 2 | 12 | - | 2 | 9 | 16 | 17 |
| E | 11 | 4 | 10 | 2 | - | 7 | 14 | 15 |
| F | 18 | 11 | 15 | 9 | 7 | - | 7 | 8 |
| G | 25 | 18 | 22 | 16 | 14 | 7 | - | 1 |
| H | 26 | 19 | 23 | 17 | 15 | 8 | 1 | - |
(b)
解法一
思路
展开
从 A 开始，每一步在最短距离表中选择尚未访问的最近城镇；访问完全部城镇后回到 A。因为使用的是最短距离表，每一步采用的是两城镇之间的最短距离，不一定是原图中的一条直接道路。
答题过程
展开
The nearest-neighbour route starting at is
Its length is
Thus 57 km is an upper bound.
(c)(i)
解法一
思路
展开
删除 A 后，只在剩余七个顶点上应用 Prim 算法。从 C 开始，每一步选择连接“已入树顶点”和“未入树顶点”的最短弧，并明确写出弧的选择顺序；只列顶点顺序不足以完整展示算法。
答题过程
展开
Starting at , Prim’s algorithm selects
in this order.
The weight of this reduced minimum spanning tree is
(c)(ii)
解法一
思路
展开
任何从 A 出发并回到 A 的巡回都必须有两条边与 A 相接。把 (c)(i) 的缩减最小生成树权重，加上从 A 出发的两条最短距离 AB 与 AC，就得到旅行商路线的下界；这也说明本小题的 “Hence” 如何承接上一问。
答题过程
展开
The two least distances incident to are
Hence the lower bound is
(d)
解法一
思路
展开
(b) 给出一条实际可行路线，所以最优值不会超过 57；(c)(ii) 证明任何巡回都不可能短于 44。题目限定只使用这两个结果，因此直接用它们作为区间两端。
答题过程
展开
Using the lower bound from (c) and the upper bound from (b),
Equivalently, the optimal length lies in km.