题目

Problem

	A	B	C	D	E	F	G	H
A	-	34	29	35	28	30	37	38
B	34	-	32	28	39	40	32	39
C	29	32	-	27	33	39	34	31
D	35	28	27	-	35	38	41	36
E	28	39	33	35	-	36	33	40
F	30	40	39	38	36	-	34	39
G	37	32	34	41	33	34	-	35
H	38	39	31	36	40	39	35	-

Table 1

Table 1 represents a network that shows the travel times, in minutes, between eight towns, A, B, C, D, E, F, G and H.

(a) Use Prim’s algorithm, starting at A, to find the minimum spanning tree for this network. You must clearly state the order in which you select the edges of your tree.

(3)

(b) State the weight of the minimum spanning tree.

(1)

	A	B	C	D	E	F	G	H
J	33	37	41	35	$x$	40	28	42

Table 2

Table 2 shows the travel times, in minutes, between town J and towns A, B, C, D, E, F, G and H.

The journey time between towns E and J is $x$ minutes where $x > 28$ .

A salesperson needs to visit all of the nine towns, starting and finishing at J.

The salesperson wishes to minimise the total time spent travelling.

(c) Starting at J, use the nearest neighbour algorithm to find an upper bound for the duration of the salesperson’s route. Write down the route that gives this upper bound.

(2)

Using the nearest neighbour algorithm, starting at E, an upper bound of 291 minutes for the salesperson’s route was found.

(d) State the best upper bound that can be obtained by using this information and your answer to (c). Give the reason for your answer.

(1)

Starting by deleting J and all of its arcs, a lower bound of 264 minutes for the duration of the salesperson’s route was found.

(e) Determine the value of $x$ . You must make your method and working clear.

(3)

题目中文翻译

	A	B	C	D	E	F	G	H
A	-	34	29	35	28	30	37	38
B	34	-	32	28	39	40	32	39
C	29	32	-	27	33	39	34	31
D	35	28	27	-	35	38	41	36
E	28	39	33	35	-	36	33	40
F	30	40	39	38	36	-	34	39
G	37	32	34	41	33	34	-	35
H	38	39	31	36	40	39	35	-

表 1

表 1 表示一个网络，显示了八个城镇 A、B、C、D、E、F、G 和 H 之间的旅行时间（单位：分钟）。

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

(3)

(b) 写出最小生成树的权重。

(1)

	A	B	C	D	E	F	G	H
J	33	37	41	35	$x$	40	28	42

表 2

表 2 显示了城镇 J 与城镇 A、B、C、D、E、F、G 和 H 之间的旅行时间（单位：分钟）。

城镇 E 和 J 之间的旅行时间为 $x$ 分钟，其中 $x > 28$ 。

一名销售人员需要访问所有九个城镇，从 J 出发并回到 J。

销售人员希望最小化旅行总时间。

(2)

使用最近邻算法，从 E 开始，找到销售人员路线的上界为 291 分钟。

(d) 说明使用此信息和 (c) 的答案可以获得的最佳上界。给出答案的理由。

(1)

通过删除 J 及其所有弧，找到销售人员路线持续时间的下界为 264 分钟。

(e) 确定 $x$ 的值。必须清楚说明方法和计算过程。

(3)

解答

(a)

解法一

思路

展开

Prim 算法从 A 开始，每一步从已选顶点到未选顶点的全部候选边中选最短的一条。写清七条边的选取顺序。

答题过程

展开

Applying Prim’s algorithm from A gives:

Step	Edge selected	Weight (minutes)	New town
1	AE	28	E
2	AC	29	C
3	CD	27	D
4	BD	28	B
5	AF	30	F
6	CH	31	H
7	BG	32	G

The selection order is

\begin{aligned} &\,AE,\ AC,\ CD,\ BD,\\ &\,\hspace{2pt}AF,\ CH,\ BG. \end{aligned}

(b)

解法一

思路

展开

将 (a) 的七条边的时间相加，得到最小生成树的权重，单位是分钟。

答题过程

展开

The weight of the minimum spanning tree is

\begin{align*} &\,28+29+27+28\\ &\,\hspace{2pt}+30+31+32\\ =&\,\boxed{205\text{ minutes}}. \end{align*}

(c)

解法一

思路

展开

从 J 开始。因为 x>28，第一步选 JG=28。此后每次选择当前位置到尚未访问城镇的最短边，全部访问后回到 J；不能漏算最后 HJ 的 42 分钟。

答题过程

展开

Since x > 28, the first choice from J is G, with travel time 28 minutes.

The nearest-neighbour route is

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

Its duration is

\begin{align*} &\,28+32+28+27+29\\ &\,\hspace{2pt}+28+36+39+42\\ =&\,\boxed{289\text{ minutes}}. \end{align*}

Thus an upper bound is 289 minutes.

(d)

解法一

思路

展开

上界越小越好，将从 J 出发的 289 与已给从 E 出发的 291 比较。

答题过程

展开

The best upper bound is 289 minutes, obtained by starting at J, because

289<291.

(e)

解法一

思路

展开

删除 J 后剩余网络就是表 1，树权重已由 (b) 求得为 205。J 的最短边为 JG=28；第二短边是 JE=x 或 JA=33，需先判断是哪一条，不能直接假设 x<33。若选 33，下界将为 266 而非 264，因此第二条必须是 x。也可以从已知下界减去树权重，再减去最短边的权重，反推出另一条边的权重，并用表 2 确认它只能是 JE。

答题过程

展开

After deleting J, the reduced minimum spanning tree is the tree in (a), of weight 205 minutes.

The smallest edge incident to J is JG(28). The second smallest has weight

\min(x,33).

If x ≥ 33, the lower bound would be

205+28+33=266,

which contradicts the given lower bound of 264 minutes. Hence x < 33, so the two smallest edges incident to J have weights 28 and x.

Therefore

\begin{align*} 205+28+x=&\,264,\\ 233+x=&\,264,\\ x=&\,\boxed{31}. \end{align*}

This satisfies the given condition x > 28.

Equivalently, the two smallest edges incident to J must have total weight

264-205=59.

Since the smallest has weight 28, the other must have weight

59-28=31.

No other edge incident to J in Table 2 has weight 31, so this edge is JE and $x=31$ .

	A	B	C	D	E	F	G	H
A	-	34	29	35	28	30	37	38
B	34	-	32	28	39	40	32	39
C	29	32	-	27	33	39	34	31
D	35	28	27	-	35	38	41	36
E	28	39	33	35	-	36	33	40
F	30	40	39	38	36	-	34	39
G	37	32	34	41	33	34	-	35
H	38	39	31	36	40	39	35	-

	A	B	C	D	E	F	G	H
A	-	34	29	35	28	30	37	38
B	34	-	32	28	39	40	32	39
C	29	32	-	27	33	39	34	31
D	35	28	27	-	35	38	41	36
E	28	39	33	35	-	36	33	40
F	30	40	39	38	36	-	34	39
G	37	32	34	41	33	34	-	35
H	38	39	31	36	40	39	35	-

	A	B	C	D	E	F	G	H
A	-	34	29	35	28	30	37	38
B	34	-	32	28	39	40	32	39
C	29	32	-	27	33	39	34	31
D	35	28	27	-	35	38	41	36
E	28	39	33	35	-	36	33	40
F	30	40	39	38	36	-	34	39
G	37	32	34	41	33	34	-	35
H	38	39	31	36	40	39	35	-

	A	B	C	D	E	F	G	H
A	-	34	29	35	28	30	37	38
B	34	-	32	28	39	40	32	39
C	29	32	-	27	33	39	34	31
D	35	28	27	-	35	38	41	36
E	28	39	33	35	-	36	33	40
F	30	40	39	38	36	-	34	39
G	37	32	34	41	33	34	-	35
H	38	39	31	36	40	39	35	-

D1 2024 Jan Q2

题目

解答

(a)

解法一

思路

答题过程

(b)

解法一

思路

答题过程

(c)

解法一

思路

答题过程

(d)

解法一

思路

答题过程

(e)

解法一

思路

答题过程

	A	B	C	D	E	F	G	H
A	-	34	29	35	28	30	37	38
B	34	-	32	28	39	40	32	39
C	29	32	-	27	33	39	34	31
D	35	28	27	-	35	38	41	36
E	28	39	33	35	-	36	33	40
F	30	40	39	38	36	-	34	39
G	37	32	34	41	33	34	-	35
H	38	39	31	36	40	39	35	-

	A	B	C	D	E	F	G	H
A	-	34	29	35	28	30	37	38
B	34	-	32	28	39	40	32	39
C	29	32	-	27	33	39	34	31
D	35	28	27	-	35	38	41	36
E	28	39	33	35	-	36	33	40
F	30	40	39	38	36	-	34	39
G	37	32	34	41	33	34	-	35
H	38	39	31	36	40	39	35	-