獎勵-收集頂點(diǎn)覆蓋問題的精確算法
2023-05-14 18:45:13曾賓寧愛兵付振星徐江盼張惠珍
計算機(jī)時代 2023年5期
曾賓 寧愛兵 付振星 徐江盼 張惠珍
摘? 要： 獎勵-收集頂點(diǎn)覆蓋問題是頂點(diǎn)覆蓋問題的衍生問題，同時也是組合優(yōu)化NP-hard問題。本文提出該問題的數(shù)學(xué)性質(zhì)并給出證明，利用數(shù)學(xué)性質(zhì)能夠確定某些頂點(diǎn)一定在或一定不在最優(yōu)獎勵-收集頂點(diǎn)覆蓋集中，從而降低該問題的規(guī)模；基于該問題的數(shù)學(xué)性質(zhì)設(shè)計出上下界子算法、降階子算法、回溯子算法，通過降階子算法可以降低該問題的規(guī)模，從而縮短回溯子算法的搜索時間，進(jìn)而降低求解該問題最優(yōu)解的時間。通過應(yīng)用和算法對比表明，所設(shè)計的算法比沒有考慮該問題數(shù)學(xué)性質(zhì)的一般精確算法的時間復(fù)雜度更低。
關(guān)鍵詞： 獎勵-收集頂點(diǎn)覆蓋； 上下界子算法； 降階子算法； 回溯子算法
中圖分類號：O223? ? ? ? ? 文獻(xiàn)標(biāo)識碼：A? ? ?文章編號：1006-8228（2023）05-51-06
Exact algorithm for the prize-collecting vertex covering problem
Zeng Bin， Ning Aibing， Fu Zhenxing， Xu Jiangpan， Zhang Huizhen
（Business School， University of Shanghai for Science and Technology， Shanghai 200093， China）
Abstract： The prize-collecting vertex covering problem is not only a derivative of the vertex covering problem， but also a problem for NP-hard combinatorial optimization. In this paper， we firstly propose the mathematical properties of the problem and give the proof， which can determine that some vertices must or must not be in the optimal prize collection vertex covering set， so as to reduce the scale of the problem. Secondly， based on the mathematical properties of the problem， we design the upper and lower bound sub-algorithm， reduced-order sub-algorithm and backtracking sub-algorithm. Through the reduced-order sub-algorithm， the scale of the problem can be reduced， so as to shorten the search time of the backtracking sub-algorithm， and then reduce the time to solve the optimal solution of the problem. A comparison of applications and algorithms shows that the designed algorithm has lower time complexity than the general accurate algorithms without considering the mathematical properties of the problem.
Key words： prize-collecting vertex cover; upper and lower bound sub-algorithm; reduced-order sub-algorithm; backtracking sub-algorithm
0 引言
獎勵-收集，是Balas[1]在研究旅行商問題時首次提出，尋找低成本、低懲罰的服務(wù)方式就是獎勵-收集所關(guān)注的問題。獎勵-收集頂點(diǎn)覆蓋問題（thePrize-Collecting Vertex Cover Problem， PCVC）是頂點(diǎn)覆蓋問題（the Vertex Cover Problem， VC）的衍生問題。在實(shí)際商業(yè)活動中，為了避免超出預(yù)算必須追求成本費(fèi)用與懲罰費(fèi)用之和最小化。因此，PCVC問題相比于其他頂點(diǎn)覆蓋問題更加切合實(shí)際的應(yīng)用。
目前，求解PCVC問題的算法主要有三類。第一類是使用分支限界的傳統(tǒng)精確算法求解PCVC問題，此類方法類似于求解VC問題[3]。此類算法可求得該問題的最優(yōu)解，但求解速度緩慢。第二類主要是近似算法，如林俊峰[4]等將PCVC問題轉(zhuǎn)化為對偶問題，利用迭代松弛方法設(shè)計出該問題的一個2-近似算法；郭金雙[5]受Konemann[6]等人求解獎勵-收集頂點(diǎn)集合覆蓋問題的f-LMP算法的啟發(fā)設(shè)計出2-LMP算法來求解該問題；Levn[7]等給出求解這類部分頂點(diǎn)覆蓋問題的貪心算法。此類算法雖然在求解速度快于傳統(tǒng)精確算法，但無法求到該問題的最優(yōu)解。第三類是啟發(fā)式算法，采用啟發(fā)式算法來求解PCVC的文獻(xiàn)極少，用啟發(fā)式算法來求解最小權(quán)頂點(diǎn)覆蓋問題文獻(xiàn)較多，如王辰尹[8]利用遺傳算法求解模糊環(huán)境下的最小權(quán)頂點(diǎn)覆蓋問題。從理論上來看，啟發(fā)式算法同樣可以用來求解PCVC問題。
1 獎勵收集頂點(diǎn)覆蓋問題的數(shù)學(xué)定義與性質(zhì)
1.1 獎勵-收集頂點(diǎn)覆蓋問題定義
獎勵收集頂點(diǎn)覆蓋問題是指在給定簡單無向賦權(quán)圖G=（V，E），其中V為頂點(diǎn)集合，E為邊集合，頂點(diǎn)vi的非負(fù)權(quán)值為c（vi），即頂點(diǎn)成本費(fèi)用，邊eij的非負(fù)權(quán)值為p（vi，vj）其中vi≠vj，即邊懲罰費(fèi)用，要求頂點(diǎn)子集S*[?]V，使得S*中所有頂點(diǎn)的成本費(fèi)用之和加上未被S*中頂點(diǎn)覆蓋的所有邊上的懲罰費(fèi)用之和最小。
1.2 數(shù)學(xué)符號
G：G=（V，E）為簡單無向賦權(quán)圖，V為頂點(diǎn)集，vi為V中的某頂點(diǎn)，vi∈V，E為邊集，eij為E中的某邊，eij∈E，c（vi）為頂點(diǎn)vi∈V的非負(fù)成本費(fèi)用，p（vi，vj）為邊eij=（vi，vj）∈E的非負(fù)懲罰費(fèi)用；
n、m：圖G的頂點(diǎn)數(shù)量；圖G的邊數(shù)量；
eij、c（vi）：頂點(diǎn)vi，vj的之間的邊，eij=（vi，vj）∈E且vi≠vj；頂點(diǎn)vi成本費(fèi)用，vi∈V；
p（vi，vj）：頂點(diǎn)vi，vj之間邊eij的懲罰費(fèi)用，eij =（vi，vj）∈E且vi≠vj；
G[F]：G=（VF，EF）由頂點(diǎn)子集F的導(dǎo)出子圖G[F]，其中VF[?]V，EF[?]E；
N（G，vi）、N（G[F]，vi）：vi在圖G、G[F]中的鄰接頂點(diǎn)集，N（G，vi）={vi|（vi，vj）∈E}，N（G[F]，vi） ={vi|（vi，vj）∈EF}；
N[G，vi]、N[G[F]，vi]：N[G，vi]=N（G，vi）∪vi，N[G[F]，vi]=N（G[F]，vi）∪vi；
N（G，Vi）、N（G[F]，Vi）：頂點(diǎn)集Vi在圖G、G[F]中的鄰接頂點(diǎn)集的合集；
E（G，vi）、E（G[F]，vi）：vi在圖G、G[F]中的鄰邊集，E（G，vi）={（vi，vj）|（vi，vj）∈E}、E（G[F]，vi）={（vi，vj）|（vi，vj）∈EF}；
P（G，vi）、P（G[F]，vi）：邊集合在E（G，vi）、E（G[F]，vi）中所有邊懲罰費(fèi)用之和；
C（N（G，vi））、C（N（G[F]，vi））：頂點(diǎn)vi的在圖G、G[F]中的所有鄰接頂點(diǎn)的成本費(fèi)用之和；
P0（Vj，vi）：vi的鄰接邊集中未被集合Vj中的頂點(diǎn)所覆蓋的邊懲罰費(fèi)用之和；
E（G，Vi）、E（G[F]，Vi）：頂點(diǎn)集Vi在圖G、G[F]中鄰邊集的合集；
d（G，vi）、d（G[F]，vi）：vi在圖G、G[F]中度，即與vi鄰接邊的數(shù)量，d（G，vi）=|N（G，vi）|、d（G[F]，vi）=N（G[F]，vi）；
u、b：該問題的上界值，全局變量；子算法中的下界值，局部變量；
S、S*：當(dāng)前最優(yōu)獎勵收集頂點(diǎn)覆蓋集合，S[?]V；最優(yōu)獎勵收集頂點(diǎn)覆蓋集合，即最優(yōu)解，S*[?]V；
z：當(dāng)前狀態(tài)下的目標(biāo)函數(shù)值，S中的頂點(diǎn)成本費(fèi)用與未被S所覆蓋邊的懲罰費(fèi)用之和；
z*：最優(yōu)目標(biāo)函數(shù)值，S*中的頂點(diǎn)成本費(fèi)用與未被S*所覆蓋邊的懲罰費(fèi)用之和；
V0，V1，V5;E0，E1，E5：分別為圖G中通過數(shù)學(xué)性質(zhì)判定一定不在、一定在、不確定是否在S*中的頂點(diǎn)集合，V5=V＼V1＼V0始終成立，初始化V0={}，V1={}，都為全局變量；分別為圖G中通過數(shù)學(xué)性質(zhì)判定一定被、一定不被、不確定是否被S*中的頂點(diǎn)所覆蓋的邊集合，都為全局變量；
VV0，VV1，VV5;EVV0， EVV1，EVV5：分別為G在執(zhí)行子算法時假設(shè)不在、假設(shè)在、不確定是否在S*中的頂點(diǎn)集合，分別初始化為VV0={}，VV1={}，VV5=V＼V1＼V0＼VV1＼VV0始終成立，都為局部變量；分別為G在執(zhí)行子算法時假設(shè)不被、假設(shè)被、不確定是否被S*中的頂點(diǎn)所覆蓋的邊集合，都為局部變量。
對某頂點(diǎn)vi而言：
⑴ 若通過數(shù)學(xué)性質(zhì)判斷得出vi∈V1，則更新V1=V1∪{vi}，V5=V5＼{vi}，此時E（G，vi）中所有的邊都被覆蓋，即E（G，vi）中所有的邊都不被懲罰；
⑵ 若假設(shè)vi∈VV1，則更新VV1=VV1∪{vi}，VV5=VV5＼{vi}；
⑶ 若通過數(shù)學(xué)性質(zhì)判斷得出vi∈V0，則更新V0=V0∪{vi}，V5=V5＼{vi}；
⑷ 若假設(shè)vi∈VV0，則更新VV0=VV0∪{vi}，VV5=VV5＼{vi}。
1.3 數(shù)學(xué)性質(zhì)及證明
性質(zhì)1 對于d（G[VV5]，vi）=0的vi，分兩種情況，情況⑴：VV1=VV0=?，此時若c（vi）>0，則vi∈V0；此時若c（vi）=0，則vi在V0或V1中都是最優(yōu)解，本文都將其放在V0中；情況⑵：VV1、VV0不全為?，此時若c（vi）>0，則vi∈VV0；此時若c（vi）=0，則vi在VV0或VV1中都是最優(yōu)解，本文都將其放在VV0中。
證明 情況⑴，當(dāng)c（vi）>0時，vi在V0中會降低目標(biāo)函數(shù)值，又因?yàn)閂V1=VV0=?，則vi只能在V0中；當(dāng)c（vi）=0時，無論vi在V0還是V1中，都不會影響目標(biāo)函數(shù)值，又因?yàn)閂V1=?和VV0=?，則此時vi∈V0中或vi∈V1中；情況⑵，同理可證。
性質(zhì)2 對于d（G[VV5]，vi）=1的vi，其鄰接頂點(diǎn)為vj，分兩種情況，情況⑴：VV1=VV0=?，此時若c（vi）>0且vj∈V1，則vi∈V0；此時若c（vi）=0且vj∈V1，則vi在V0或V1中都是最優(yōu)解，本文算法都將其放在V0中；情況⑵：VV1、VV0不全為?，此時若c（vi）>0且vj∈V1，則vi∈VV0；此時若c（vi）=0且vj∈V1，則vi在VV0或VV1中都是最優(yōu)解，本文算法都將其放在VV0中。
證明 情況⑴，當(dāng)c（vi）>0且vj∈V1時，vi在V0中會降低目標(biāo)函數(shù)值，又因?yàn)閂V1=VV0=?，則此時vi只能在V0中；當(dāng)c（vi）=0且vj∈V1時，vi在V0或V1中都不會影響目標(biāo)函數(shù)值，又因?yàn)閂V1=VV0=?，則vi只能在V0中或V1中；情況⑵，同理可證。
性質(zhì)3 對于d（G[VV5]，vi）=1的vi，其鄰接頂點(diǎn)為vj，分兩種情況，情況⑴：VV1=VV0=?，此時若p（vi，vj）
證明 情況⑴，當(dāng)p（vi，vj）
性質(zhì)4 對于d（G[VV5]，vi）=2的vi，其鄰接頂點(diǎn)為vk、vj，分兩種情況，情況⑴：VV1=VV0=?，此時若c（vk）+c（vj） 證明 替代法證明，若vi在V1中，那么此時用vk或vj在V1中而vi在V0中，目標(biāo)函數(shù)會更小，又因?yàn)閂V1=VV0=?，則vj只能在V1中；那么當(dāng)VV1、VV0不全為?時，則vj只能在VV1中。 性質(zhì)5 對于圖G[VV5]中的懲罰費(fèi)用為+∞的eij，分兩種情況，情況⑴：VV1=VV0=?，此時若vj∈V0且c（vi）≠+∞，則vi∈V1；情況⑵：VV1、VV0不全為?，此時若vj∈V0且c（vi）≠+∞，則vi∈VV1。 證明 因?yàn)閑ij的懲罰費(fèi)用為+∞，則eij必須要覆蓋，又因?yàn)閂V1=VV0=?，則vi只能在V1中；那么當(dāng)VV1、VV0不全為?時，則vj只能在VV1中。 性質(zhì)6 在VV5中存在vi，設(shè)其鄰接頂點(diǎn)集為N（G[VV5]，vi），分兩種情況，情況⑴：VV1=VV0=?，若C（N（G[VV5]，vi）） 證明 此時vi在V0中可以降低頂點(diǎn)的成本費(fèi)用，從而使得目標(biāo)函數(shù)值降低，又因?yàn)閂V1=VV0=?，則vi只能在V0中；那么當(dāng)VV1、VV0不全為?時，則vi只能在VV0中。 性質(zhì)7 當(dāng)vi滿足P（G[VV5]，vi） 證明 當(dāng)P（G[VV5]，vi） 性質(zhì)8 對于d（G[VV5]，vi）=2的vi，設(shè)與其相連的vj，vk之間沒有邊，分兩種情況，情況⑴：VV1=VV0=?，若c（vi） 證明 此時vi在V0中降低了頂點(diǎn)成本費(fèi)用，從而使得目標(biāo)函數(shù)值降低，又因?yàn)閂V1=VV0=?，則vi只能在V0中；那么當(dāng)VV1、VV0不全為?時，則vj只能在VV0中。 性質(zhì)9 對于d（G[VV5]，vi）=2的vi，設(shè)與vi相連的頂點(diǎn)vj，vk之間有邊ejk=（vj，vk），分兩種情況，情況⑴：VV1=VV0=?，此時若p（vi，vj）+p（vi，vk）>c（vj）+c（vk）且c（vj）+c（vk） 證明 此時vi在V0中降低了頂點(diǎn)成本費(fèi)用，從而使得目標(biāo)函數(shù)值降低，又因?yàn)閂V1=VV0=?，則vi只能在V0中；那么當(dāng)VV1、VV0不全為?時，則vj只能在VV0中。 性質(zhì)10 若圖G中所有vi滿足c（vi）>P（G，vi），則該問題可在多項(xiàng)式時間內(nèi)求解。 證明 此時最優(yōu)獎勵收集頂點(diǎn)集為空集，目標(biāo)函數(shù)值為圖中所有邊懲罰費(fèi)用之和。 性質(zhì)11 若圖G中所有eij滿足p（vi，vj）>min{c（vi），c（vj）}，則該問題為最小權(quán)頂點(diǎn)覆蓋問題。 證明 此時圖中任意一邊不覆蓋所要花費(fèi)的懲罰費(fèi)用都比覆蓋它所要花費(fèi)的成本費(fèi)用高，則圖中所有邊都要用頂點(diǎn)覆蓋，又要追求成本費(fèi)用最小，此時即為最小權(quán)頂點(diǎn)覆蓋問題。 性質(zhì)12 假設(shè)vi不在最優(yōu)集合S*中時，若在這種情況下的下界大于上界，此時若|VV0|=|VV1|=0，則vi一定在最優(yōu)集合S*中，vi此時也一定在V1中，此時若|VV0|≠0或|VV1|≠0，則vi一定在VV1中。 證明 假設(shè)vi不在S*中，此時下界大于上界且集合VV0與VV1為空，表明若頂點(diǎn)vi不在S*中是不可能求得最優(yōu)解，則vi只能在S*中，自然也就在V1中；假設(shè)vi不在S*中，此時下界大于上界且集合VV0與VV1不為空，表明此時若vi不在VV1中是不可能求得比當(dāng)前狀態(tài)下更好的解，又因?yàn)関i是假設(shè)不在S*中，則vi只能在VV1中。 性質(zhì)13 假設(shè)vi在最優(yōu)集合S*中時，若在這種情況下的下界大于上界，此時若|VV0|=|VV1|=0，則vi一定不在最優(yōu)集合S*中，vi此時也一定在V0中，此時若|VV0|≠0或|VV1|≠0，則vi一定在VV0中。 證明 證明同理性質(zhì)12的證明，不再贅述。 2 算法設(shè)計與案例分析 2.1上界子算法 結(jié)合上文的數(shù)學(xué)性質(zhì)設(shè)計一個上界子算法來尋找該問題的上界。設(shè)上界子算法所求出的頂點(diǎn)集合為Su，其所有頂點(diǎn)成本費(fèi)用為Cu，即Cu=[vi∈sucvi]，設(shè)未被頂點(diǎn)集合Su中頂點(diǎn)所覆蓋的邊集合為Eu，其所有邊懲罰費(fèi)用為Pu，即Pu=[（vi， vj）∈Eup（vi，vj）]，則上界為u=Cu+Pu，上界子算法的具體步驟描述如下： Step 1 初始化集合Su={}，Eu={}，u=0； Step 2 依據(jù)上文的數(shù)學(xué)性質(zhì)將一定在、不在S*中的頂點(diǎn)分別添加到V1、V0，執(zhí)行Su=Su∪V1； Step 3 將V5中每個頂點(diǎn)vi的鄰接邊中未被集合V1∪Su中頂點(diǎn)所覆蓋的邊的懲罰費(fèi)用之和減去頂點(diǎn)vi的成本費(fèi)用c（vi）的值計算出來，并設(shè)該值為αi，即αi=P0（V1∪Su， vi）-c（vi）； Step 4 將V5＼Su中αi值大于0所對應(yīng)的頂點(diǎn)vi添加到集合Su，再重新計算集合N（G，vi）＼（V1∪Su）中各頂點(diǎn)對應(yīng)的αi值，直到集合V5＼Su為空集或集合V5＼Su中頂點(diǎn)vi 的最大αi值小于等于0為止，跳到Step 5； Step 5 將未被集合V1∪Su中的頂點(diǎn)所覆蓋的邊都添加到Eu，并計算Eu所有邊的懲罰費(fèi)用之和Pu； Step 6 計算上界u=Cu+Pu，輸出集合Su與上界u，退出該子算法。 2.2 下界子算法 結(jié)合上文的數(shù)學(xué)性質(zhì)設(shè)計一個下界子算法求該問題的初始下界，在回溯子算法中調(diào)用下界子算法求出當(dāng)前狀態(tài)下的下界，若在該狀態(tài)下出現(xiàn)下界大于上界，則結(jié)束該狀態(tài)下的搜索，形成剪枝，提高搜索效率。 Step 1 初始化b=0，集合Temp_0={}，Temp_1={}，Temp_2={}，Temp_V={}； Step 2 根據(jù)上文中的數(shù)學(xué)性質(zhì)將一定在、不在S*中的頂點(diǎn)分別添加到V1、V0，假設(shè)在S*中的頂點(diǎn)加到VV1，假設(shè)不在S*中的頂點(diǎn)加到VV0，執(zhí)行VV5=V＼V1＼V0＼VV1＼VV0； Step 3 由于V1∪VV1中的頂點(diǎn)一定在解中，則把V1∪VV1中頂點(diǎn)的成本費(fèi)用累加得到累加和sum1，執(zhí)行b=b+sum1； Step 4 把圖G中有兩個頂點(diǎn)都在集合V0∪VV0中的邊都放到集合Temp_0中，由于Temp_0中的邊不可能被覆蓋，因此把Temp_0中的每一條邊的懲罰費(fèi)用p（vi，vj）累加得到累加和sum 2，執(zhí)行b=b+ sum 2； Step 5 把圖G中有0個頂點(diǎn)在集合V1∪VV1中且有0個頂點(diǎn)在V0∪VV0中的邊都放到集合Temp_1中，把圖G中有0個頂點(diǎn)在集合V1∪VV1中且有1個頂點(diǎn)在V0∪VV0中的邊都放到集合Temp_2中； Step 6 k=1； Step 7 對于Temp_2中第k條邊eij，設(shè)eij的頂點(diǎn)vi在V0∪VV0中，若vj?Temp_V，此時邊eij可能被覆蓋也可能不被覆蓋，如果eij不被覆蓋，則其懲罰費(fèi)用為p（vi，vj），如果eij被覆蓋，則至少需要付出的頂點(diǎn)成本為c（vj）；而這兩種情況必然有一種情況發(fā)生，因此執(zhí)行b=b+min{p（vi，vj），c（vj）}，Temp_V=Temp_V∪vj；若vj?Temp_V則不操作，因?yàn)榇藭r的邊eij可能被Temp_V中的頂點(diǎn)覆蓋； Step 8 k=k+1；若k≤|Temp_2|則跳到Step 7； Step 9 k=1； Step 10 對于Temp_1中第k條邊eij，若vi?Temp_V且vj?Temp_V，此時eij可能被覆蓋也可能不被覆蓋，如果eij不被覆蓋，則其懲罰費(fèi)用為p（vi，vj），如果eij被覆蓋，則至少需要付出的頂點(diǎn)成本為min{c（vi）， c（vj）}；而這兩種情況必然有一種情況發(fā)生，因此執(zhí)行b=b+min{p（vi，vj），c（vi），c（vj）}，Temp_V=Temp_V∪vi∪vj；若vi?Temp_V或vj?Temp_V則不操作，因?yàn)榇藭r的eij可能被Temp_V中的頂點(diǎn)覆蓋； Step11 k=k+1；若k≤|Temp_1|則跳到Step 10； 算法結(jié)束后，b即為在V1，VV1，V0，VV0確定情況下的下界值。 2.3 降階回溯算法 降階子算法是利用數(shù)學(xué)性質(zhì)來確定圖中某些頂點(diǎn)在或不在S*中，從而降低問題規(guī)模。回溯子算法是從根節(jié)點(diǎn)出發(fā)，以深度優(yōu)先的方式對VV5進(jìn)行搜索。搜索到任意vi先計算當(dāng)前下界b1，再判斷下界b1是否小于等于上界，若不滿足則進(jìn)行剪枝；若滿足則分兩種情況：情況①假設(shè)頂點(diǎn)vi在S*中，對應(yīng)搜索左子樹；情況②假設(shè)頂點(diǎn)vi不在S*中，對應(yīng)搜索右子樹。 ⑴ 降階子算法具體步驟 Step 1 輸入圖G=（V， E），初始化V1={}，V0={}，V5=V，VV1={}，VV0={}，VV5={}，E1={}，E0={}，EVV0={}，EVV1={}，E5=E＼E＼E0，EVV5={}，S={}，S*={}，z=0，z*=+∞； Step 2 若圖G滿足性質(zhì)10，則該問題多項(xiàng)式時間內(nèi)可求得最優(yōu)解，輸出最優(yōu)解S*={}，最優(yōu)解對應(yīng)的目標(biāo)函數(shù)值為圖中所有邊懲罰費(fèi)用之和，退出求解程序；否則跳到Step 2； Step 3 根據(jù)性質(zhì)1、2、3、4、6、7、5、8、9進(jìn)行降階； Step 4 調(diào)用上、下界子算法，若u=b，則z*=u，結(jié)束算法； Step 5 調(diào)用回溯子算法Backtrack（1）。 調(diào)用回溯子算法Backtrack（1）之前，令cur_i為當(dāng)前搜索層數(shù)，對集合初始化：VV5=V5，VV1={}，VV0={}，EVV0={}，EVV1={}，EVV5=E＼E1＼E0，S={}，S*={}，z=0，z*=u；再將集合VV5中vi的鄰接邊集E（G，vi）中未被集合VV1∪V1中的頂點(diǎn)所覆蓋邊懲罰費(fèi)用之和減去vi成本費(fèi)用c（vi）的值βi計算出來，即βi=P0（VV1∪V1，vi）[-]c（vi），并按照βi的大小進(jìn)行降序排列。 ⑵ 回溯子算法Backtrack（cur_i）具體步驟 Step 1 若cur_i>|VV5| 或VV5={}，則搜索到葉節(jié)點(diǎn)，此時解為S=VV1∪V1，若z Step 2 在VV5中找βi最大的vi，假設(shè)頂點(diǎn)vi在S*中，VV1=VV1∪{vi}，VV5 =VV5＼{vi}，調(diào)用下界子算法計算出當(dāng)前情況下的下界b，若b≤u，則該狀態(tài)下可能存在比S更優(yōu)的解，調(diào)用Backtrack（cur_i+1）進(jìn)入左子樹進(jìn)行搜索；若b>u，則當(dāng)前情況下不存在最優(yōu)解并剪枝，跳到Step 3； Step 3 返回上一層前執(zhí)行VV1=VV1＼{vi}，VV5=VV5∪{vi}； Step 4 在VV5中找βi最大的vi，假設(shè)頂點(diǎn)vi不在S*中，VV0=VV0∪{vi}；VV5=VV5＼{vi}，調(diào)用下界子算法計算出當(dāng)前情況下的下界b，若b≤u，則該狀態(tài)下可能存在比S更優(yōu)的解，調(diào)用Backtrack（cur_i+1）進(jìn)入右子樹進(jìn)行搜索；若b>u，則當(dāng)前情況下不存在最優(yōu)解并剪枝，跳到Step 5； Step 5 返回上一層前執(zhí)行VV0=VV0＼{vi}，VV5=VV5∪{vi}。 算法結(jié)束后，S*即為該問題的最優(yōu)解。 2.4 應(yīng)用案例分析 如圖1為A公司在某區(qū)域擬建快遞配送點(diǎn)示意圖，該公司計劃擬建快遞配送點(diǎn)最多n=11個，各配送點(diǎn)建設(shè)成本費(fèi)用為圖中頂點(diǎn)的權(quán)值，因某些原因無法擬建配送點(diǎn)所造成的懲罰費(fèi)用為圖中邊權(quán)值。設(shè)計出以盡可能少的配送點(diǎn)來服務(wù)更多的客戶其數(shù)學(xué)模型就是獎勵-收集頂點(diǎn)覆蓋問題。 案例的具體求解過程： ⑴ 初始化集合：V1={}，V0={}，V5=V，VV1={}，VV0={}，VV5={}，E1={}，E0={}，EVV0={}，EVV1={}，E5=E＼E＼E0，EVV5={}，S={}，S*={}，z=0，z*=+∞； ⑵ 調(diào)用降階子算法得出V1={v1，v3，v9}，V0={v2，v5，v6，v8，v11}，V5=V＼V1＼V0，E1={（v3，v9}，E0={}，E5=E＼E1＼E0； ⑶ 計算上界：調(diào)用上界子算法計算出當(dāng)前上界u1=15，此時Su={v1，v3，v4，v9，v10}； ⑷ 回溯部分：令VV5=V5，調(diào)用回溯子算法求解，如圖2解空間所示，得出S*={v1，v3，v9，v10}。 由此，A公司應(yīng)在上述⑷中S*的位置上擬建快遞配送點(diǎn)所要的花費(fèi)最小。 2.5 算法時間復(fù)雜度分析與對比 本文以圖的頂點(diǎn)數(shù)n作為問題的規(guī)模，除回溯子算法外，其他子算法的時間復(fù)雜度都是多項(xiàng)式時間算法，因此僅需分析回溯子算法的時間復(fù)雜度。利用本文的數(shù)學(xué)性質(zhì)對問題的規(guī)模進(jìn)行降階，在進(jìn)入回溯子算法前，進(jìn)一步壓縮搜索空間。此外，進(jìn)入回溯子算法后，在導(dǎo)出子圖G[VV5]中以VV5中最大βi值所對應(yīng)的頂點(diǎn)在或不在最優(yōu)獎勵收集頂點(diǎn)覆蓋集合S*中進(jìn)行分支。所以，該問題規(guī)模由n經(jīng)過降階子算法之后降低到k=|V5|≤n，因此，該算法最壞時間復(fù)雜度為O（2k）。 目前，求解該問題主要算法有啟發(fā)式算法、近似算法、精確算法；本文的算法克服了啟發(fā)式算法與近似算法在一般情況下不能得到問題的最優(yōu)解的缺點(diǎn)；而傳統(tǒng)精確算法雖然可以保證求得問題的最優(yōu)解，但因未考慮該問題的數(shù)學(xué)性質(zhì)，求解速度慢，其最壞時間復(fù)雜度為O（2n），高于本文提出的降階回溯算法的最壞時間復(fù)雜度O（2k），其中k=|V5|≤n。比如用一般精確算法求解本文案例，其最壞時間復(fù)雜度為O（211），本文算法由于利用數(shù)學(xué)性質(zhì)進(jìn)行降階與求解，求解案例的時間復(fù)雜度為O（23），其求解速度比一般精確算法快。 3 結(jié)束語 本文首先研究問題的數(shù)學(xué)性質(zhì)，然后設(shè)計出上下界子算法、降階子算法、回溯子算法。一般情況下，本文的降階子算法可以降低問題的規(guī)模，進(jìn)而降低該問題的時間復(fù)雜度。相比于近似算法和啟發(fā)式算法，本文算法的優(yōu)點(diǎn)是可以得到該問題的最優(yōu)解，相較于傳統(tǒng)精確算法，其優(yōu)點(diǎn)是利用該問題的數(shù)學(xué)性質(zhì)降階從而使得時間復(fù)雜度更低。最后，本文所提出的數(shù)學(xué)性質(zhì)不僅可以用于本文算法，還可與啟發(fā)式算法等其他算法結(jié)合起來求解該問題，能夠加快其他算法的求解速度。 參考文獻(xiàn)（References）： [1] Balas E. The prize collecting traveling salesman problem[J].Networks，1989，19（1）：621-626 [2] Karp R.M. Reducibility among combinatorial problem[J].Complexity of Computer Computations，1972，43（1）：85-103 [3] 王露芝.求解最小頂點(diǎn)覆蓋問題的精確算法研究[D].碩士，東北師范大學(xué)，2020 [4] 杜俊峰，涂建華.獎勵-收集頂點(diǎn)覆蓋問題的一個2-近似算法[J].北京化工大學(xué)學(xué)報（自然科學(xué)版），2014，41（2）：120-123 [5] 郭金雙.部分獎勵-收集頂點(diǎn)覆蓋問題的近似算法[D].碩士，河北師范大學(xué)，2021 [6] Konemann J， et al. A Unified Approach to ApproximatingPartial Covering Problems[J]. Algorithmica，2011，59（4）：489-509 [7] Levin A， Segev D. Partial multicuts in trees[J]. TheoreticalComputer Science，2006，369（1）：384-392 [8] 王辰尹，倪耀東，柯華.模糊環(huán)境下的最小權(quán)頂點(diǎn)覆蓋問題[J].計算機(jī)應(yīng)用研究，2012，29（1）：38-42
