题目
Figure 3 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 and G, represent seven towns. Derek needs to visit each town. He will start and finish at A and wishes to minimise the total distance travelled.
[The total weight of the network is 291]
(a) By inspection, complete the two copies of 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 Derek’s route. Write down the route that gives this upper bound.
(c) Interpret the route found in (b) in terms of the towns actually visited.
(d) Starting by deleting A and all of its arcs, find a lower bound for the route length.
Clive needs to travel along the roads to check that they are in good repair. He wishes to minimise the total distance travelled and must start at A and finish at G.
(e) By considering the pairings of all relevant nodes, find the length of Clive’s route. State the edges that need to be traversed twice. You must make your method and working clear.
题目中文翻译
图 3 模拟了一个道路网络。每条边上的数字表示对应道路的长度（单位：km）。顶点 A、B、C、D、E、F 和 G 代表七个城镇。Derek 需要访问每个城镇。他将从 A 出发并回到 A，并希望最小化旅行总距离。
[网络总权重为 291]
(a) 通过检查，完成答案本中两份最短距离表。
(b) 从 A 开始，使用最近邻算法找到 Derek 路线长度的上界。写出给出此上界的路线。
(c) 根据实际访问的城镇解释 (b) 中找到的路线。
(d) 通过删除 A 及其所有弧，找到路线长度的下界。
Clive 需要沿道路行驶以检查其是否状况良好。他希望最小化旅行总距离，必须从 A 开始并在 G 结束。
(e) 通过考虑所有相关节点的配对，找到 Clive 路线的长度。写出需要经过两次的边。必须清楚说明方法和计算过程。
解答
(a)
解法一
思路
展开
对每一对城镇比较直接道路与可能的间接路线，填入最短距离。答案本中的两份表内容相同，因此完整列出一份对称矩阵即可表示两份完成结果。
答题过程
展开
Both copies of the completed table of least distances are:
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| A | - | 21 | 42 | 17 | 25 | 31 | 41 |
| B | 21 | - | 26 | 27 | 12 | 15 | 20 |
| C | 42 | 26 | - | 32 | 17 | 11 | 46 |
| D | 17 | 27 | 32 | - | 15 | 21 | 47 |
| E | 25 | 12 | 17 | 15 | - | 6 | 32 |
| F | 31 | 15 | 11 | 21 | 6 | - | 35 |
| G | 41 | 20 | 46 | 47 | 32 | 35 | - |
(b)
解法一
思路
展开
从 A 出发，每次在尚未访问的城镇中选择与当前城镇距离最短者；访问全部城镇后返回 A。这里使用的是上一问的最短距离表，而不一定是原图中的直接道路。
答题过程
展开
The nearest neighbour algorithm starting at A gives
The corresponding length is
Therefore an upper bound for Derek’s route is km.
(c)
解法一
思路
展开
上一问的回路来自最短距离表，其中 C 到 B 的最短路要经过 F，G 到 A 的最短路要经过 B。把这两段展开，就得到在原道路网络中实际访问城镇的次序。
答题过程
展开
In the original network, the least-distance arc from C to B represents
and the least-distance arc from G to A represents
Hence the route in terms of the towns actually visited is
(d)
解法一
思路
展开
删去 A 后，先在其余六个顶点上求最小生成树；再加上从 A 出发权重最小的两条连接，使巡回路线能够进入并离开 A，从而得到旅行商问题的删点下界。
答题过程
展开
After deleting A, a minimum spanning tree on the remaining vertices uses
with weight
The two least-weight arcs incident with A have weights 17 and 21. Therefore the lower bound is
(e)
解法一
思路
展开
原网络与指定起终点 A、G 比较后，需要配对的奇度顶点是 A、C、E、G。列出三种完整配对并选总距离最小者，再把最短距离表中的 AG、CE 还原成原网络中实际重复的道路。
答题过程
展开
The vertices to be paired are A, C, E and G. The possible pairings are
The minimum pairing is .
The least-distance route from A to G is , and the least-distance route from C to E is . Therefore the edges that must be traversed twice are
Hence Clive’s minimum route length is