题目

Problem

	A	B	C	D	E	F	G	H
A	-	38	37	$x$	37	42	41	27
B	38	-	26	32	33	38	37	34
C	37	26	-	39	38	39	30	39
D	$x$	32	39	-	37	36	29	36
E	37	33	38	37	-	32	33	30
F	42	38	39	36	32	-	31	28
G	41	37	30	29	33	31	-	33
H	27	34	39	36	30	28	33	-

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 $x$ km where $32 \leq x \leq 35$ .

(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.

(3)

(b) Use your answer to (a) to determine an initial upper bound for the length of the tourist’s route.

(1)

(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.

(2)

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.

(2)

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.

(4)

题目中文翻译

	A	B	C	D	E	F	G	H
A	-	38	37	$x$	37	42	41	27
B	38	-	26	32	33	38	37	34
C	37	26	-	39	38	39	30	39
D	$x$	32	39	-	37	36	29	36
E	37	33	38	37	-	32	33	30
F	42	38	39	36	32	-	31	28
G	41	37	30	29	33	31	-	33
H	27	34	39	36	30	28	33	-

表中所示的网络表示八个博物馆 A、B、C、D、E、F、G 和 H 之间的最小距离（单位：km）。

一名游客想要每个博物馆至少访问一次，从 A 出发并回到 A。游客希望最小化旅行总距离。A 和 D 之间的最短距离为 $x$ km，其中 $32 \leq x \leq 35$ 。

(a) 使用 Prim 算法，从 A 开始，获得网络的最小生成树。必须清楚说明选择树边的顺序。

(3)

(b) 使用 (a) 的答案确定游客路线长度的初始上界。

(1)

(2)

从 E 开始的最近邻算法给出路线 E–H–A–D–G–C–B–F–E。

(d) 说明这两个最近邻路线中哪个给出更好的上界。给出理由。

(2)

通过删除 A 及其所有弧，找到路线长度的下界为 235 km。

(e) 确定必须包含游客路线最优长度的最小区间。必须清楚说明方法和计算过程。

(4)

解答

(a)

解法一

思路

展开

从 A 开始用 Prim 算法，每次选择跨越已选与未选顶点集合的最短边。已知 x 在 32 至 35 之间，因此不会改变以下选择次序。

答题过程

展开

Applying Prim’s algorithm from A gives:

Step	Arc selected	Weight (km)	New vertex
1	AH	27	H
2	FH	28	F
3	EH	30	E
4	FG	31	G
5	DG	29	D
6	CG	30	C
7	BC	26	B

The order is

\begin{aligned} &\,AH,\ FH,\ EH,\ FG,\\ &\,\hspace{2pt}DG,\ CG,\ BC. \end{aligned}

The tree has total weight

\begin{align*} &\,27+28+30+31\\ &\,\hspace{2pt}+29+30+26\\ =&\,201\text{ km}. \end{align*}

(b)

解法一

思路

展开

使用 (a) 的树权重，把每条边往返一次，就有一条访问全部博物馆并返回起点的路线。初始上界为树权重的两倍。

答题过程

展开

An initial upper bound is twice the weight of the minimum spanning tree:

2(201)=\boxed{402\text{ km}}.

(c)

解法一

思路

展开

从 A 开始，每一步只在尚未访问的博物馆中选择最近的一个，最后回到 A。所得路线的实际长度给出另一个上界。

答题过程

展开

The nearest-neighbour route from A is

\begin{aligned} &\,A-H-F-G-D\\ &\,\hspace{2pt}-B-C-E-A. \end{aligned}

Its length is

\begin{align*} &\,27+28+31+29\\ &\,\hspace{2pt}+32+26+38+37\\ =&\,\boxed{248\text{ km}}. \end{align*}

(d)

解法一

思路

展开

把题目给出的 E 出发路线按各边权相加，得到 212+x。利用 x 的整个允许区间，不需先知道它的精确值，就能证明这条路线总比 248 短。

答题过程

展开

The route starting at E is

\begin{aligned} &\,E-H-A-D-G\\ &\,\hspace{2pt}-C-B-F-E. \end{aligned}

Its length is

\begin{align*} &\,30+27+x+29\\ &\,\hspace{2pt}+30+26+38+32\\ =&\,212+x. \end{align*}

Since 32 ≤ x ≤ 35,

244\leqslant212+x\leqslant247.

In particular, 212 + x ≤ 247 < 248. Therefore the nearest-neighbour route starting at E gives the better upper bound.

(e)

解法一

思路

展开

先利用删除 A 得到的下界 235 求 x。A 在 (a) 的树中是只通过 AH 连接的叶顶点，删掉 AH 后，剩余树的权重是 174。A 的两条最短边为 AH=27 与 AD=x；加回这两条后与 235 相等。求出 x 再更新较好的上界。

答题过程

展开

Deleting A leaves a reduced minimum spanning tree of weight

201-27=174\text{ km}.

The two shortest arcs incident to A are AH(27) and AD(x), since 32 ≤ x ≤ 35 and all other arcs from A have weights at least 37.

The given lower bound therefore satisfies

\begin{align*} 174+27+x=&\,235,\\ 201+x=&\,235,\\ x=&\,\boxed{34}. \end{align*}

Using the better route from (d), the upper bound becomes

212+34=246\text{ km}.

Let L be the optimal route length, in km. The smallest interval is

\boxed{235\leqslant L\leqslant246}.

	A	B	C	D	E	F	G	H
A	-	38	37	$x$	37	42	41	27
B	38	-	26	32	33	38	37	34
C	37	26	-	39	38	39	30	39
D	$x$	32	39	-	37	36	29	36
E	37	33	38	37	-	32	33	30
F	42	38	39	36	32	-	31	28
G	41	37	30	29	33	31	-	33
H	27	34	39	36	30	28	33	-

	A	B	C	D	E	F	G	H
A	-	38	37	$x$	37	42	41	27
B	38	-	26	32	33	38	37	34
C	37	26	-	39	38	39	30	39
D	$x$	32	39	-	37	36	29	36
E	37	33	38	37	-	32	33	30
F	42	38	39	36	32	-	31	28
G	41	37	30	29	33	31	-	33
H	27	34	39	36	30	28	33	-

	A	B	C	D	E	F	G	H
A	-	38	37	$x$	37	42	41	27
B	38	-	26	32	33	38	37	34
C	37	26	-	39	38	39	30	39
D	$x$	32	39	-	37	36	29	36
E	37	33	38	37	-	32	33	30
F	42	38	39	36	32	-	31	28
G	41	37	30	29	33	31	-	33
H	27	34	39	36	30	28	33	-

	A	B	C	D	E	F	G	H
A	-	38	37	$x$	37	42	41	27
B	38	-	26	32	33	38	37	34
C	37	26	-	39	38	39	30	39
D	$x$	32	39	-	37	36	29	36
E	37	33	38	37	-	32	33	30
F	42	38	39	36	32	-	31	28
G	41	37	30	29	33	31	-	33
H	27	34	39	36	30	28	33	-

D1 2023 June Q7

题目

解答

(a)

解法一

思路

答题过程

(b)

解法一

思路

答题过程

(c)

解法一

思路

答题过程

(d)

解法一

思路

答题过程

(e)

解法一

思路

答题过程

	A	B	C	D	E	F	G	H
A	-	38	37	$x$	37	42	41	27
B	38	-	26	32	33	38	37	34
C	37	26	-	39	38	39	30	39
D	$x$	32	39	-	37	36	29	36
E	37	33	38	37	-	32	33	30
F	42	38	39	36	32	-	31	28
G	41	37	30	29	33	31	-	33
H	27	34	39	36	30	28	33	-

	A	B	C	D	E	F	G	H
A	-	38	37	$x$	37	42	41	27
B	38	-	26	32	33	38	37	34
C	37	26	-	39	38	39	30	39
D	$x$	32	39	-	37	36	29	36
E	37	33	38	37	-	32	33	30
F	42	38	39	36	32	-	31	28
G	41	37	30	29	33	31	-	33
H	27	34	39	36	30	28	33	-