閉區(qū)間有限覆蓋的算法

江世宏

（武漢工程大學(xué)理學(xué)院，湖北 武漢 430205）

0 引 言

許多實(shí)際問(wèn)題可抽象成為閉區(qū)間（或閉區(qū)域）的有限覆蓋問(wèn)題．如，對(duì)發(fā)生在海洋某區(qū)域的海難進(jìn)行搜救，參與搜救的各種設(shè)備（如艦船、飛機(jī)、衛(wèi)星）所能探測(cè)范圍有限且不同，如何有效地利用這些設(shè)備，對(duì)疑擬區(qū)域進(jìn)行搜救，是一個(gè)利用多種設(shè)備的探測(cè)區(qū)域去覆蓋疑擬區(qū)域的問(wèn)題．又如，有m個(gè)居民小區(qū)，需配置n臺(tái)信號(hào)發(fā)射設(shè)備覆蓋它（m＞n），如何經(jīng)濟(jì)地購(gòu)買(mǎi)與配置n臺(tái)發(fā)射設(shè)備，是一個(gè)多區(qū)域的覆蓋問(wèn)題．有限覆蓋定理［1－2］是一個(gè)著名的數(shù)學(xué)定理，它給出了這樣一個(gè)結(jié)論：若開(kāi)區(qū)間集S覆蓋閉區(qū)間［a，b］，則S中存在有限個(gè)開(kāi)區(qū)間也覆蓋［a，b］．該定理的證明多為存在性的，并非構(gòu)造性的，即沒(méi)有給出覆蓋［a，b］的開(kāi)區(qū)間挑選方法．

本文根據(jù)貪心法［3－4］，討論了兩種求閉區(qū)間有限覆蓋的算法，并用計(jì)算機(jī)對(duì)所提出的算法進(jìn)行了摸擬測(cè)試．

1 多個(gè)閉區(qū)間的覆蓋問(wèn)題

1．1 問(wèn)題的提出

用i來(lái)表示x軸上坐標(biāo)為［i，i＋1］的閉區(qū)間，對(duì)于任意給定的m個(gè)互異正整數(shù)，就有m個(gè)這樣的閉區(qū)間．現(xiàn)在要求畫(huà)若干條線段覆蓋住這些閉區(qū)間．其條件是：線段的數(shù)目為n，每條線段可以任意長(zhǎng)，但要求所畫(huà)線段的長(zhǎng)度之和最?。?/p>

1．2 求解分析

將m個(gè)互異正整數(shù)按升序排序，并存入m維的一維數(shù)組p中，討論如下：

（1）當(dāng)n≥m時(shí)：可用m條長(zhǎng)度為1的線段覆蓋所有閉區(qū)間，線段總長(zhǎng)的最小值為m．

（2）當(dāng)n＝1時(shí)：顯然，用一條長(zhǎng)度為p（m）－p（1）＋1的線段可以覆蓋住所有閉區(qū)間．

（3）當(dāng)n＝2時(shí)：欲用2條線段覆蓋住所有的閉區(qū)間，等價(jià)于將n＝1時(shí)的覆蓋線段分為兩部分，分別覆蓋住左邊和右邊的閉區(qū)間，即在m個(gè)閉區(qū)間中的某兩個(gè)不相鄰區(qū)間之間斷開(kāi)（如圖1所示）．

圖1 多區(qū)間的覆蓋方法Fig．1 Method of covering intervals

如果在p（1）與p（2）之間斷開(kāi)，線段的長(zhǎng)度將會(huì)減少p（2）－p（1）－1．要獲得最小的線段總長(zhǎng)，需找到間隔距離最大的兩個(gè)區(qū)間，在它們之間斷開(kāi)即尋找d（i）＝p（i＋1）－p（i）－1（1≤i≤m－1）中的最大者．

（4）當(dāng)n＝3時(shí)：應(yīng)在n＝2時(shí)的某種覆蓋方案下，將某條線段斷成兩截，為了得到當(dāng)前情況下的最小總長(zhǎng)，同樣應(yīng)該在間隔最大的兩個(gè)區(qū)間之間斷開(kāi)．如果原方案是n＝2時(shí)總長(zhǎng)最小的方案，那么這一操作可以得到n＝3時(shí)總長(zhǎng)最小的方案．

類(lèi)似地，當(dāng)n＝k（k＞1）時(shí)，只要在n＝k－1時(shí)總長(zhǎng)最小的覆蓋方案下，找到被同一條線段覆蓋的間隔最大的兩個(gè)區(qū)間，從間隔處斷開(kāi)，就可以得到n＝k時(shí)的最佳覆蓋方案．

據(jù)上述分析，多區(qū)間覆蓋問(wèn)題是一個(gè)多階段決策問(wèn)題，它滿足最優(yōu)化原理，可運(yùn)用貪心法來(lái)求解．

1．3 算法

步驟一：輸入m個(gè)互異正整數(shù)，作升序排序，存入一維數(shù)組p；輸入覆蓋線段數(shù)n．

步驟二：計(jì)算兩個(gè)相鄰區(qū)間的間隔距離、間隔區(qū)間的左右端點(diǎn)，并存入二維數(shù)組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）．

步驟三：對(duì)gap中各列，按第一行作降序排序．

步驟四：如果n≥m，用從p（i）到p（i）＋1的線段覆蓋區(qū)間（i＝1，2，…，m），輸出總長(zhǎng)length＝m，線段數(shù)num＝m；

步驟五：如果n＝1，用從p（1）到p（m）＋1的線段覆蓋區(qū)間，輸出總長(zhǎng)length＝p（m）－p（1）＋1，線段數(shù)num＝1；

步驟六：如果2≤n＜m，做以下操作

（1）用從p（1）到p（m）＋1的線段覆蓋區(qū)間，置總長(zhǎng)length＝p（m）－p（1）＋1，線段數(shù)num＝1；

（2）當(dāng)num＜n時(shí)，反復(fù)做以下操作

①?gòu)母采w線段中，挖去gap（2，num）至gap（3，num）這一段；

②更新線段總長(zhǎng)length＝length－gap（1，num）；

③更新線段數(shù)num＝num＋1．

（3）輸出總長(zhǎng)length和線段數(shù)num；

在MATLAB下，編寫(xiě)該算法的摸擬檢測(cè)程序，其程序運(yùn)行結(jié)果如圖2所示．

圖2 多區(qū)間覆蓋方法演示程序Fig．2 Program of covering intervals

2 閉區(qū)間的有限覆蓋問(wèn)題

2．1 問(wèn)題的提出

設(shè)有閉區(qū)間［a，b］和開(kāi)區(qū)間集S＝｛（a1，b1），（a2，b2），…，（an，bn）｝，判斷S是否能覆蓋［a，b］，如果能覆蓋，給出［a，b］的一個(gè)有限覆蓋，但要求使覆蓋的開(kāi)區(qū)間個(gè)數(shù)最少．

2．2 求解分析

用二維數(shù)組I存放開(kāi)區(qū)間集（不妨認(rèn)為已對(duì)I中的第一列作了升序排序），即

欲覆蓋閉區(qū)間［a，b］，其關(guān)鍵是如何從開(kāi)區(qū)間集I中挑選出某開(kāi)區(qū)間（ai，bi），覆蓋左端點(diǎn)a．為了能用最少的開(kāi)區(qū)間覆蓋［a，b］，開(kāi)區(qū)間（ai，bi）應(yīng)滿足條件：ai＜a，bi－a＝di＞0且di最大（這就是貪心策略）．

具體的挑選過(guò)程為：在開(kāi)區(qū)間Ii＝（ai，bi）（i＝1，2，…，n）中，做第一輪挑選．對(duì)所有的ai＜a，計(jì)算di＝bi－a，存在著dr＝max｛di｝，選出開(kāi)區(qū)間Ir＝（ar，br），它具有以下3種情況之一（如圖3所示）．情況1：dr≤0，Ir未覆蓋a；情況2：dr＞b－a，Ir覆蓋a，且覆蓋［a，b］；情況3：0＜dr≤b－a，Ir覆蓋a，未覆蓋［a，b］．

圖3 首選開(kāi)區(qū)間的3種可能情況Fig．3 Three cases of first opened interval

對(duì)于情況1，可以斷言，在開(kāi)區(qū)間集I中，無(wú)法挑選出有限個(gè)開(kāi)區(qū)間，實(shí)現(xiàn)對(duì)［a，b］的覆蓋；對(duì)于情況2，可以斷言，開(kāi)區(qū)間Ir＝（ar，br）已實(shí)現(xiàn)對(duì)［a，b］的覆蓋；對(duì)于情況3，取a＝br，縮?。踑，b］，再?gòu)拈_(kāi)區(qū)間Ii＝（ai，bi）（i＝r＋1，r＋2，…，n）中，做新一輪的挑選．

2．3 算法

步驟一：輸入［a，b］，I．

步驟二：獲取I中開(kāi)區(qū)間個(gè)數(shù)n，對(duì)I中第1列作升序排序．

步驟三：置所選開(kāi)區(qū)間個(gè)數(shù)m＝0，取j＝1（即從I中第j＝1個(gè)開(kāi)區(qū)間開(kāi)始進(jìn)行挑選）．

步驟四：當(dāng)j≤n時(shí)，反復(fù)做以下操作：

（1）d＝0（所選開(kāi)區(qū)間對(duì)a的覆蓋距離賦初值），r＝0（所選開(kāi)區(qū)間序號(hào)賦初值）．

（2）對(duì)于i＝j(luò)，j＋1，…，n，反復(fù)做以下操作

如果I（i，1）＜a且I（i，2）－a＞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，則標(biāo)識(shí)變量flag＝0，退出挑選操作．

（5）如果d＞b－a，則標(biāo)識(shí)變量flag＝1，退出挑選操作．

（6）如果0＜d≤b－a，則a＝I（r，2），j＝r＋1，返回第4步．

步驟五：如果flag＝0，輸出“不能覆蓋”信息；否則，輸出“可以覆蓋”信息，并輸出S中所存儲(chǔ)的m個(gè)開(kāi)區(qū)間．

在MATLAB下，編寫(xiě)該算法的模擬檢測(cè)程序，其程序運(yùn)行結(jié)果如圖4所示．

圖4 閉區(qū)間覆蓋方法演示程序Fig．4 Program of covering closed interval

3 結(jié) 語(yǔ)

閉區(qū)間有限覆蓋問(wèn)題，在經(jīng)濟(jì)、管理、軍事、計(jì)算機(jī)和數(shù)學(xué)領(lǐng)域里，具有十分廣泛的應(yīng)用，對(duì)該問(wèn)題的研究，有待進(jìn)一步深化．例如，還可以討論，在要求所有覆蓋閉區(qū)間的開(kāi)區(qū)間總長(zhǎng)最小的條件下，算法的設(shè)計(jì)問(wèn)題．

致謝

感謝國(guó)家科技部和武漢工程大學(xué)對(duì)本項(xiàng)目的資助！

［1］郭改慧，李兵方．有限覆蓋定理的應(yīng)用［J］．牡丹江大學(xué)學(xué)報(bào)，2013，22（10）：103－104．

［2］關(guān)金玉，徐永春，祁建芳．用完全覆蓋證明實(shí)數(shù)系中若干定理［J］．河北北方學(xué)院學(xué)報(bào)：自然科學(xué)版，2006，22（3）：6－7．GUAN Jin－yu，XU Yong－chun，QI Jian－fang．To prove several theorems in real number field by using full covering theorem［J］．Journal of Hebei North University：Natural Science Edition，2006，22（3）：6－7．（in Chinese）

［3］常友渠，肖貴元，曾敏．貪心算法的探討與研究［J］．重慶電力高等專(zhuān)科學(xué)校學(xué)報(bào)，2008，13（3）：41－42，47．CHANG You－qu，XIAO Gui－yuan，ZENG Min．Exploration of greedy algorithm ［J］．Journal of Chongqing Electric Power College，2008，13（3）：41－42，47．（in Chinese）

［4］崔鵬，劉紅靜．測(cè)試集問(wèn)題的綜合覆蓋貪心算法的深入近似［J］．軟件學(xué)報(bào)，2006，17（7）：1494－1500．CUI Peng，LIU Hong－jing．Deep approximation of set cover greedy algorithm for test set［J］．Journal of Software，2006，17（7）：1494－1500．（in Chinese）