题目
(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.
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 最优路线长度的最小区间。