题目

Problem

The table shows the shortest distances, in miles, between ten towns, A, B, C, D, E, F, G, H, J and K.

	A	B	C	D	E	F	G	H	J	K
A	–	16	26	19	22	34	30	41	45	36
B	16	–	10	15	38	33	40	25	29	20
C	26	10	–	12	39	30	31	15	19	10
D	19	15	12	–	33	18	25	28	31	22
E	22	38	39	33	–	15	8	33	20	29
F	34	33	30	18	15	–	7	24	19	28
G	30	40	31	25	8	7	–	25	12	21
H	41	25	15	28	33	24	25	–	13	5
J	45	29	19	31	20	19	12	13	–	9
K	36	20	10	22	29	28	21	5	9	–

(a) Explain the difference between the classical Travelling Salesman Problem and the practical Travelling Salesman Problem.

(2)

Kenzo must visit each town at least once, starting and finishing at A. Kenzo wishes to minimise the total distance travelled.

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

(3)

(1)

(d) Use the nearest neighbour algorithm, starting at A, to find another upper bound for the length of Kenzo’s route. Write down the route that gives this upper bound.

(3)

Using the answer to part (d), and given that the length of the nearest neighbour route starting at G is 145 miles,

(e) state which of these two nearest neighbour routes gives the better upper bound. Give a reason for your answer.

(1)

(f) By deleting A and all of its arcs, obtain a lower bound for the length of Kenzo’s route.

(2)

(g) State the smallest interval that must contain the optimal length of Kenzo’s route.

(1)

题目中文翻译

下表显示了十个城镇 A、B、C、D、E、F、G、H、J 和 K 之间的最短距离（单位：英里）。

	A	B	C	D	E	F	G	H	J	K
A	–	16	26	19	22	34	30	41	45	36
B	16	–	10	15	38	33	40	25	29	20
C	26	10	–	12	39	30	31	15	19	10
D	19	15	12	–	33	18	25	28	31	22
E	22	38	39	33	–	15	8	33	20	29
F	34	33	30	18	15	–	7	24	19	28
G	30	40	31	25	8	7	–	25	12	21
H	41	25	15	28	33	24	25	–	13	5
J	45	29	19	31	20	19	12	13	–	9
K	36	20	10	22	29	28	21	5	9	–

(a) 解释经典旅行商问题和实际旅行商问题之间的区别。

Kenzo 必须访问每个城镇至少一次，从 A 出发并回到 A。Kenzo 希望最小化总行驶距离。

(b) 使用 Prim 算法，从 A 出发，求网络的最小生成树。必须清楚说明选择弧的顺序。

(d) 使用最近邻算法，从 A 出发，求 Kenzo 路线长度的另一个上界。写出给出此上界的路线。

利用 (d) 的答案，并已知从 G 出发的最近邻路线长度为 145 英里，

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

(f) 通过删除 A 及其所有弧，求 Kenzo 路线长度的下界。

(g) 说明必须包含 Kenzo 路线最优长度的最小区间。

解答

(a)

解法一

思路

展开

两类旅行商问题都要求最后回到起点。区别在于经典问题要求每个顶点恰好访问一次，而实际问题允许为利用现实道路网络而重复访问顶点，只要求每个顶点至少访问一次。

答题过程

展开

In the classical Travelling Salesman Problem, every vertex is visited exactly once before returning to the starting vertex.

In the practical Travelling Salesman Problem, every vertex is visited at least once before returning to the starting vertex, so vertices may be revisited.

(b)

解法一

思路

展开

从 A 开始使用 Prim 算法，每一步选择连接“已纳入树的顶点”与“尚未纳入树的顶点”的最短弧。选完 JK 后，CD 与 GJ 的权均为 12，因此两者的先后顺序可以互换；之后的弧与最小生成树总权不变。

答题过程

展开

Starting at A, one valid order of selection is

Step	Selected arc	Weight
1	AB	16
2	BC	10
3	CK	10
4	KH	5
5	KJ	9
6	CD	12
7	JG	12
8	FG	7
9	EG	8

Since CD and JG both have weight 12, the following order is also valid:

AB,\ BC,\ CK,\ KH,\ KJ,\ JG,\ FG,\ EG,\ CD.

Thus a minimum spanning tree consists of

\boxed{AB,\ BC,\ CK,\ KH,\ KJ,\ CD,\ JG,\ FG,\ EG}.

Its total weight is

16+10+10+5+9+12+12+7+8=89\text{ miles}.

(c)

解法一

思路

展开

将最小生成树的每条弧往返一次，便能从 A 出发、访问所有顶点并回到 A。因此把 (b) 的最小生成树总权乘以 2，得到初始上界。

答题过程

展开

Doubling the weight of the minimum spanning tree gives the initial upper bound

2(89)=\boxed{178\text{ miles}}.

(d)

解法一

思路

展开

从 A 出发，每次移动到尚未访问的最近城镇；全部城镇访问后再回到 A。必须写出完整路线，并把最后返回 A 的距离计入总长度。

答题过程

展开

The nearest neighbour route starting at A is

A-B-C-K-H-J-G-F-E-D-A.

Its length is

\begin{align*} &\,16+10+10+5+13\\ +&\,12+7+15+33+19\\ =&\,140. \end{align*}

Hence another upper bound is

\boxed{140\text{ miles}},

given by the route $\boxed{A-B-C-K-H-J-G-F-E-D-A}$ .

(e)

解法一

思路

展开

两个数都是可行路线长度，因此都是上界；其中较小的上界更接近未知的最优路线长度，所以比较 140 与 145 即可。

答题过程

展开

The nearest neighbour route starting at A gives the better upper bound because

140<145.

Therefore, the better upper bound is

\boxed{140\text{ miles}}.

(f)

解法一

思路

展开

删除 A 后，(b) 的最小生成树只需移除 AB，剩余八条弧仍连接其余九个顶点。再加入与 A 相连的两条最短弧 AB、AD，所得总权即为旅行商路线长度的下界。

答题过程

展开

Deleting A removes AB, of weight 16, from the minimum spanning tree. The remaining spanning tree has weight

89-16=73.

The two shortest arcs incident to A are AB and AD, with weights 16 and 19. Therefore, the lower bound is

\begin{align*} 73+(16+19)=&\,108. \end{align*}

Hence the required lower bound is

\boxed{108\text{ miles}}.

(g)

解法一

思路

展开

(f) 给出最优长度的下界，而 (e) 给出目前最小的上界。把二者合并，便得到必须包含最优长度的最小区间。

答题过程

展开

Let $L$ be the optimal route length. From parts (e) and (f),

\boxed{108\leqslant L\leqslant140}.

	A	B	C	D	E	F	G	H	J	K
A	–	16	26	19	22	34	30	41	45	36
B	16	–	10	15	38	33	40	25	29	20
C	26	10	–	12	39	30	31	15	19	10
D	19	15	12	–	33	18	25	28	31	22
E	22	38	39	33	–	15	8	33	20	29
F	34	33	30	18	15	–	7	24	19	28
G	30	40	31	25	8	7	–	25	12	21
H	41	25	15	28	33	24	25	–	13	5
J	45	29	19	31	20	19	12	13	–	9
K	36	20	10	22	29	28	21	5	9	–

	A	B	C	D	E	F	G	H	J	K
A	–	16	26	19	22	34	30	41	45	36
B	16	–	10	15	38	33	40	25	29	20
C	26	10	–	12	39	30	31	15	19	10
D	19	15	12	–	33	18	25	28	31	22
E	22	38	39	33	–	15	8	33	20	29
F	34	33	30	18	15	–	7	24	19	28
G	30	40	31	25	8	7	–	25	12	21
H	41	25	15	28	33	24	25	–	13	5
J	45	29	19	31	20	19	12	13	–	9
K	36	20	10	22	29	28	21	5	9	–

	A	B	C	D	E	F	G	H	J	K
A	–	16	26	19	22	34	30	41	45	36
B	16	–	10	15	38	33	40	25	29	20
C	26	10	–	12	39	30	31	15	19	10
D	19	15	12	–	33	18	25	28	31	22
E	22	38	39	33	–	15	8	33	20	29
F	34	33	30	18	15	–	7	24	19	28
G	30	40	31	25	8	7	–	25	12	21
H	41	25	15	28	33	24	25	–	13	5
J	45	29	19	31	20	19	12	13	–	9
K	36	20	10	22	29	28	21	5	9	–

	A	B	C	D	E	F	G	H	J	K
A	–	16	26	19	22	34	30	41	45	36
B	16	–	10	15	38	33	40	25	29	20
C	26	10	–	12	39	30	31	15	19	10
D	19	15	12	–	33	18	25	28	31	22
E	22	38	39	33	–	15	8	33	20	29
F	34	33	30	18	15	–	7	24	19	28
G	30	40	31	25	8	7	–	25	12	21
H	41	25	15	28	33	24	25	–	13	5
J	45	29	19	31	20	19	12	13	–	9
K	36	20	10	22	29	28	21	5	9	–

IAL 2025 Jan D1 Q6

题目

解答

(a)

解法一

思路

答题过程

(b)

解法一

思路

答题过程

(c)

解法一

思路

答题过程

(d)

解法一

思路

答题过程

(e)

解法一

思路

答题过程

(f)

解法一

思路

答题过程

(g)

解法一

思路

答题过程

	A	B	C	D	E	F	G	H	J	K
A	–	16	26	19	22	34	30	41	45	36
B	16	–	10	15	38	33	40	25	29	20
C	26	10	–	12	39	30	31	15	19	10
D	19	15	12	–	33	18	25	28	31	22
E	22	38	39	33	–	15	8	33	20	29
F	34	33	30	18	15	–	7	24	19	28
G	30	40	31	25	8	7	–	25	12	21
H	41	25	15	28	33	24	25	–	13	5
J	45	29	19	31	20	19	12	13	–	9
K	36	20	10	22	29	28	21	5	9	–

	A	B	C	D	E	F	G	H	J	K
A	–	16	26	19	22	34	30	41	45	36
B	16	–	10	15	38	33	40	25	29	20
C	26	10	–	12	39	30	31	15	19	10
D	19	15	12	–	33	18	25	28	31	22
E	22	38	39	33	–	15	8	33	20	29
F	34	33	30	18	15	–	7	24	19	28
G	30	40	31	25	8	7	–	25	12	21
H	41	25	15	28	33	24	25	–	13	5
J	45	29	19	31	20	19	12	13	–	9
K	36	20	10	22	29	28	21	5	9	–