题目
The network represented by the table shows the least distances, in km, between eight museums, A, B, C, D, E, F, G and H.
A tourist wants to visit each museum at least once, starting and finishing at A. The tourist wishes to minimise the total distance travelled. The shortest distance between A and D is km where .
(a) Using Prim’s algorithm, starting at A, obtain a minimum spanning tree for the network. You must clearly state the order in which you select the arcs of your tree.
(b) Use your answer to (a) to determine an initial upper bound for the length of the tourist’s route.
(c) Starting at A, use the nearest neighbour algorithm to find another upper bound for the length of the tourist’s route. Write down the route that gives this upper bound.
The nearest neighbour algorithm starting at E gives a route of E–H–A–D–G–C–B–F–E.
(d) State which of these two nearest neighbour routes gives the better upper bound. Give reasons for your answer.
Starting by deleting A, and all of its arcs, a lower bound of 235 km for the length of the route is found.
(e) Determine the smallest interval that must contain the optimal length of the tourist’s route. You must make your method and working clear.
题目中文翻译
表中所示的网络表示八个博物馆 A、B、C、D、E、F、G 和 H 之间的最小距离（单位：km）。
一名游客想要每个博物馆至少访问一次，从 A 出发并回到 A。游客希望最小化旅行总距离。A 和 D 之间的最短距离为 km，其中 。
(a) 使用 Prim 算法，从 A 开始，获得网络的最小生成树。必须清楚说明选择树边的顺序。
(b) 使用 (a) 的答案确定游客路线长度的初始上界。
(c) 从 A 开始，使用最近邻算法找到游客路线长度的另一个上界。写出给出此上界的路线。
从 E 开始的最近邻算法给出路线 E–H–A–D–G–C–B–F–E。
(d) 说明这两个最近邻路线中哪个给出更好的上界。给出理由。
通过删除 A 及其所有弧，找到路线长度的下界为 235 km。
(e) 确定必须包含游客路线最优长度的最小区间。必须清楚说明方法和计算过程。