刘文强 周波 马海峰 陶贵丽 韩娜

摘 要：阐述了算法分析与设计课程中活动安排问题的求解方法，给出了问题的贪心准则，根据贪心准则设计了贪心求解算法。利用该算法解决了一道程序设计竞赛题目，即海岸雷达监控问题。通过该问题的求解，有助于学生举一反三，启发学生思维，以学致用，提高问题求解能力。

关键词：活动安排问题；海岸雷达监控问题；贪心准则

中图分类号：G642 文献标志码：A 文章编号：2096-000X（2018）20-0096-03

Abstract： The method of solving the activity arrangement problem in the algorithm analysis and design course is introduced， the greedy criterion of the problem is given， and a greedy algorithm is designed according to the greedy criterion. The algorithm is applied to solve a programming competition problem， namely coastal radar monitoring. Through solving this problem， it helps students draw inferences and draw lessons from others， inspire students' thinking， learn to use and improve problem-solving ability.

Keywords： activity arrangement problem； coastal radar monitoring problem； greedy criterion

在算法分析与设计课程中，活动安排问题是一个可用贪心方法求解的经典问题，该问题是一个十分实用的问题，利用该问题可以有效地求解许多实际问题。

该问题描述为：设S={1，2，…，n}是活动的集合，其中1，2，…，n表示的是n个活动的编号，每项活动有一个开始时间和一个结束时间，对于任意给定的两个活动i和j来说，设si和fi分别是活动i的开始时间和结束时间，sj和fj分别是活动j的开始时间和结束时间，如果有si≥fj或者sj≥fi，则活动i的发生时间段与活动j的发生时间段不冲突，安排完活动i后可以安排活动j，或者是安排完活动j后可以安排活动i。问题是如何从这n个活动中选出一些活动来安排，使得被安排的活动数目最多。即要求的就是集合S的一个子集A，A中任意两个活动都是不冲突的，而且A中活动的数目还是最多的。

例如，有11个活动要使用同一个会场，各个活动的开始时间和结束时间如表1所示。

则活动集合{1，8，11}是一个可行的安排方案，集合中任意两个活动都不冲突，被安排的活动数目为3；活动集合{2，6，9，11}也是一个可行的安排方案，集合中任意两个活动也不冲突，被安排的活动数目为4；活动集合{4，6，10，11}也是一个可行的安排方案，集合中任意两个活动也不冲突，被安排的活动数目也为4；显然，不存在包含大于4个互不冲突活动的活动集合，因此，包含了4个互不冲突活动的活动集合就是该问题的最优解，即活动集合{2，6，9，11}和活动集合{4，6，10，11}都可看成是该问题的最优解。

一、活动安排问题的贪心算法

用贪心法求解问题时，首要任务是确定它的贪心准则（最佳选择标准），即究竟应该按照什么样的方式来选择下一个要安排的活动，才最有可能选择出问题的最优解，也就是说究竟应该按照什么方式来选择下一个活动，才能既保证安排了一个活动，又留下了更多的时间去安排其他活动呢？要达到这个目的，只需优先选择当前结束时间最早的那个活动，即按照各个活动的结束时间从小到大的次序来逐一考虑各个活动，只要当前活动能与之前选择的活动不冲突，就选择当前的活动。因为直觉告诉我们，先安排结束时间早的活动，不仅安排了一个活动，还留下了尽可能多的时间去安排其他活动。

例如，对于表1中给出的包括11个活动的活动安排问题实例来说，按照早结束的活动优先安排的原则，应先安排活动2，安排完活动2后，考察当前结束时间最早的活动4，由于活动4与活动2冲突，所以不安排；再考察当前结束时间最早的活动1，活动1与活动2也冲突，所以不安排；再考察当前结束时间最早的活动6，由于活动6与活动2不冲突，所以安排活动6；再考察当前结束时间最早的活动5，由于活动5与活动6冲突，所以不安排；再考察当前结束时间最早的活动7，活动7与活动6冲突，不安排；再考察當前结束时间最早的活动8，活动8与活动6也冲突，不安排；再考察当前结束时间最早的活动9，由于活动9与活动6不冲突，所以安排活动9；再考察当前结束时间最早的活动10，由于活动10与活动9冲突，所以不安排；再考察当前结束时间最早的活动3，由于活动3与活动9冲突，所以不安排；再考察当前结束时间最早的活动11，由于活动11与活动9不冲突，所以安排活动11；由此得到的解为A={2，6，9，11}，显然它是该问题的一个最优解。

下面设计活动安排问题的贪心算法，用active结构体类型来表示活动的数据类型，它应包含三个成员，用整型变量num来表示一个活动的编号，用整型变量s来表示一个活动的开始时间，用整型变量f来表示一个活动的结束时间，其类型定义如下。

struct active{ int num； float s； float f； }；

活动安排问题的贪心算法如下。

struct active a[100]，t；

int active_greedy（int n） {

int k，i，j，count=0；

for（i=1；i<=n；i++） a[i].num=i；

for（j=1；jfor（i=1；i<=n-j；i++）

if（a[i].f>a[i+1].f）{t=a[i]；a[i]=a[i+1]；a[i+1]=t； }

printf（“%d ”，a[1].num）； count++； k=1；

for（i=2；i<=n；i++）

if（a[i].s>=a[k].f）{

printf（“%d ”，a[i].num）； count++； k=i；

}

return count；

}

二、活动安排问题的应用-求解海岸雷达监控问题

（一）问题描述

海岸雷達监控问题是北京大学在线评测系统（POJ）中的一道程序设计竞赛题目，编号为1328，可以应用活动安排问题的贪心算法来求解该问题。该问题描述如下。

为了有效的监控我国海洋各岛屿，海军某部决定部署专门的雷达来进行监控。现在在一个直角坐标系中考虑这个问题，如图1所示。

假设海岸线为直角坐标系中的x轴，x轴上方表示海，下方表示陆地。在海洋上分布着一些小岛，现在海军某部决定在海岸线上部署一些雷达，每个雷达能够覆盖半径为d的圆形区域，海洋中的一个岛屿能够被雷达覆盖到，当且仅当它和某个雷达之间的距离小于或等于d。给定海洋中各个岛屿的位置坐标（x，y）、岛屿的个数n和雷达的覆盖半径d，问题是求能监控到所有岛屿所需要部署的最少雷达数目。

（二）问题分析

在图1所给实例中共有三个岛屿P1（1，2），P2（-3，1），P3（2，1），雷达覆盖半径为2，显然部署两个雷达就可以监控这三个岛屿，P2由一个雷达监控，图1中给出的雷达位置坐标是（-2，0），显然以点（-2，0）为圆心，半径为2的圆可以明显覆盖该岛屿。而P1和P3这两个岛屿则由同一个雷达监控，雷达位置坐标是（1，0），显然以点（1，0）为圆心，半径为2的圆能够恰好覆盖岛屿P1，岛屿P1在圆的边缘上，而且可以明显覆盖岛屿P3。

对于坐标为（xi，yi）的岛屿Pi来说，当d