《武汉工程大学学报》
2014年04期
76-78
出版日期：
2014-04-30
ISSN:
1674-2869
CN:
42-1779/TQ
闭区间有限覆盖的算法
0引言许多实际问题可抽象成为闭区间（或闭区域）的有限覆盖问题.如，对发生在海洋某区域的海难进行搜救，参与搜救的各种设备（如舰船、飞机、卫星）所能探测范围有限且不同，如何有效地利用这些设备，对疑拟区域进行搜救，是一个利用多种设备的探测区域去覆盖疑拟区域的问题.又如，有m个居民小区，需配置n台信号发射设备覆盖它(m>n)，如何经济地购买与配置n台发射设备，是一个多区域的覆盖问题.有限覆盖定理［12］是一个著名的数学定理，它给出了这样一个结论：若开区间集S覆盖闭区间［a,b］，则S中存在有限个开区间也覆盖［a,b］.该定理的证明多为存在性的，并非构造性的，即没有给出覆盖［a,b］的开区间挑选方法.本文根据贪心法［34］，讨论了两种求闭区间有限覆盖的算法，并用计算机对所提出的算法进行了摸拟测试.1多个闭区间的覆盖问题1.1问题的提出用i来表示x轴上坐标为［i，i+1］的闭区间，对于任意给定的m个互异正整数，就有m个这样的闭区间.现在要求画若干条线段覆盖住这些闭区间.其条件是：线段的数目为n，每条线段可以任意长，但要求所画线段的长度之和最小.1.2求解分析将m个互异正整数按升序排序，并存入m维的一维数组p中，讨论如下：（1）当n≥m时：可用m条长度为1的线段覆盖所有闭区间，线段总长的最小值为m.（2）当n=1时：显然，用一条长度为p(m)-p(1)+1的线段可以覆盖住所有闭区间.（3）当n=2时：欲用2条线段覆盖住所有的闭区间，等价于将n=1时的覆盖线段分为两部分，分别覆盖住左边和右边的闭区间，即在m个闭区间中的某两个不相邻区间之间断开(如图1所示) . 图1多区间的覆盖方法Fig.1Method of covering intervals如果在p(1)与p(2)之间断开，线段的长度将会减少p(2)-p(1)-1.要获得最小的线段总长，需找到间隔距离最大的两个区间，在它们之间断开即寻找d(i)=p(i+1)-p(i)-1(1≤i≤m-1)中的最大者.（4）当n=3时：应在n=2时的某种覆盖方案下，将某条线段断成两截，为了得到当前情况下的最小总长，同样应该在间隔最大的两个区间之间断开.如果原方案是n=2时总长最小的方案，那么这一操作可以得到n=3时总长最小的方案.类似地，当n=k(k>1)时，只要在n=k-1时总长最小的覆盖方案下，找到被同一条线段覆盖的间隔最大的两个区间，从间隔处断开，就可以得到n=k时的最佳覆盖方案.据上述分析，多区间覆盖问题是一个多阶段决策问题，它满足最优化原理，可运用贪心法来求解.1.3算法步骤一：输入m个互异正整数，作升序排序，存入一维数组p；输入覆盖线段数n.步骤二：计算两个相邻区间的间隔距离、间隔区间的左右端点，并存入二维数组gap中，即gap(1,i)=p(i+1)-p(i)-1，gap(2,i)=p(i)+1，gap(3,i)=p(i+1)(i=1,2,…,m-1).步骤三：对gap中各列，按第一行作降序排序.步骤四：如果n≥m，用从p(i)到p(i)+1的线段覆盖区间(i=1,2,…,m)，输出总长length=m，线段数num=m；步骤五：如果n=1，用从p(1)到p(m)+1的线段覆盖区间，输出总长length=p(m)-p(1)+1，线段数num=1；步骤六：如果2≤n
0且di最大（这就是贪心策略）.具体的挑选过程为：在开区间Ii=(ai,bi)(i=1,2,…,n)中，做第一轮挑选.对所有的ai
b-a，Ir覆盖a，且覆盖［a,b］；情况3:0
d，则d=I(i,2)-a，r=i（3）如果r>0，则m=m+1，S(m,1)=I(r,1)，S(m,2)=I(r,2)（4）如果d=0,则标识变量flag=0，退出挑选操作.（5）如果d>b-a，则标识变量flag=1，退出挑选操作.（6）如果0
/m，做以下操作（1）用从p(1)到p(m)+1的线段覆盖区间，置总长length=p(m)-p(1)+1，线段数num=1；（2）当num