劉文強(qiáng) 周波 馬海峰 陶貴麗 韓娜

摘 要：闡述了算法分析與設(shè)計(jì)課程中活動(dòng)安排問題的求解方法，給出了問題的貪心準(zhǔn)則，根據(jù)貪心準(zhǔn)則設(shè)計(jì)了貪心求解算法。利用該算法解決了一道程序設(shè)計(jì)競(jìng)賽題目，即海岸雷達(dá)監(jiān)控問題。通過該問題的求解，有助于學(xué)生舉一反三，啟發(fā)學(xué)生思維，以學(xué)致用，提高問題求解能力。

關(guān)鍵詞：活動(dòng)安排問題；海岸雷達(dá)監(jiān)控問題；貪心準(zhǔn)則

中圖分類號(hào)：G642 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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

在算法分析與設(shè)計(jì)課程中，活動(dòng)安排問題是一個(gè)可用貪心方法求解的經(jīng)典問題，該問題是一個(gè)十分實(shí)用的問題，利用該問題可以有效地求解許多實(shí)際問題。

該問題描述為：設(shè)S={1，2，…，n}是活動(dòng)的集合，其中1，2，…，n表示的是n個(gè)活動(dòng)的編號(hào)，每項(xiàng)活動(dòng)有一個(gè)開始時(shí)間和一個(gè)結(jié)束時(shí)間，對(duì)于任意給定的兩個(gè)活動(dòng)i和j來說，設(shè)si和fi分別是活動(dòng)i的開始時(shí)間和結(jié)束時(shí)間，sj和fj分別是活動(dòng)j的開始時(shí)間和結(jié)束時(shí)間，如果有si≥fj或者sj≥fi，則活動(dòng)i的發(fā)生時(shí)間段與活動(dòng)j的發(fā)生時(shí)間段不沖突，安排完活動(dòng)i后可以安排活動(dòng)j，或者是安排完活動(dòng)j后可以安排活動(dòng)i。問題是如何從這n個(gè)活動(dòng)中選出一些活動(dòng)來安排，使得被安排的活動(dòng)數(shù)目最多。即要求的就是集合S的一個(gè)子集A，A中任意兩個(gè)活動(dòng)都是不沖突的，而且A中活動(dòng)的數(shù)目還是最多的。

例如，有11個(gè)活動(dòng)要使用同一個(gè)會(huì)場(chǎng)，各個(gè)活動(dòng)的開始時(shí)間和結(jié)束時(shí)間如表1所示。

則活動(dòng)集合{1，8，11}是一個(gè)可行的安排方案，集合中任意兩個(gè)活動(dòng)都不沖突，被安排的活動(dòng)數(shù)目為3；活動(dòng)集合{2，6，9，11}也是一個(gè)可行的安排方案，集合中任意兩個(gè)活動(dòng)也不沖突，被安排的活動(dòng)數(shù)目為4；活動(dòng)集合{4，6，10，11}也是一個(gè)可行的安排方案，集合中任意兩個(gè)活動(dòng)也不沖突，被安排的活動(dòng)數(shù)目也為4；顯然，不存在包含大于4個(gè)互不沖突活動(dòng)的活動(dòng)集合，因此，包含了4個(gè)互不沖突活動(dòng)的活動(dòng)集合就是該問題的最優(yōu)解，即活動(dòng)集合{2，6，9，11}和活動(dòng)集合{4，6，10，11}都可看成是該問題的最優(yōu)解。

一、活動(dòng)安排問題的貪心算法

用貪心法求解問題時(shí)，首要任務(wù)是確定它的貪心準(zhǔn)則（最佳選擇標(biāo)準(zhǔn)），即究竟應(yīng)該按照什么樣的方式來選擇下一個(gè)要安排的活動(dòng)，才最有可能選擇出問題的最優(yōu)解，也就是說究竟應(yīng)該按照什么方式來選擇下一個(gè)活動(dòng)，才能既保證安排了一個(gè)活動(dòng)，又留下了更多的時(shí)間去安排其他活動(dòng)呢？要達(dá)到這個(gè)目的，只需優(yōu)先選擇當(dāng)前結(jié)束時(shí)間最早的那個(gè)活動(dòng)，即按照各個(gè)活動(dòng)的結(jié)束時(shí)間從小到大的次序來逐一考慮各個(gè)活動(dòng)，只要當(dāng)前活動(dòng)能與之前選擇的活動(dòng)不沖突，就選擇當(dāng)前的活動(dòng)。因?yàn)橹庇X告訴我們，先安排結(jié)束時(shí)間早的活動(dòng)，不僅安排了一個(gè)活動(dòng)，還留下了盡可能多的時(shí)間去安排其他活動(dòng)。

例如，對(duì)于表1中給出的包括11個(gè)活動(dòng)的活動(dòng)安排問題實(shí)例來說，按照早結(jié)束的活動(dòng)優(yōu)先安排的原則，應(yīng)先安排活動(dòng)2，安排完活動(dòng)2后，考察當(dāng)前結(jié)束時(shí)間最早的活動(dòng)4，由于活動(dòng)4與活動(dòng)2沖突，所以不安排；再考察當(dāng)前結(jié)束時(shí)間最早的活動(dòng)1，活動(dòng)1與活動(dòng)2也沖突，所以不安排；再考察當(dāng)前結(jié)束時(shí)間最早的活動(dòng)6，由于活動(dòng)6與活動(dòng)2不沖突，所以安排活動(dòng)6；再考察當(dāng)前結(jié)束時(shí)間最早的活動(dòng)5，由于活動(dòng)5與活動(dòng)6沖突，所以不安排；再考察當(dāng)前結(jié)束時(shí)間最早的活動(dòng)7，活動(dòng)7與活動(dòng)6沖突，不安排；再考察當(dāng)前結(jié)束時(shí)間最早的活動(dòng)8，活動(dòng)8與活動(dòng)6也沖突，不安排；再考察當(dāng)前結(jié)束時(shí)間最早的活動(dòng)9，由于活動(dòng)9與活動(dòng)6不沖突，所以安排活動(dòng)9；再考察當(dāng)前結(jié)束時(shí)間最早的活動(dòng)10，由于活動(dòng)10與活動(dòng)9沖突，所以不安排；再考察當(dāng)前結(jié)束時(shí)間最早的活動(dòng)3，由于活動(dòng)3與活動(dòng)9沖突，所以不安排；再考察當(dāng)前結(jié)束時(shí)間最早的活動(dòng)11，由于活動(dòng)11與活動(dòng)9不沖突，所以安排活動(dòng)11；由此得到的解為A={2，6，9，11}，顯然它是該問題的一個(gè)最優(yōu)解。

下面設(shè)計(jì)活動(dòng)安排問題的貪心算法，用active結(jié)構(gòu)體類型來表示活動(dòng)的數(shù)據(jù)類型，它應(yīng)包含三個(gè)成員，用整型變量num來表示一個(gè)活動(dòng)的編號(hào)，用整型變量s來表示一個(gè)活動(dòng)的開始時(shí)間，用整型變量f來表示一個(gè)活動(dòng)的結(jié)束時(shí)間，其類型定義如下。

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

活動(dòng)安排問題的貪心算法如下。

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；

}

二、活動(dòng)安排問題的應(yīng)用-求解海岸雷達(dá)監(jiān)控問題

（一）問題描述

海岸雷達(dá)監(jiān)控問題是北京大學(xué)在線評(píng)測(cè)系統(tǒng)（POJ）中的一道程序設(shè)計(jì)競(jìng)賽題目，編號(hào)為1328，可以應(yīng)用活動(dòng)安排問題的貪心算法來求解該問題。該問題描述如下。

為了有效的監(jiān)控我國(guó)海洋各島嶼，海軍某部決定部署專門的雷達(dá)來進(jìn)行監(jiān)控?，F(xiàn)在在一個(gè)直角坐標(biāo)系中考慮這個(gè)問題，如圖1所示。

假設(shè)海岸線為直角坐標(biāo)系中的x軸，x軸上方表示海，下方表示陸地。在海洋上分布著一些小島，現(xiàn)在海軍某部決定在海岸線上部署一些雷達(dá)，每個(gè)雷達(dá)能夠覆蓋半徑為d的圓形區(qū)域，海洋中的一個(gè)島嶼能夠被雷達(dá)覆蓋到，當(dāng)且僅當(dāng)它和某個(gè)雷達(dá)之間的距離小于或等于d。給定海洋中各個(gè)島嶼的位置坐標(biāo)（x，y）、島嶼的個(gè)數(shù)n和雷達(dá)的覆蓋半徑d，問題是求能監(jiān)控到所有島嶼所需要部署的最少雷達(dá)數(shù)目。

（二）問題分析

在圖1所給實(shí)例中共有三個(gè)島嶼P1（1，2），P2（-3，1），P3（2，1），雷達(dá)覆蓋半徑為2，顯然部署兩個(gè)雷達(dá)就可以監(jiān)控這三個(gè)島嶼，P2由一個(gè)雷達(dá)監(jiān)控，圖1中給出的雷達(dá)位置坐標(biāo)是（-2，0），顯然以點(diǎn)（-2，0）為圓心，半徑為2的圓可以明顯覆蓋該島嶼。而P1和P3這兩個(gè)島嶼則由同一個(gè)雷達(dá)監(jiān)控，雷達(dá)位置坐標(biāo)是（1，0），顯然以點(diǎn)（1，0）為圓心，半徑為2的圓能夠恰好覆蓋島嶼P1，島嶼P1在圓的邊緣上，而且可以明顯覆蓋島嶼P3。

對(duì)于坐標(biāo)為（xi，yi）的島嶼Pi來說，當(dāng)d