题目
(a) Explain the difference between the classical and the practical travelling salesperson problems.
The table below shows the distances, in km, between seven museums, A, B, C, D, E, F and G.
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| A | - | 25 | 31 | 28 | 35 | 30 | 32 |
| B | 25 | - | 34 | 24 | 27 | 32 | 39 |
| C | 31 | 34 | - | 40 | 35 | 27 | 29 |
| D | 28 | 24 | 40 | - | 37 | 35 | 36 |
| E | 35 | 27 | 35 | 37 | - | 28 | 31 |
| F | 30 | 32 | 27 | 35 | 28 | - | 33 |
| G | 32 | 39 | 29 | 36 | 31 | 33 | - |
Fran must visit each museum. She will start and finish at A and wishes to minimise the total distance travelled.
(b) Starting at A, use the nearest neighbour algorithm to obtain an upper bound for the length of Fran’s route. Make your method clear.
Starting at D, a second upper bound of 203 km was found.
(c) State whether this is a better upper bound than the answer to (b), giving a reason for your answer.
A reduced network is formed by deleting G and all the arcs that are directly joined to G.
(d) (i) Use Prim’s algorithm, starting at A, 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 Fran’s route.
By deleting A, a second lower bound was found to be 188 km.
(e) State whether this is a better lower bound than the answer to (d)(ii), giving a reason for your answer.
(f) Using only the results from (c) and (e), write down the smallest interval that you can be confident contains the length of Fran’s optimal route.
题目中文翻译
(a) 解释经典旅行商问题和实际旅行商问题之间的区别。
下表显示了七个博物馆 A、B、C、D、E、F 和 G 之间的距离（单位：km）。
Fran 必须每个博物馆至少访问一次。她将从 A 出发并回到 A，并希望最小化旅行总距离。
(b) 从 A 开始，使用最近邻算法获得 Fran 路线长度的上界。清楚说明方法。
从 D 开始，找到第二个上界为 203 km。
(c) 说明这是否比 (b) 的答案更好的上界，并给出理由。
通过删除 G 及其所有直接相连的弧，形成一个简化网络。
(d) (i) 使用 Prim 算法，从 A 开始，为简化网络构建最小生成树。必须清楚说明选择树弧的顺序。
(ii) 由此计算 Fran 路线长度的下界。
通过删除 A，找到第二个下界为 188 km。
(e) 说明这是否比 (d)(ii) 的答案更好的下界，并给出理由。
(f) 仅使用 (c) 和 (e) 的结果，写出你确信包含 Fran 最优路线长度的最小区间。
解答
(a)
解法一
思路
展开
两种旅行商问题的区别在于允许访问顶点的次数。“至少一次”允许重复访问，但并不要求一定重复；“恰好一次”则不允许在巡回中重复访问其它顶点，最后回到起点除外。
答题过程
展开
In the classical travelling salesperson problem, each vertex must be visited exactly once before returning to the starting vertex.
In the practical travelling salesperson problem, each vertex must be visited at least once; vertices may be revisited.
(b)
解法一
思路
展开
最近邻算法每一步只比较当前位置到尚未访问博物馆的距离，并选择最短的一条。所有博物馆访问完后，还要加上回到 A 的距离；所得实际巡回长度给出上界。
答题过程
展开
Starting at A, the nearest-neighbour choices are:
| Current museum | Next unvisited museum | Distance (km) |
|---|---|---|
| A | B | 25 |
| B | D | 24 |
| D | F | 35 |
| F | C | 27 |
| C | G | 29 |
| G | E | 31 |
| E | A (return) | 35 |
Thus the route is
Its length is
Therefore an upper bound is 206 km.
(c)
解法一
思路
展开
上界越小，能确定的最优值范围就越紧。把从 D 出发的 203 与 (b) 从 A 出发的 206 比较即可。
答题过程
展开
Yes. The route starting at D gives a better upper bound because
(d)(i)
解法一
思路
展开
先删去 G。Prim 算法每一步从“已加入树的顶点”与“尚未加入的顶点”之间选择最短边，不是只从刚加入的顶点找最近邻。必须保留选边顺序。
答题过程
展开
After deleting G, applying Prim’s algorithm from A gives:
| Step | Arc selected | Weight (km) | Vertices in the tree |
|---|---|---|---|
| 1 | AB | 25 | A, B |
| 2 | BD | 24 | A, B, D |
| 3 | BE | 27 | A, B, D, E |
| 4 | EF | 28 | A, B, D, E, F |
| 5 | CF | 27 | A, B, D, E, F, C |
The selection order is
The reduced minimum spanning tree has weight
(d)(ii)
解法一
思路
展开
承接 (d)(i)，把与被删顶点 G 相连的两条最短边加到剩余最小生成树的权重上。任何经过 G 的巡回都需要进入和离开 G，因此这样得到下界。
答题过程
展开
The two shortest arcs incident to G are CG, of length 29 km, and EG, of length 31 km.
Using the reduced minimum spanning tree from (d)(i), a lower bound is
(e)
解法一
思路
展开
下界越大越好。这里问题询问删除 A 得到的 188 是否更好；它小于删除 G 得到的 191，因此回答“不是”。
答题过程
展开
No. Since
the lower bound obtained by deleting G is better.
(f)
解法一
思路
展开
只使用 (c) 与 (e) 选出的较好界：上界 203，下界 191。最优巡回长度位于这两个数之间，保留端点。
答题过程
展开
Let L be the length, in km, of Fran’s optimal route.
From (c), the best upper bound is 203 km. From (e), the best lower bound is 191 km. Hence