求解0-1背包問題的融合貪心策略的回溯算法

j

j

j

j

i

n

i

x

i

C

C

i

14.else

15.break;

i

n

x

i

v

i

i

x

i

19.return maxvalue

O

n

O

n

O

n

n

O

n

n

1.3 0-1背包問題的經(jīng)典回溯算法

與貪心算法相比，經(jīng)典回溯算法更看重問題的整體性分析。經(jīng)典回溯算法是使用深度優(yōu)先遍歷求解0-1背包問題的經(jīng)典算法。在問題求解的過程中，回溯算法將物品的選擇狀態(tài)構(gòu)造成一個解空間樹，通過遍歷解空間樹中的每個節(jié)點來尋找問題的可行解和最優(yōu)解。具體地說，經(jīng)典的回溯算法從解空間樹的根節(jié)點出發(fā)，依次判斷解空間樹的每一個節(jié)點，并選擇當(dāng)前狀態(tài)下滿足問題約束條件的節(jié)點，當(dāng)遍歷到葉子節(jié)點時，算法對當(dāng)前各個節(jié)點的選擇狀態(tài)進(jìn)行記錄和判斷，當(dāng)約束條件不滿足時，回退一步至上一狀態(tài)或回退多步，直至遍歷過解空間樹的每一個節(jié)點并回溯到根。在搜索的過程中，回溯算法會不斷判斷是否存在更優(yōu)的解，并記錄和更新目前已找到的最優(yōu)解。

經(jīng)典回溯算法解決0-1背包問題的主要步驟如下：

(1)構(gòu)造問題的解空間樹；

(2)確定問題的約束條件。一個是放入背包的物品總重量不超過背包的容量，另一個是放入背包的物品是否構(gòu)成問題的最優(yōu)解；

(3)從根節(jié)點開始，深度優(yōu)先遍歷解空間樹，在遍歷的過程中根據(jù)問題的約束條件選擇性地進(jìn)行回溯和繼續(xù)遍歷。

O

1.3.1 遞歸回溯算法

存在兩種實現(xiàn)經(jīng)典回溯的算法，一個是遞歸算法，一個是非遞歸算法。遞歸回溯算法，是指把一個大型的復(fù)雜問題分解為一個與原問題相似的、規(guī)模較小的問題，通過遞歸求解小問題并將子問題的解合并，從而得到原問題的解。

算法2給出了遞歸回溯算法(knap1)的偽代碼描述，該算法從位于解空間樹根節(jié)點的第1個物品開始遍歷，依次考慮當(dāng)前選中物品不放入背包和放入背包時，所有物品的選擇狀態(tài)。當(dāng)遍歷到葉子節(jié)點時，進(jìn)行最優(yōu)解的約束條件檢驗并判斷是否進(jìn)行回溯，算法的主要步驟如下：

(1)引入cw和cv分別表示當(dāng)前狀態(tài)下背包內(nèi)物品的總重量和總價值；

(2)對于每一個物品，首先選擇“不裝入背包”并進(jìn)行遞歸，而在進(jìn)行“裝入背包”的選擇前，則需要判斷所有選中物品的總重量是否滿足背包的容量；

(3)當(dāng)遍歷到最后一個物品時，計算此時背包內(nèi)物品的總價值，判斷是否為問題的最優(yōu)解。

算法2：遞歸回溯算法knap1。

Initialize maxvalue, cw, cv as 0

knap1(1)

output maxvalue

intknap1(int i)

if i=n+1 then

if cv>maxvalue then

maxvalue←cv;

result←x;

else

x[i]←0;

knap1(i+1);

if cw+w[i]≤C then

x[i]←1;

cv←cv+v[i], cw←cw+w[i];

knap1(i+1);

x[i]←0;

cv←cv-v[i], cw←cw-w[i];

returnmaxvalue

1.3.2 非遞歸回溯算法

與遞歸回溯算法不同，非遞歸回溯算法利用物品的狀態(tài)值判斷是否需要回溯，而不需要借助操作系統(tǒng)提供的遞歸機制，因而一般具有較高的時空效率。

算法3給出了非遞歸回溯算法(knap2)的偽代碼描述，在該算法中，選中物品在進(jìn)行“裝入”或“不裝入”背包的選擇前，其狀態(tài)值首先會被賦值為-1(代碼第2行)；當(dāng)物品的選擇狀態(tài)確定后，其狀態(tài)值則為0或1(代碼第4、15行)；一旦該物品的狀態(tài)值增加至2時，則需要進(jìn)行回溯(代碼第17、18行)。

算法3：非遞歸回溯算法knap2。

i

x

i

i

x

i

x

i

i

n

j

n

x

j

w

j

x

j

v

j

10.if cw≤C and cv>maxvalue then

11.maxvalue←cv;

12.result←x;

13.cw←0, cv←0;

14.else

i

x

i

17.else

i

19.end

20.return maxvalue

2 融合貪心策略和剪枝策略的回溯算法

2.1 問題分析

使用貪心算法求解0-1背包問題時，算法從問題的某一初始解出發(fā)，選擇當(dāng)前條件下的最優(yōu)解，并試圖構(gòu)造或逼近問題的整體最優(yōu)解。貪心算法每一步的決策僅考慮當(dāng)前的局部信息，其解空間不可回溯再現(xiàn)，具有較強的隨機性和不可預(yù)知性。這種基于經(jīng)驗或直覺的判斷，并不一定能夠保證找到問題真正的最優(yōu)解，在絕大多數(shù)情況下，貪心算法得到的解只是問題的近似最優(yōu)解。但是，由于貪心算法采用局部最優(yōu)決策，因而往往具有較高的效率。

回溯算法的思想和枚舉法類似，即通過嘗試問題所有可能的解來尋找問題的最優(yōu)解，這種算法雖然確保了解的正確性，但是以犧牲算法運行時間為代價。當(dāng)問題規(guī)模較大時，回溯算法的運行時間呈指數(shù)式增長，在短時間內(nèi)可能無法得到問題的最優(yōu)解。

針對上述特征，該文將貪心算法的高效性和回溯算法的最優(yōu)性相結(jié)合，提出了一種融合貪心策略和剪枝策略的新型回溯算法，簡稱新型算法?？紤]到貪心算法得到的解雖然可能不是問題的最優(yōu)解，但至少一定是問題的近似解，故將其作為初始解應(yīng)用于回溯算法，從而可以盡快實現(xiàn)剪枝操作，進(jìn)而提高回溯算法效率。

因此，新型算法將貪心算法的解作為回溯算法中剪枝策略的判斷條件，同時優(yōu)化了遍歷過程中的約束條件，從而在確保得到問題最優(yōu)解的同時，可以進(jìn)一步提高算法效率。

2.2 新型算法

算法4給出了所提出的新型算法的偽代碼描述。該算法使用遞歸方法求解0-1背包問題，與經(jīng)典的回溯算法不同，首先，算法4增加了基于價值的剪枝策略，若背包內(nèi)物品的總價值與未遍歷到的物品的總價值之和小于算法1得到的解，則進(jìn)行剪枝并回溯。其次，在遍歷的過程中，算法4優(yōu)化了物品選擇的約束條件，將經(jīng)典回溯算法的約束條件“放入背包的物品總重量不超過背包的容量”修改為“當(dāng)前選中的物品重量滿足背包的剩余容量”。

所提出新型算法的主要步驟如下：

i

(2)算法1得到的解存儲到maxvalue_greedy中；

i

C

(4)首先判斷選中物品“不裝入背包”時是否需要剪枝；

(5)若選中物品“裝入背包”，首先判斷物品重量是否滿足背包的剩余容量，若“能裝入”，則繼續(xù)進(jìn)行步驟4的剪枝判斷，最終確定物品的選擇狀態(tài)。

算法4：新型算法。

C

i

2.maxvalue_greedy←greedy()

C

4.output maxvalue

i

i

n

i

n

v

i

x

i

4.if value>maxvalue then

5.maxvalue←value;

6.result←x;

7.else

v

i

i

v

i

w

i

11.if pv+rv>maxvalue_greedy then

x

i

i

i

w

i

v

i

v

i

x

i

15.return maxvalue

在新型算法中，遞歸函數(shù)GB(第3行)的含義是：若當(dāng)前考慮的物品“不裝入背包”，計算此時背包內(nèi)物品的總價值與未遍歷到的物品的總價值之和，若大于maxvalue_greedy，則表明，在當(dāng)前物品的選擇狀態(tài)下，存在將某些物品裝入背包后使得總價值提高的可能，因此進(jìn)行遞歸；否則，表明在當(dāng)前物品的選擇狀態(tài)下，任何后續(xù)的裝入選擇都將不可能超過現(xiàn)在背包內(nèi)物品的總價值，此時則進(jìn)行剪枝并回溯。若當(dāng)前選中物品想要“裝入背包”，首先判斷該物品的重量是否滿足背包的剩余容量，然后繼續(xù)判斷是否“有必要裝入”。當(dāng)遍歷到最后一個物品時，計算此時背包內(nèi)物品的總價值并判斷是否為問題的最優(yōu)解。

新型算法的核心思想是：對于每一個物品，只有該物品“能裝入背包”且“有必要裝入”，才會將其放入背包中。

3 仿真實驗與分析

3.1 實驗環(huán)境

該文進(jìn)行了大量的仿真實驗，具體實驗環(huán)境為：CPU：i7-8550U，內(nèi)存：DDR2 16 GB；硬盤：1 TB；緩存，8 MB；PF使用率：36%～45%；編程語言：Java，軟件開發(fā)工具：Eclipse。分別實現(xiàn)了遞歸回溯算法(算法2)、非遞歸回溯算法(算法3)和新型算法(算法4)，并在不同問題規(guī)模下進(jìn)行仿真實驗與分析。

n

f

f

f

3.2 實驗結(jié)果分析

f

n

表1 三種算法在實驗系數(shù)f=0.3的時間耗費

表2 三種算法在實驗系數(shù)f=0.6的時間耗費

表3 三種算法在實驗系數(shù)f=0.8的時間耗費

通過上述比較，可以得出以下結(jié)論：

(1)在不同實驗系數(shù)下，隨著問題規(guī)模的增加，所有算法的時間耗費都呈現(xiàn)上升趨勢，其中經(jīng)典的遞歸回溯算法和非遞歸回溯算法的上升趨勢更為顯著。結(jié)合算法的時間復(fù)雜度可知，經(jīng)典回溯算法的時間耗費隨著問題規(guī)模的增加呈指數(shù)級增長。此外發(fā)現(xiàn)，非遞歸回溯算法較遞歸回溯算法具有較高的運行時間。

(2)在同一實驗系數(shù)、同一問題規(guī)模下，與經(jīng)典回溯算法相比，該文所提出的新型算法在保證得到問題的最優(yōu)解的同時，具有較小的時間耗費，特別是在問題規(guī)模較大時，效果更為明顯。

在不同實驗系數(shù)下，對遞歸回溯算法(算法2)和非遞歸回溯算法(算法3)的時間耗費進(jìn)行了對比，從而驗證實驗系數(shù)是否對經(jīng)典回溯算法的執(zhí)行時間產(chǎn)生影響。實驗結(jié)果見表4。

表4 經(jīng)典回溯算法在問題規(guī)模n=20時的時間耗費

根據(jù)表4可知，當(dāng)實驗系數(shù)從0.3逐漸增加至0.9時，遞歸回溯算法的時間耗費線性增長至某一數(shù)值后，在該數(shù)值處呈現(xiàn)小幅度波動；非遞歸回溯算法的時間耗費則始終在某數(shù)值處小幅度波動。

f

圖1 新型算法的時間耗費(f=0.8)

從圖1可以看出，在實驗系數(shù)為0.8時，只有當(dāng)問題規(guī)模近似增加至70時，新型算法的時間耗費才會有較為明顯的遞增，效率遠(yuǎn)遠(yuǎn)高于經(jīng)典回溯算法。

表5列出了在不同的實驗系數(shù)和不同的問題規(guī)模下，新型算法得到問題最優(yōu)解的時間耗費情況。從表5中可知，新型算法普遍隨實驗系數(shù)的增加而減少，其原因在于，隨著實驗系數(shù)的增加，背包的容量不斷增大，背包可以容納的物品數(shù)量相應(yīng)增加，從而減少了回溯的概率，進(jìn)而提高了算法效率。

表5 新型算法在不同實驗系數(shù)、不同問題規(guī)模下的時間耗費

4 結(jié)束語

0-1背包問題是經(jīng)典的NP完全問題，而經(jīng)典的回溯算法采用枚舉的思想，通過深度優(yōu)先搜索解空間樹尋找問題的最優(yōu)解。在問題規(guī)模較小時，回溯算法同其他求解0-1背包問題的經(jīng)典算法相比，具有更小的時間耗費和空間耗費。但隨著問題規(guī)模的增加，回溯算法在時間和空間上都有極為明顯的增加，這種增加導(dǎo)致算法在較短時間內(nèi)無法得到問題的最優(yōu)解。

該文將貪心算法的高效性和經(jīng)典回溯算法的最優(yōu)性相結(jié)合，提出的融合貪心策略與剪枝策略的新型算法，將經(jīng)典貪心算法得到的問題近似解用于剪枝策略的判斷條件中，減少了經(jīng)典回溯算法遍歷過程中的無效搜索；同時，在進(jìn)行物品選擇的判斷時，使用背包剩余容量作為約束條件，大大提高了算法的求解效率。大量仿真實驗結(jié)果表明，該新型算法在保證得到問題最優(yōu)解的同時，有效提高了算法的運行效率。