回溯法與分枝限界法的分析與比較

楊超 何書(shū)前 鄭志群 石春

摘要：主要對(duì)回溯法與分枝限界法進(jìn)行了分析與研究。首先介紹了兩種算法的基本概念，引出它們的基本解題思想與過(guò)程。然后運(yùn)用0-1背包問(wèn)題分別對(duì)回溯法，隊(duì)列式分枝界限法和優(yōu)先隊(duì)列式分枝界限法進(jìn)行詳細(xì)的分析與說(shuō)明。進(jìn)一步總結(jié)算法的異同，研究發(fā)現(xiàn)回溯法解決問(wèn)題時(shí)對(duì)內(nèi)存空間的要求更低，而分枝限界法解決問(wèn)題時(shí)需要的時(shí)間更短。

關(guān)鍵詞：回溯法；分枝限界法；0-1背包問(wèn)題

中圖分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）11-0044-03

Analysis and Comparison of Backtracking and Branch-and-bound Methods

YANG Chao ， HE Shu-qian， ZHENG Zhi-qun ，SHI Chun*

（School of Information Science and Technology， Hainan Normal University， Haikou 571158，China）

Abstract：This paper mainly analyzes and studies the backtracking and the branch-and-bound method. First， the basic concepts of the two algorithms are introduced， and their basic idea and process of solving the problem are introduced. Then the 0-1 knapsack problem is used to analyze and explain the backtracking method， the queue branch boundary method and the priority queue branch and boundary method in detail. By further summarizing the similarities and differences of the algorithm， it is found that the memory space requirement is lower when the backtracking method solves the problem， while the branch-and-bound method takes shorter time to solve the problem.

Key words： backtracking； branch and bound method； 0-1 knapsack problem

1 回溯法與分枝限界法

1.1 回溯法

回溯法指在一個(gè)解空間樹(shù)中（樹(shù)中包括問(wèn)題的所有解），依照深度優(yōu)先搜索的方法，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)，得出問(wèn)題所有解的算法[1]。算法對(duì)解空間樹(shù)的某一點(diǎn)進(jìn)行搜索時(shí)，應(yīng)判斷這一結(jié)點(diǎn)是否含有這個(gè)問(wèn)題的解。如果不包含，則跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向其父節(jié)點(diǎn)回溯；否則，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先策略搜索[2]。這種以深度優(yōu)先方式搜索問(wèn)題結(jié)點(diǎn)的算法稱(chēng)為回溯法。

1.2分枝界限法

分枝限界法指在一個(gè)解空間樹(shù)中（樹(shù)中包括問(wèn)題的所有解），依照廣度優(yōu)先搜索或最小耗費(fèi)優(yōu)先搜索的方法[3]，對(duì)根結(jié)點(diǎn)的所有分枝結(jié)點(diǎn)進(jìn)行搜索，得出根結(jié)點(diǎn)所有相鄰結(jié)點(diǎn)，建立活結(jié)點(diǎn)表，對(duì)表中結(jié)點(diǎn)進(jìn)行廣度搜索或最小耗費(fèi)得出最優(yōu)解的算法。根據(jù)搜索方式的差異，分枝限界法分為兩種。廣度優(yōu)先搜索對(duì)每個(gè)結(jié)點(diǎn)的所有分枝結(jié)點(diǎn)進(jìn)行從左到右的搜索，搜索出所有可行解，通過(guò)比較他們的限界函數(shù)得出最優(yōu)解。這種解決問(wèn)題的方法稱(chēng)為隊(duì)列式分枝限界法。最小耗費(fèi)搜索需要計(jì)算每一個(gè)活結(jié)點(diǎn)的限界函數(shù)，依據(jù)函數(shù)值選擇一個(gè)最好的結(jié)點(diǎn)成為擴(kuò)展結(jié)點(diǎn)，使搜索最優(yōu)解變得快捷。這種解決問(wèn)題的方法稱(chēng)為優(yōu)先隊(duì)列式分枝限界法。

2 回溯法與分枝限界法基本解題思想與過(guò)程

2.1回溯法求解問(wèn)題

如圖1所示，利用回溯法對(duì)問(wèn)題進(jìn)行求解時(shí)，應(yīng)先確定其解空間并保證解空間中至少含有一個(gè)解。為了使得回溯法搜索解空間時(shí)變得方便，要運(yùn)用子集樹(shù)和排列樹(shù)把解空間組織起來(lái)進(jìn)行深度優(yōu)先搜索得到問(wèn)題的所有解。下圖講述了回溯法如何對(duì)解空間樹(shù)進(jìn)行深度優(yōu)先搜索：

如圖2所示，回溯法從根結(jié)點(diǎn)出發(fā)，以深度優(yōu)先方式搜索整個(gè)解空間[4]。在根結(jié)點(diǎn)處向縱深方向搜索一個(gè)新的結(jié)點(diǎn)，若這個(gè)新結(jié)點(diǎn)可以再向縱深方向搜索，則這個(gè)新結(jié)點(diǎn)成為活結(jié)點(diǎn)，即為擴(kuò)展結(jié)點(diǎn)。反之，當(dāng)前結(jié)點(diǎn)成為死結(jié)點(diǎn)。此時(shí)應(yīng)回溯，移動(dòng)至其父結(jié)點(diǎn)，使之成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。當(dāng)回溯至根結(jié)點(diǎn)且所有結(jié)點(diǎn)都被標(biāo)記時(shí)即搜索結(jié)束。

2.2分枝界限法求解問(wèn)題

分枝限界法與回溯法類(lèi)似，區(qū)別在于對(duì)于解空間樹(shù)的搜索方式上的不同和搜索出的結(jié)果形式不同。分枝限界發(fā)采用的是廣度優(yōu)先或最小耗費(fèi)優(yōu)先搜索的方式，得出的結(jié)果一般是最優(yōu)的解。

設(shè)有活結(jié)點(diǎn)[Ni]，有四個(gè)子孩子。我們可以通過(guò)設(shè)計(jì)限界函數(shù)來(lái)刪除兩個(gè)不必要的孩子結(jié)點(diǎn)。如下圖所示：

圖4所示，分枝限界法通過(guò)設(shè)置合理的限界函數(shù)來(lái)對(duì)解空間樹(shù)進(jìn)行剪枝處理，使分枝限界法搜索效率提高；也可以通過(guò)限界函數(shù)來(lái)判定最優(yōu)解。

在對(duì)解空間樹(shù)進(jìn)行搜索時(shí)候，根據(jù)分枝限界法搜索方式的不同，可以制定不同的活結(jié)點(diǎn)表。隊(duì)列式分枝限界法的活結(jié)點(diǎn)表中起始只有根結(jié)點(diǎn)，表中結(jié)點(diǎn)按照隊(duì)列順序出表，每個(gè)活結(jié)點(diǎn)出表后需要將它的子結(jié)點(diǎn)按從左到右的順序進(jìn)入表中，若子結(jié)點(diǎn)為葉子結(jié)點(diǎn)，則構(gòu)成一個(gè)可行解，可以不用入表，當(dāng)活結(jié)點(diǎn)表為空，算法結(jié)束。優(yōu)先隊(duì)列式分枝限界法建立的活結(jié)點(diǎn)表的不同之處在于，出表結(jié)點(diǎn)的順序是通過(guò)限界函數(shù)的大小來(lái)決定。

分枝限界法中每個(gè)結(jié)點(diǎn)都保存了從開(kāi)始結(jié)點(diǎn)到這個(gè)結(jié)點(diǎn)的路徑或者是這個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)指針。因?yàn)榉种ο藿绶▽?duì)結(jié)點(diǎn)的處理是跳躍式的，只有這樣才能在搜索到可行解時(shí)得到相對(duì)應(yīng)的解向量。

3 用回溯法與分枝限界法求解0-1背包問(wèn)題

3.1 問(wèn)題描述

設(shè)n件物品的重量分別為[w1、w2、w3、…、wn]，用數(shù)組w[1..n]表示，物品的價(jià)值分別為[v1、v2、v3、…、vn]，用數(shù)組v[1..n]表示，求一個(gè)負(fù)重不超過(guò)W的背包最多可以裝多少價(jià)值的物品。（n=3； W=30；w=（16，15，15）；v=（45，25，25））

3.2 問(wèn)題分析

由題可知，以背包里物品價(jià)值和重量為狀態(tài)，開(kāi)始狀態(tài)是背包里的價(jià)值和重量都為空，背包放入物體重量不超過(guò)30可以引出2個(gè)狀態(tài)，又根據(jù)這些狀態(tài)引出其他狀態(tài)，這些狀態(tài)和它們的關(guān)系構(gòu)造了問(wèn)題的解空間。

3.3 用回溯法解0-1背包問(wèn)題

回溯法通過(guò)對(duì)解空間的組織得出解空間樹(shù)，按照深度優(yōu)先搜索解空間樹(shù)，得出所有可行解，通過(guò)比較各個(gè)可行解背包里物品價(jià)值來(lái)得到最優(yōu)解。如下圖所示：

圖5所示，w代表背包里的重量；v代表背包里物品的總價(jià)值；連線上的0代表下一個(gè)物體不放入背包，1代表下一個(gè)物體放入背包；圓圈里的字母代表回溯法搜索解空間樹(shù)結(jié)點(diǎn)的順序，按照字母表排序。由字母順序可以看到，回溯法搜索解空間樹(shù)時(shí)，優(yōu)先向縱深方向搜索，每搜索到一個(gè)可擴(kuò)展結(jié)點(diǎn)時(shí)將結(jié)點(diǎn)進(jìn)行入棧操作，當(dāng)搜索到的結(jié)點(diǎn)無(wú)法擴(kuò)展時(shí)，對(duì)結(jié)點(diǎn)進(jìn)行出棧操作，回溯到它的父結(jié)點(diǎn)繼續(xù)向縱深搜索，直到回溯到根結(jié)點(diǎn)且根結(jié)點(diǎn)也無(wú)法擴(kuò)展時(shí)算法才結(jié)束。此題回溯法搜索可行解過(guò)程如下：

首先由根結(jié)點(diǎn)A入棧；縱深搜索到B，B入棧；縱深搜索到C，由于C結(jié)點(diǎn)超重所以無(wú)法進(jìn)行擴(kuò)展，回溯到B；縱深搜索到D；縱深搜索到E，E超重；回溯到D；縱深搜索到F，F(xiàn)為葉子節(jié)點(diǎn)，得出一個(gè)可行解；回溯到D，D無(wú)法再擴(kuò)展，回溯到B；B也無(wú)法擴(kuò)展，回溯到A；縱深搜索到G；縱深搜索到H；縱深搜索到I，可行解；回溯到H；縱深搜索到J，可行解；回溯到H；回溯到G；縱深搜索到K；縱深搜索到L，可行解；回溯到K；縱深搜索到M，可行解；回溯到K；回溯到G；回溯到A，根結(jié)點(diǎn)A無(wú)法擴(kuò)展，算法結(jié)束。

我們可以看到，這個(gè)問(wèn)題一共有5個(gè)可行解，結(jié)點(diǎn)I所代表的可行解v最大，所以解出來(lái)當(dāng)背包物品重量為30時(shí)，價(jià)值為50時(shí)的解為此題最優(yōu)解。

3.4 用隊(duì)列式分枝限界法解0-1背包問(wèn)題

隊(duì)列式分枝限界法通過(guò)對(duì)解空間的組織得出解空間樹(shù)，按照廣度優(yōu)先搜索解空間樹(shù)，得出可行解，通過(guò)比較各個(gè)可行解的限界函數(shù)ub得到最優(yōu)解。圖6為隊(duì)列式分枝界限法解決0-1背包問(wèn)題時(shí)的解空間樹(shù)，樹(shù)中結(jié)點(diǎn)內(nèi)字母代表隊(duì)列式分枝限界法搜索空間樹(shù)時(shí)對(duì)各結(jié)點(diǎn)的訪問(wèn)順序：

如圖6所示，i表示解空間樹(shù)的層，w表示重量，v表示價(jià)值 ，0-1背包問(wèn)題各結(jié)點(diǎn)的限界函數(shù)ub設(shè)定方法如下：

設(shè)已裝入總重量為e.w，已裝入的總價(jià)值為e.v，物品k+1裝入背包的部分重量為[wk+1]，物品k+1的單位價(jià)值為[vk+1]。

首先需要滿足

[e.wi+e.wi+1<=W]

當(dāng)下一個(gè)物品可以全部裝入背包時(shí)，價(jià)值上界為：

[e.ub=e.v+j=i+1nv[j]]

當(dāng)下一個(gè)物品不可全部裝入背包時(shí)，價(jià)值上界為：

[e.ub=e.v+j=i+1kv[j]+wk+1*vk+1]

設(shè)隊(duì)列FIFO[]， 此題隊(duì)列式分枝限界法搜索可行解過(guò)程如下：

A進(jìn)隊(duì)，其ub=68，F(xiàn)IFO=[A]。

A出隊(duì)，孩子結(jié)點(diǎn)B、C進(jìn)隊(duì)，B的ub=68，C的ub=50，F(xiàn)IFO=[B、C]。

B出隊(duì)，因?yàn)镈的w=31>30，舍棄該結(jié)點(diǎn)，E進(jìn)隊(duì)，其ub=68，F(xiàn)IFO=[C、E]。

C出隊(duì)，F(xiàn)、G進(jìn)隊(duì)，F(xiàn)的ub=50，G的ub=25，F(xiàn)IFO=[E、F、G]。

E出隊(duì)，因?yàn)橛液⒆親的w=31>30，舍棄該結(jié)點(diǎn)。得出左孩子I的ub=45，是一個(gè)可行解，暫時(shí)作為最大價(jià)值解maxv，解向量為（1、0、0）。FIFO=[F、G]。

F出隊(duì)，得出左孩子J的ub=50>45，是一個(gè)可行解，暫時(shí)作為maxv，解向量為（0、1、1）。因?yàn)橛液⒆覭的ub=25

G出隊(duì)，得出左孩子L的ub=25，是一個(gè)可行解，解向量為（0、1、1）。因?yàn)橛液⒆覯的ub=0

FIFO隊(duì)列為空，算法結(jié)束。

maxv是結(jié)點(diǎn)I的ub，I的解向量為（0、1、1），w=30，v=50。所以當(dāng)背包物品重量為30時(shí)，價(jià)值為50時(shí)的解為此題最優(yōu)解。

3.5 用優(yōu)先隊(duì)列式分枝限界法解0-1背包問(wèn)題

優(yōu)先隊(duì)列式分枝限界法通過(guò)對(duì)解空間的組織得出解空間樹(shù)，按照最小耗費(fèi)優(yōu)先搜索解空間樹(shù)，得出最優(yōu)解。其限界函數(shù)ub的設(shè)定與隊(duì)列式分枝限界法相同。下圖為優(yōu)先隊(duì)列式分枝界限法解決0-1背包問(wèn)題時(shí)的解空間樹(shù)：

設(shè)隊(duì)列FIFO[]， 此題優(yōu)先隊(duì)列式分枝限界法搜索可行解過(guò)程如下：

A進(jìn)隊(duì)，其ub=68，F(xiàn)IFO=[A]。

A出隊(duì)，孩子結(jié)點(diǎn)B、C進(jìn)隊(duì)，B的ub=68，C的ub=50，B（ub）>C（ub）（B的ub大于C的ub），F(xiàn)IFO=[B、C]。

B出隊(duì)，因?yàn)镈的w=31>30，舍棄該結(jié)點(diǎn)，E進(jìn)隊(duì)，其ub=68，E（ub）>C（ub），F(xiàn)IFO=[E、C]。

E出隊(duì)，右孩子F的w=31>30，舍棄該結(jié)點(diǎn)。左孩子G的ub=45，是一個(gè)可行解，暫時(shí)作為最大價(jià)值解maxv，解向量為（1、0、0）。FIFO=[C]。

C出隊(duì)，左孩子H進(jìn)隊(duì)，其ub=50。由于右孩子的ub=25，小于maxv，舍棄該結(jié)點(diǎn)。 FIFO=[H]。

H出隊(duì)，得出左孩子J的v=50>45，是一個(gè)可行解，暫時(shí)作為maxv，解向量為（0、1、1），因?yàn)橛液⒆覭的ub=25

FIFO隊(duì)列為空，算法結(jié)束。

maxv是結(jié)點(diǎn)J的ub，J的解向量為（0、1、1），w=30，v=50。所以當(dāng)背包物品重量為30時(shí)，價(jià)值為50時(shí)的解為此題最優(yōu)解。

4 總結(jié)

回溯法與分枝限界法都是將問(wèn)題的解空間組織成為解空間樹(shù)，在樹(shù)上對(duì)問(wèn)題的解進(jìn)行搜索的算法，且兩種算法都屬于窮舉法?；厮莘ㄟ\(yùn)用深度優(yōu)先搜索結(jié)點(diǎn)，堆棧存儲(chǔ)結(jié)點(diǎn)，通?？梢哉页鰡?wèn)題的所有解；分枝界限法運(yùn)用的是廣度優(yōu)先或者是最小耗費(fèi)優(yōu)先搜索結(jié)點(diǎn)，隊(duì)列或者優(yōu)先隊(duì)列存儲(chǔ)結(jié)點(diǎn)，通常找出的是問(wèn)題在某種意義上的最優(yōu)解。相比與回溯法，分枝界限法對(duì)最優(yōu)解的搜索效率會(huì)更高。但由于分枝限界法每個(gè)結(jié)點(diǎn)都需要存儲(chǔ)路徑或雙親結(jié)點(diǎn)，需要比較大的存儲(chǔ)空間，所以在內(nèi)存容量有限的情況下，回溯法對(duì)問(wèn)題求解成功率會(huì)更大。

參考文獻(xiàn)：

[1] 董鵬.吳艷群.張春民.應(yīng)用回溯算法求解多樞紐選址問(wèn)題[J]. 交通與計(jì)算機(jī)， 2004（8）.

[2] 胡金初. 計(jì)算機(jī)算法[M].北京：清華大學(xué)出版社#北京交通大學(xué)出版社，2009.

[3] 王春梅. 分支限界算法的研究與實(shí)現(xiàn)[J]. 現(xiàn)代電子技術(shù)，2011.

[4] 李春葆. 算法設(shè)計(jì)與分析[M]. 北京：清華大學(xué)出版社，2015.