题目

Problem

The table below represents a complete network that shows the least costs of travelling between eight cities, A, B, C, D, E, F, G and H.

	A	B	C	D	E	F	G	H
A	-	36	38	40	23	39	38	35
B	36	-	35	36	35	34	41	38
C	38	35	-	39	25	32	40	40
D	40	36	39	-	37	37	26	33
E	23	35	25	37	-	42	24	43
F	39	34	32	37	42	-	45	38
G	38	41	40	26	24	45	-	40
H	35	38	40	33	43	38	40	-

Srinjoy must visit each city at least once. He will start and finish at A and wishes to minimise his total cost.

(a) Use Prim’s algorithm, starting at A, to find a minimum spanning tree for this network. You must list the arcs that form the tree in the order in which you select them.

(3)

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

(1)

(d) Show that there are two nearest neighbour routes that start from A. You must make the routes and their corresponding costs clear.

(4)

(e) State the best upper bound that can be obtained by using your answers to (c) and (d).

(1)

(f) Starting by deleting A and all of its arcs, find a lower bound for the total cost of Srinjoy’s route. You must make your method and working clear.

(3)

(g) Use your results to write down the smallest interval that must contain the optimal cost of Srinjoy’s route.

(2)

题目中文翻译

下表表示一个完整网络，显示了八个城市 A、B、C、D、E、F、G 和 H 之间的最小旅行成本。

	A	B	C	D	E	F	G	H
A	-	36	38	40	23	39	38	35
B	36	-	35	36	35	34	41	38
C	38	35	-	39	25	32	40	40
D	40	36	39	-	37	37	26	33
E	23	35	25	37	-	42	24	43
F	39	34	32	37	42	-	45	38
G	38	41	40	26	24	45	-	40
H	35	38	40	33	43	38	40	-

Srinjoy 必须每个城市至少访问一次。他将从 A 出发并回到 A，并希望最小化总成本。

(a) 使用 Prim 算法，从 A 开始，找到此网络的最小生成树。必须按选择顺序列出构成树的弧。

(3)

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

(1)

(d) 证明从 A 出发有两条最近邻路线。必须清楚说明路线及其对应的成本。

(4)

(e) 写出使用 (c) 和 (d) 的答案可以获得的最佳上界。

(1)

(f) 通过删除 A 及其所有弧，找到 Srinjoy 路线总成本的下界。必须清楚说明方法和计算过程。

(3)

(g) 使用你的结果写出必须包含 Srinjoy 路线最优成本的最小区间。

(2)

解答

(a)

解法一

思路

展开

从 A 开始，每次在已选顶点与未选顶点之间找权重最小的边，把新顶点接入树。按实际顺序写出七条边，不把最近邻算法误当成 Prim 算法。

答题过程

展开

Applying Prim’s algorithm from A gives:

Step	Arc selected	Weight	New vertex
1	AE	23	E
2	EG	24	G
3	CE	25	C
4	DG	26	D
5	CF	32	F
6	DH	33	H
7	BF	34	B

Thus the selection order is

\begin{aligned} &\,AE,\ EG,\ CE,\ DG,\\ &\,\hspace{2pt}CF,\ DH,\ BF. \end{aligned}

(b)

解法一

思路

展开

把 (a) 的七条边的权重相加，不重复计入任何边。

答题过程

展开

The weight of the minimum spanning tree is

\begin{align*} &\,23+24+25+26\\ &\,\hspace{2pt}+32+33+34\\ =&\,\boxed{197}. \end{align*}

(c)

解法一

思路

展开

把最小生成树中的每条边走两次，可以形成访问所有顶点并回到起点的闭合路线。总成本是树权重的两倍，因此给出初始上界。

答题过程

展开

Traversing every arc of the minimum spanning tree twice gives an initial upper bound of

2(197)=\boxed{394}.

(d)

解法一

思路

展开

最近邻前五个顶点为 A、E、G、D、H。到 H 后，未访问的 B 与 F 都距 H 为 38，因此分成两条路线；两条都要继续遵守最近邻规则，并回到 A。

答题过程

展开

The nearest-neighbour choices initially give

A-E-G-D-H.

At H, the costs to the unvisited cities B and F are both 38, while the cost to C is 40. Hence there are two choices.

If B is chosen next, the route is

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

with cost

\begin{align*} &\,23+24+26+33\\ &\,\hspace{2pt}+38+34+32+38\\ =&\,\boxed{248}. \end{align*}

If F is chosen next, the route is

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

with cost

\begin{align*} &\,23+24+26+33\\ &\,\hspace{2pt}+38+32+35+36\\ =&\,\boxed{247}. \end{align*}

(e)

解法一

思路

展开

比较 (c) 的 394 与 (d) 的 248、247。上界取较小者；这里是第二条最近邻巡回的成本 247。

答题过程

展开

The best upper bound is

\min(394,248,247)=\boxed{247}.

(f)

解法一

思路

展开

先删除 A 与所有连接 A 的边，对其余七个城市求最小生成树，再加回与 A 相连的两条最短边。原树中 A 只通过 AE 接入，删除 AE 后留下的树权重为 174；也可从剩余六条边直接相加确认。

答题过程

展开

After deleting A, a reduced minimum spanning tree contains

\begin{aligned} &\,EG(24),\ CE(25),\\ &\,\hspace{2pt}DG(26),\ CF(32),\\ &\,\hspace{4pt}DH(33),\ BF(34). \end{aligned}

Its weight is

\begin{align*} &\,24+25+26\\ &\,\hspace{2pt}+32+33+34\\ =&\,174. \end{align*}

Equivalently, this is the tree in (a) with AE removed, giving 197 - 23 = 174.

The two smallest arcs incident to A are AE(23) and AH(35). Therefore a lower bound is

174+23+35=\boxed{232}.

(g)

解法一

思路

展开

(f) 给出下界 232，(e) 给出较好的上界 247。把两者组合即可，不使用较差的初始上界 394。

答题过程

展开

Let C be the optimal cost. Using (e) and (f),

\boxed{232\leqslant C\leqslant247}.

	A	B	C	D	E	F	G	H
A	-	36	38	40	23	39	38	35
B	36	-	35	36	35	34	41	38
C	38	35	-	39	25	32	40	40
D	40	36	39	-	37	37	26	33
E	23	35	25	37	-	42	24	43
F	39	34	32	37	42	-	45	38
G	38	41	40	26	24	45	-	40
H	35	38	40	33	43	38	40	-

	A	B	C	D	E	F	G	H
A	-	36	38	40	23	39	38	35
B	36	-	35	36	35	34	41	38
C	38	35	-	39	25	32	40	40
D	40	36	39	-	37	37	26	33
E	23	35	25	37	-	42	24	43
F	39	34	32	37	42	-	45	38
G	38	41	40	26	24	45	-	40
H	35	38	40	33	43	38	40	-

	A	B	C	D	E	F	G	H
A	-	36	38	40	23	39	38	35
B	36	-	35	36	35	34	41	38
C	38	35	-	39	25	32	40	40
D	40	36	39	-	37	37	26	33
E	23	35	25	37	-	42	24	43
F	39	34	32	37	42	-	45	38
G	38	41	40	26	24	45	-	40
H	35	38	40	33	43	38	40	-

	A	B	C	D	E	F	G	H
A	-	36	38	40	23	39	38	35
B	36	-	35	36	35	34	41	38
C	38	35	-	39	25	32	40	40
D	40	36	39	-	37	37	26	33
E	23	35	25	37	-	42	24	43
F	39	34	32	37	42	-	45	38
G	38	41	40	26	24	45	-	40
H	35	38	40	33	43	38	40	-

D1 2021 Oct Q3

题目

解答

(a)

解法一

思路

答题过程

(b)

解法一

思路

答题过程

(c)

解法一

思路

答题过程

(d)

解法一

思路

答题过程

(e)

解法一

思路

答题过程

(f)

解法一

思路

答题过程

(g)

解法一

思路

答题过程

	A	B	C	D	E	F	G	H
A	-	36	38	40	23	39	38	35
B	36	-	35	36	35	34	41	38
C	38	35	-	39	25	32	40	40
D	40	36	39	-	37	37	26	33
E	23	35	25	37	-	42	24	43
F	39	34	32	37	42	-	45	38
G	38	41	40	26	24	45	-	40
H	35	38	40	33	43	38	40	-

	A	B	C	D	E	F	G	H
A	-	36	38	40	23	39	38	35
B	36	-	35	36	35	34	41	38
C	38	35	-	39	25	32	40	40
D	40	36	39	-	37	37	26	33
E	23	35	25	37	-	42	24	43
F	39	34	32	37	42	-	45	38
G	38	41	40	26	24	45	-	40
H	35	38	40	33	43	38	40	-