算法分析與設計課程中活動安排問題的教學探討

劉文強 周波 馬海峰 陶貴麗 韓娜

摘 要：闡述了算法分析與設計課程中活動安排問題的求解方法，給出了問題的貪心準則，根據貪心準則設計了貪心求解算法。利用該算法解決了一道程序設計競賽題目，即海岸雷達監控問題。通過該問題的求解，有助于學生舉一反三，啟發學生思維，以學致用，提高問題求解能力。

關鍵詞：活動安排問題；海岸雷達監控問題；貪心準則

中圖分類號：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