帶拒絕箱覆蓋問題的局內算法

摘 要:作為對裝箱覆蓋問題的推廣，提出帶拒絕的裝箱覆蓋問題#65377;設有許多等長的一維箱子，給定一個物品集，每個物品有兩個參數:長度和費用#65377;物品可以放入箱子也可被拒絕放入箱子，每個物品只準放入一只箱子中，每只箱子中的物品容量總和至少為箱子容量，一旦箱子中的物品長度達到要求則需啟用新箱#65377;如果物品被放入箱中，則產生費用#65377;該問題是一個新的組合優化問題，在內部互聯網信息管理等問題中有著廣泛的應用背景#65377;給出一個求解該問題的局內近似算法C-FF，分析其最壞情況漸近性能比為1/2，并給出了相應的實驗結果#65377;

關鍵詞:箱覆蓋問題;近似算法;最壞情況漸近性能比;因特網通信;信息管理

中圖分類號:TP393文獻標識碼:A

1 引 言

面對內外眾多客戶對Web服務信息的高頻率訪問要求，如何有效地對內部網(Intranet) 的分布式信息系統進行管理，以達到低費用#65380;高效率的目的，是非常重要的關鍵技術#65377;文獻[1]首先提出這類問題，進行了一定深度的研究#65377;文獻[2]對此問題進行了探討#65377;一個企業為了有效地降低通信費用，往往將被訪問頻繁的外部Internet信息塊下載至Intranet內部的網絡服務器上，使之成為內部信息塊#65377;但由于網絡服務器本身內存的限制及訪問該服務器上的信息的速度的要求，企業要有選擇地下載Internet外部信息塊#65377;企業要考慮的是如何使通信費用總和最小#65377;

本文將上述問題轉化成如下定義的優化問題:如何合理地將互聯網上的信息分布到所有Web服務器上，在至少達到各個服務器容量基本額度要求下，使這些信息因被訪問而產生的通信費用最小?因為可以對每個有用的信息塊定義兩個參數:信息塊容量，表示其內存大小;信息塊費用值，表示放在服務器上產生的費用值#65377;從而目標變為達到放在服務器上的信息塊費用值之和最少的服務器數最多#65377;該問題描述如下:

設有長為C的一維箱子，給定n個物品的序列Ln=<ɑ1，ɑ2，…，ɑn>，物品ɑi(1≤i≤n)的大小為ωi，費用值為pi(1≤i≤n)#65377;物品可以放入箱子也可被拒絕放入箱子#65377;每個物品只準放入一只箱子中，每只箱子中的物品容量總和至少超過箱子容量，如果某物品被放入箱中，則產生費用pi，怎樣安排物品使箱子中物品總費用之和最小同時容量達到要求的箱子數最多#65377;我們稱此問題為帶拒絕箱覆蓋問題#65377;

注意到如果令每個物品的費用都充分大，大于購買服務器的費用，在最優解中該物品一定不會拒絕#65377;帶拒絕箱覆蓋問題就變成箱覆蓋問題，它是強NP難的^[3]，因此帶拒絕箱覆蓋問題也是強NP難的#65377;

計算技術與自動化2007年6月第26卷第2期楊鼎強等:帶拒絕箱覆蓋問題的局內算法本文第2節給出相關知識;第3節提出一個求解帶拒絕箱覆蓋問題的局內近似算法C-FF算法，然后分析了該算法的性能;第4節給出了實驗結果#65377;

2 相關知識

箱覆蓋問題是:給定n個物品的序列Ln=<ɑ1，ɑ2，…，ɑn>，物品ɑi(1≤i≤n)的大小為ωi∈(0，1]，要求將這些物品裝入單位容量的箱子B1，B2，…，Bm中，使得每個箱子中的物品大小之和至少為1，并使所使用的箱子數目m最大#65377;

箱覆蓋問題是組合優化領域的基本問題，已有很多好的結果^[4-6]，而對帶拒絕裝箱覆蓋問題，尚未見文獻研究#65377;由于目前NP完全問題不存在有效時間內求得精確解的算法，因此設計和分析其近似算法是重要的研究內容#65377;設A為一近似算法，A(L)表示算法A對輸入物品序列L操作所使用的裝箱數，OPT(L)表示最優值#65377;算法A的最壞情況漸近性能比定義為R∞A=limn→∞infL{A(L)/OPT(L)|OPT(L)≥n}#65377;

根據對物品信息的依賴程度，近似算法分為局內(online)算法和局外(offline)算法#65377;如果在依序處理各輸入物品時，不知道任何后續物品信息，并立即給出當前物品的裝箱方案，則稱為局內算法;而首先得到所有物品信息之后，統一處理所有物品的裝箱方案，則稱為局外算法#65377;

最早研究此類帶拒絕的組合優化問題是可拒絕并行處理器調度問題，它與本文所討論的問題有一定聯系#65377;該問題可描述如下:設有m個同型并行處理器(identical multiprocessor)，n類不同尺寸的工件，其罰值也不同，并行處理器可選擇，也可拒絕，要求將最后一個工件的完工時間與被拒絕工件的總罰值之和最小#65377;這個問題最早由Bartal等人提出^[7]#65377;他們對局外和局內算法的研究都得到了很好的結果#65377;Alex和Richar^[8]將此問題推廣同型并行處理器(uniform multiprocessor)上的調度問題，對局外算法的設計進行了探討#65377;

3 C-FF算 法

帶拒絕箱覆蓋問題中，要求每個箱子中的物品費用總和最小，同時物品尺寸之和盡可能大，因此，可以考慮將達到要求的費用/尺寸比值的物品裝入箱子#65377;一種自然的策略是首先判斷物品是否滿足裝箱的條件，然后在滿足條件的物品使用經典裝箱算法#65377;基于此思想，我們提出C-FF(classified-first fit)算法#65377;

為方便計，將所有信息塊的費用除以購買新服務器的費用后作為新的費用#65377;

根據物品ɑi的費用密度Cpi/ωi，算法中的物品分成兩大類:

C-FF算法主要過程:

1)物品ɑ1到達，如果p1<1則拒絕，轉步驟2);否則轉步驟3)#65377;

2)物品ɑi到達，設已到達物品的總費用值為P，如果P+pi<1則拒絕ɑi，否則轉步驟3)#65377;

3)自當前物品ɑi開始，如果該物品屬于M1，則按FF算法將該物品裝入箱子中，當箱子中的物品大小至少為C時則關閉當前箱子;如果該物品屬于M2，則拒絕該物品#65377;

引理1^[2] 對任意帶拒絕裝箱問題實例I，L=∑i∈M1ωiC+P(M2)是其最優解值OPT(I)的下界，即有OPT(I)≥L;且成立L≥12(OPT(I)-1)#65377;這里P(M2)=∑i∈M2pi為M2中物品的總罰值#65377;

定理2 對于帶拒絕箱覆蓋問題的所有實例L，成立2C-FF(L)≥OPT(L)-1;C-FF算法的最壞情況漸近性能比RC-FF∞=1/2#65377;

證明 如果所有物品的總罰值小于1，則顯然算法C-FF得到問題最優解#65377;故以下假定所有物品的總罰值至少為1#65377;令L1為算法C-FF按步驟3安排的物品集組成的實例#65377;由于算法C-FF步驟1～步驟2中被拒絕物品的總罰值不超過1，且未將任何物品裝箱，所以C-FF(L\\L1)≤1#65377;下面就L1中物品總長度分兩種情況考慮:

(1) 如果L1中物品總長度小于C，按M2的定義知，L1中被拒絕物品的總罰值不超過它們的總長度除以C#65377;因此總罰值也不超過1，且未被拒絕的物品總長度仍小于C，所以C-FF(L1)=0，因此

C-FF(L)=C-FF(L1)+C-FF(L\\L1)≤C-FF(L1)+1=1#65377;

由于OPT(L)≥1，顯然成立C-FF(L)≤OPT(L)，2C-FF(L)≥OPT(L)-1#65377;

(2) 如果L1中物品總長度至少為C，因為C-FF算法中每個箱子的物品大小之和超過C但小于2C，我們有2C-FF(L1)+1≥OPT(L1)，因此有2C-FF(L)+1=2C-FF(L1)+2C-FF(L\\L1)+1≥2C-FF(L1)+2≥OPT(L1)+1又據引理1知OPT(L)≤OPT(L1)+1，因此有2C-FF(L)≥OPT(L)-1#65377;

令ε=12m，用(ɑ，c)表示大小為ɑ#65380;費用為c的物品，{ɑ1，ɑ2，…，ɑn}表示把物品序列{ɑ1，ɑ2，…，ɑn}重復k次所得的物品序列，考慮輸入物品序列:

L={(1-ε，1)，(1-ε2m，1)}2m

則所有物品均屬于M1#65377;使用算法時每兩個大小為1-ε的物品占用一個箱子，所以C-FF(L)=m;而若使用最佳策略，所有大小為(1-ε)/2m的物品恰好可以放入一個箱子中，每個大小為1-ε的物品也恰好占用一個箱子，故OPT(L)=2m+1，所以綜上所述，C-FF算法的最壞情況漸近性能比RC-FF∞=1/2#65377;

證畢#65377;

4 實驗結果

實驗中分別取物品個數n=20，30，50，100，箱子長度C=100#65377;物品長度為區間[1，C]中隨機產生的整數，費用為區間[0，2]中隨機產生的實數#65377;對每一種組合，隨機產生50個實例，對50個的性能比取平均值#65377;實驗環境是CPU1.6G，512M內存#65377;

求C-FF算法的平均性能比時，我們用第2節給出的最優解定界，采用分枝定界法(深探法)求出最優解#65377;實驗結果如圖1所示#65377;

從實驗結果可以看出，隨著問題規模的擴大，近似算法C-FF平均性能比逐步下降#65377;

5 結 論

本文從互聯網的信息管理問題中提出了一個新的組合優化問題——極小化箱子中物品費用的帶拒絕箱覆蓋問題#65377;本文進一步給出了求解帶拒絕裝箱覆蓋問題的局內近似算法C-FF，證明了該算法最壞情況漸近性能比R∞C-FF為1/2，實驗顯示在平均意義下C-FF的效果相當好#65377;設計出帶拒絕箱覆蓋問題最壞情況漸近性能比更好的局內算法，是我們進一步研究的課題#65377;

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。