题目

Problem

Pupils from ten schools are visiting a museum on the same day. The museum needs to allocate each school to a tour group. The maximum size of each tour group is 42 pupils. A group may include pupils from more than one school. Pupils from each school must be kept in the same tour group. The numbers of pupils visiting from each school are given below.

8, 17, 9, 14, 18, 12, 22, 10, 15, 7

(a) Calculate a lower bound for the number of tour groups required. You must make your method clear.

(2)

(b) Using the above list, apply the first-fit bin packing algorithm to allocate the pupils visiting from each school to tour groups.

(2)

The above list of numbers is to be sorted into descending order.

(c) Perform a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.

(4)

(d) Using your sorted list from (c), apply the first-fit decreasing bin packing algorithm to obtain a second allocation of pupils to tour groups.

(2)

Figure 4 shows the corridors in the museum. The number on each arc is the length, in metres, of the corresponding corridor. Sally is a tour guide in the museum and she must travel along each corridor at least once during each tour. Sally wishes to minimise the length of her route. She must start and finish at the museum’s entrance at A.

(e) Use an appropriate algorithm to find the corridors that Sally will need to traverse twice. You should make your method and working clear.

(4)

(f) Write down a possible shortest route, giving its length.

(2)

Sally is now allowed to start at H and finish her route at a different vertex. A route of minimum length that includes each corridor at least once needs to be found.

(g) State the finishing vertex of Sally’s new route and calculate the difference in length between this new route and the route found in (f).

(2)

(Total 18 marks)

题目中文翻译

来自十所学校的学生将在同一天参观博物馆。博物馆需要将每所学校分配到一个导览团。每个导览团的最大人数为 42 人。一个团可以包含来自多所学校的学生。来自同一所学校的学生必须分配在同一个导览团中。来自每所学校的学生人数如下。

8、17、9、14、18、12、22、10、15、7

(a) 计算所需导览团数量的下界。你必须清楚说明你的方法。

(b) 使用上面的列表，应用首次适应装箱算法将来自每所学校的学生分配到导览团。

上面的数字列表需要按降序排列。

(d) 使用你从 (c) 得到的有序列表，应用首次适应递减装箱算法获得学生的第二次分配方案。

图 4 显示了博物馆内的走廊。每条弧上的数字是相应走廊的长度（单位：m）。Sally 是博物馆的导览员，她必须在每次导览中至少经过每条走廊一次。Sally 希望最小化她的路线长度。她必须从博物馆入口 A 出发并回到 A。

(e) 使用适当的算法找到 Sally 需要经过两次的走廊。你应该清楚说明你的方法和计算过程。

(f) 写出一条可能的最短路线，并给出其长度。

Sally 现在被允许从 H 出发并在不同的顶点结束她的路线。需要找到一条包含每条走廊至少一次的最短路线。

(g) 说明 Sally 新路线的结束顶点，并计算这条新路线与 (f) 中找到的路线之间的长度差。

解答

(a)

解法一

思路

展开

先把十所学校人数相加，再除以每团容量 42。所得结果不是整数时必须向上取整，因为每所学校都必须被分配，且不能使用不足一个的导览团。

答题过程

展开

The total number of pupils is

8+17+9+14+18+12+22+10+15+7=132.

Therefore

\frac{132}{42}=3.142\ldots,

so a lower bound is

\boxed{4\text{ tour groups}}.

(b)

解法一

思路

展开

按原顺序逐个处理学校人数，每次放入第一个仍有足够容量的导览团；若所有已有团都放不下，才建立新团。

答题过程

展开

Applying first fit in the given order gives

Group	Numbers of pupils	Total
1	$8,17,9,7$	$41$
2	$14,18,10$	$42$
3	$12,22$	$34$
4	$15$	$15$

(c)

解法一

思路

展开

采用官方评分资料中的 middle-right 选取方式。每个子列表取中间偏右的数为 pivot，把较大值保留在左侧、较小值放在右侧，并同时处理各个尚未完成的子列表。

答题过程

展开

Using middle-right pivots:

Pass	Pivot(s)	Result
1	$12$	$17,14,18,22,15,12,8,9,10,7$
2	$18,10$	$22,18,17,14,15,12,10,8,9,7$
3	$14,9$	$22,18,17,15,14,12,10,9,8,7$
4	$15,7$	$22,18,17,15,14,12,10,9,8,7$

The sort is complete, giving

\boxed{22,18,17,15,14,12,10,9,8,7}.

解法二

思路

展开

也可使用官方接受的 middle-left 选取方式。偶数长度子列表改取中间偏左的数，因此需要的趟数与中间结果不同，但最终降序列表相同。

答题过程

展开

Using middle-left pivots:

Pass	Pivot(s)	Result
1	$18$	$22,18,8,17,9,14,12,10,15,7$
2	$14$	$22,18,17,15,14,8,9,12,10,7$
3	$17,12$	$22,18,17,15,14,12,8,9,10,7$
4	$9$	$22,18,17,15,14,12,10,9,8,7$
5	$8$	$22,18,17,15,14,12,10,9,8,7$

Therefore the completed descending list is

\boxed{22,18,17,15,14,12,10,9,8,7}.

(d)

解法一

思路

展开

使用 (c) 的降序列表按 first fit 依次装入。前三个导览团分别达到 40、42、42 人，最后剩下 8 人单独组成第四团。

答题过程

展开

Applying first-fit decreasing gives

Group	Numbers of pupils	Total
1	$22,18$	$40$
2	$17,15,10$	$42$
3	$14,12,9,7$	$42$
4	$8$	$8$

(e)

解法一

思路

展开

这是封闭路线巡检问题。原网络的奇点为 B、C、G、H，因此列出三种奇点配对，并分别以最短路径连接每一对；增加总长度最小的配对所含各边需要重复经过。

答题过程

展开

The odd vertices are $B,C,G$ and $H$ . The three possible pairings are:

Pairing	Shortest paths	Added length (m)
$BC+GH$	$B-E-C$ and $G-I-H$	$(11.2+14.5)+(8.3+17.2)=51.2$
$BG+CH$	$B-F-G$ and $C-E-J-H$	$(10.3+15.2)+(14.5+7.5+16.2)=63.7$
$BH+CG$	$B-E-J-H$ and $C-E-F-G$	$(11.2+7.5+16.2)+(14.5+4.3+15.2)=68.9$

The minimum added length is $51.2$ m. Hence the corridors to be traversed twice are

\boxed{BE,\ CE,\ GI\text{ and }HI}.

(f)

解法一

思路

展开

将 (e) 的四条边各重复一次后，所有顶点的度数均为偶数，因此存在从 A 出发并回到 A 的欧拉回路。总长度等于原网络总权 227.2 加最小重复长度 51.2。

答题过程

展开

One possible shortest route is

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

Its length is

227.2+51.2=\boxed{278.4\text{ m}}.

(g)

解法一

思路

展开

开放路线从奇点 H 开始时，另一个端点也应选奇点，使这两个点保留奇度数。比较其余两奇点之间需补上的最短路径：若终点为 C，只需重复 B-F-G，增加 25.5 m，是三种选择中最小的。

答题过程

展开

With $H$ fixed as the starting vertex, the possible finishing vertices and remaining pairings are:

Finish	Remaining pair	Added length (m)
B	$CG$	$14.5+4.3+15.2=34.0$
C	$BG$	$10.3+15.2=25.5$
G	$BC$	$11.2+14.5=25.7$

Therefore Sally should finish at

\boxed{C}.

The new route has length

227.2+25.5=252.7\text{ m},

so the reduction, and hence the difference in length, is

278.4-252.7=\boxed{25.7\text{ m}}.

IAL 2019 June D1 Q3

题目

解答

(a)

解法一

思路

答题过程

(b)

解法一

思路

答题过程

(c)

解法一

思路

答题过程

解法二

思路

答题过程

(d)

解法一

思路

答题过程

(e)

解法一

思路

答题过程

(f)

解法一

思路

答题过程

(g)

解法一

思路

答题过程