閉區間有限覆蓋的算法

江世宏

（武漢工程大學理學院，湖北 武漢 430205）

0 引 言

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

本文根據貪心法［3－4］，討論了兩種求閉區間有限覆蓋的算法，并用計算機對所提出的算法進行了摸擬測試．

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．1 Method 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＜m，做以下操作

（1）用從p（1）到p（m）＋1的線段覆蓋區間，置總長length＝p（m）－p（1）＋1，線段數num＝1；

（2）當num＜n時，反復做以下操作

①從覆蓋線段中，挖去gap（2，num）至gap（3，num）這一段；

②更新線段總長length＝length－gap（1，num）；

③更新線段數num＝num＋1．

（3）輸出總長length和線段數num；

在MATLAB下，編寫該算法的摸擬檢測程序，其程序運行結果如圖2所示．

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

2 閉區間的有限覆蓋問題

2．1 問題的提出

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

2．2 求解分析

用二維數組I存放開區間集（不妨認為已對I中的第一列作了升序排序），即

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

具體的挑選過程為：在開區間Ii＝（ai，bi）（i＝1，2，…，n）中，做第一輪挑選．對所有的ai＜a，計算di＝bi－a，存在著dr＝max｛di｝，選出開區間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 首選開區間的3種可能情況Fig．3 Three cases of first opened interval

對于情況1，可以斷言，在開區間集I中，無法挑選出有限個開區間，實現對［a，b］的覆蓋；對于情況2，可以斷言，開區間Ir＝（ar，br）已實現對［a，b］的覆蓋；對于情況3，取a＝br，縮小［a，b］，再從開區間Ii＝（ai，bi）（i＝r＋1，r＋2，…，n）中，做新一輪的挑選．

2．3 算法

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

步驟二：獲取I中開區間個數n，對I中第1列作升序排序．

步驟三：置所選開區間個數m＝0，取j＝1（即從I中第j＝1個開區間開始進行挑選）．

步驟四：當j≤n時，反復做以下操作：

（1）d＝0（所選開區間對a的覆蓋距離賦初值），r＝0（所選開區間序號賦初值）．

（2）對于i＝j，j＋1，…，n，反復做以下操作

如果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，則標識變量flag＝0，退出挑選操作．

（5）如果d＞b－a，則標識變量flag＝1，退出挑選操作．

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

步驟五：如果flag＝0，輸出“不能覆蓋”信息；否則，輸出“可以覆蓋”信息，并輸出S中所存儲的m個開區間．

在MATLAB下，編寫該算法的模擬檢測程序，其程序運行結果如圖4所示．

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

3 結 語

閉區間有限覆蓋問題，在經濟、管理、軍事、計算機和數學領域里，具有十分廣泛的應用，對該問題的研究，有待進一步深化．例如，還可以討論，在要求所有覆蓋閉區間的開區間總長最小的條件下，算法的設計問題．

致謝

感謝國家科技部和武漢工程大學對本項目的資助！

［1］郭改慧，李兵方．有限覆蓋定理的應用［J］．牡丹江大學學報，2013，22（10）：103－104．

［2］關金玉，徐永春，祁建芳．用完全覆蓋證明實數系中若干定理［J］．河北北方學院學報：自然科學版，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］．重慶電力高等專科學校學報，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］崔鵬，劉紅靜．測試集問題的綜合覆蓋貪心算法的深入近似［J］．軟件學報，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）