题目

Problem

The table below shows the distances, in km, between six data collection points, A, B, C, D, E and F.

	A	B	C	D	E	F
A	–	35	42	55	48	50
B	35	–	40	49	52	31
C	42	40	–	47	53	49
D	55	49	47	–	39	44
E	48	52	53	39	–	52
F	50	31	49	44	52	–

Ferhana must visit each data collection point. She will start and finish at A and wishes to minimise the total distance she travels.

(a) Starting at A, use the nearest neighbour algorithm to obtain an upper bound for the distance Ferhana must travel. Make your method clear.

(2)

(b) Starting by deleting B, and all of its arcs, find a lower bound for the distance Ferhana must travel. Make your calculation clear.

(3)

(Total 5 marks)

题目中文翻译

下表显示了六个数据收集点 A、B、C、D、E 和 F 之间的距离（单位：km）。

	A	B	C	D	E	F
A	–	35	42	55	48	50
B	35	–	40	49	52	31
C	42	40	–	47	53	49
D	55	49	47	–	39	44
E	48	52	53	39	–	52
F	50	31	49	44	52	–

Ferhana 必须访问每个数据收集点。她将从 A 出发并回到 A，希望最小化总行程距离。

(a) 从 A 出发，使用最近邻算法求出 Ferhana 必须行驶距离的上界。请清楚说明你的方法。

(b) 从删除 B 及其所有弧开始，求出 Ferhana 必须行驶距离的下界。请清楚说明你的计算过程。

解答

(a)

解法一

思路

展开

从 A 开始，每一步前往尚未访问点中距离当前点最近的一个，直到六个点全部访问，再返回 A。所得完整巡回路线给出最短巡回距离的一个上界。

答题过程

展开

The nearest-neighbour choices are

\begin{aligned} &\,A\xrightarrow{35}B\xrightarrow{31}F\xrightarrow{44}D,\\ &\,D\xrightarrow{39}E\xrightarrow{53}C\xrightarrow{42}A. \end{aligned}

Therefore the route is

A-B-F-D-E-C-A,

with total length

35+31+44+39+53+42=\boxed{244\text{ km}}.

Thus an upper bound is $244\text{ km}$ .

(b)

解法一

思路

展开

先删去 B 及所有关联边，在余下五个顶点上求限制最小生成树。任何完整巡回路线经过 B 时必须使用两条与 B 相连的边，因此再加回 B 的两条最小关联边，便得到所需下界。

答题过程

展开

With $B$ and all its incident edges deleted, a minimum spanning tree on $A,C,D,E,F$ uses

DE(39),\ AC(42),\ DF(44)\text{ and }CD(47).

Its weight is

39+42+44+47=172\text{ km}.

The two least-weight edges incident to $B$ are

BF=31\text{ km}\qquad\text{and}\qquad BA=35\text{ km}.

Hence the lower bound is

172+31+35=\boxed{238\text{ km}}.

	A	B	C	D	E	F
A	–	35	42	55	48	50
B	35	–	40	49	52	31
C	42	40	–	47	53	49
D	55	49	47	–	39	44
E	48	52	53	39	–	52
F	50	31	49	44	52	–

	A	B	C	D	E	F
A	–	35	42	55	48	50
B	35	–	40	49	52	31
C	42	40	–	47	53	49
D	55	49	47	–	39	44
E	48	52	53	39	–	52
F	50	31	49	44	52	–

	A	B	C	D	E	F
A	–	35	42	55	48	50
B	35	–	40	49	52	31
C	42	40	–	47	53	49
D	55	49	47	–	39	44
E	48	52	53	39	–	52
F	50	31	49	44	52	–

	A	B	C	D	E	F
A	–	35	42	55	48	50
B	35	–	40	49	52	31
C	42	40	–	47	53	49
D	55	49	47	–	39	44
E	48	52	53	39	–	52
F	50	31	49	44	52	–

IAL 2020 Jan D1 Q1

题目

解答

(a)

解法一

思路

答题过程

(b)

解法一

思路

答题过程

	A	B	C	D	E	F
A	–	35	42	55	48	50
B	35	–	40	49	52	31
C	42	40	–	47	53	49
D	55	49	47	–	39	44
E	48	52	53	39	–	52
F	50	31	49	44	52	–

	A	B	C	D	E	F
A	–	35	42	55	48	50
B	35	–	40	49	52	31
C	42	40	–	47	53	49
D	55	49	47	–	39	44
E	48	52	53	39	–	52
F	50	31	49	44	52	–