算法課件以及實驗指導(dǎo)書第5章回溯

第5章

回溯法Back

Tracking11

回溯法框架2

裝載問題3

0-1背包問題4圖的m著色問題The

m-coloring

Problem5

旅行售貨員問題Traveling

Salesman

Problem2有許多問題，當(dāng)需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時，往往要使用回溯法?？梢韵到y(tǒng)地搜索一個問題的所有解或任意解，既有系統(tǒng)性，又有跳躍性。3回溯法The

n-Queens

Problem4Place

nqueens

on

an

nby

n

chessboard

so

that

no

two

of

them

are

onthe

same

row,

column,

or

diagonal.例：n后問題5例:在一個n×n的棋盤上放置n個皇后，要求每兩個之間都不能相互“攻擊”，即使得任兩個皇后都不在同一行、同一列及同一條斜線上。12346111???21??212????12?3123????123??4abcdefgh7Depth-first

search回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的方法稱為回溯法。適用于解一些組合數(shù)相當(dāng)大的問題。85.1

回溯法的算法框架1.

問題的解空間問題的解空間應(yīng)至少包含問題的一個（最優(yōu)）解。例如：對于有n種可選擇物品的0-1背包問題，其解空間由長度為n的0-1向量組成，該解空間包含了對變量的所有可能的0-1賦值。當(dāng)n

=3時，解空間為{

(0,

0,

0

),

(0,

1,

0

)

,

(

0,

0,

1

)，(

1,

0,

0

),

(

0,

1,

1

),(1,

0,

1),(1,

1,

0),(1,

1,

1)}。5.1

回溯法的算法框架910問題的解空間定義了問題的解空間后，還應(yīng)將解空間很好地組織起來，使得用回溯法能方便地搜索解空間，通常組織成樹或圖的形式。n=3時的0-1背包問題用完全二叉樹表示的解空間，從根結(jié)點到結(jié)點H的路徑相應(yīng)于解空間中的元素（1，1，1）。5.1

回溯法的算法框架11例：1.對于n

=3時的0-1背包問題，w

=[16,15,15],v

=

[45,

25,

25],

c

=

30r

=

14v

=

45r

=

14v

=

45v

=

45r

=

30v

=

0r

=

15v

=

25v

=

50v

=

25r

=

30v

=

0v

=

25v

=

0根結(jié)點的孩子已經(jīng)都被搜索過，搜索結(jié)束。5.1

回溯法的算法框架12回溯法在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點時，總是先判斷該結(jié)點是否肯定不包含問題的解，如果肯定不包含，則跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點回溯。否則進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。用來求問題的所有解時，要回溯到根，且根結(jié)點的所有子樹都已被搜索遍才結(jié)束。用來求問題的任一解時，只要搜索到問題的一個解就可結(jié)束。回溯法適用于解一些組合數(shù)較大的問題。5.1

回溯法的算法框架生成問題狀態(tài)的基本方法擴展結(jié)點:一個正在產(chǎn)生兒子的結(jié)點稱為擴展結(jié)點?；罱Y(jié)點:一個自身已生成但其兒子還沒有全部生成的節(jié)點稱做活結(jié)點。死結(jié)點:一個所有兒子已經(jīng)產(chǎn)生的結(jié)點稱做死結(jié)點。死結(jié)點擴展結(jié)點活結(jié)點5.1

回溯法的算法框架13深度優(yōu)先的問題狀態(tài)生成法：如果對一個擴展結(jié)點

R，一旦產(chǎn)生了它的一個兒子C，就把C當(dāng)做新的擴展結(jié)點。在完成對子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴展結(jié)點，繼續(xù)生成R的下一個兒子（如果存在）。5.1

回溯法的算法框架14寬度優(yōu)先的問題狀態(tài)生成法：在一個擴展結(jié)點變成死結(jié)點之前，它一直是擴展結(jié)點。5.1

回溯法的算法框架15回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(boundingfunction)來處死那些實際上不可能產(chǎn)生所需解的活結(jié)點，以減少問題的計算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法。5.1

回溯法的算法框架16從開始結(jié)點（根結(jié)點）出發(fā)，它成為第一個活結(jié)點， 也成為當(dāng)前的擴展結(jié)點。在當(dāng)前的擴展結(jié)點處，搜索向縱深方向移至一個新 結(jié)點。這個結(jié)點就成為一個新的活結(jié)點，并成為當(dāng) 前擴展結(jié)點。如果在當(dāng)前的擴展結(jié)點處不能再向縱深方向移動， 則當(dāng)前的擴展結(jié)點就成為死結(jié)點，此時應(yīng)往回移動（回溯）至最近的一個活結(jié)點處，并使這個活結(jié)點成為當(dāng)前的擴展結(jié)點，用這種方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已無活結(jié)點為止。2.回溯法的基本思想5.1

回溯法的算法框架17例2.設(shè)某售貨員要到若干城市去推銷商品，已知各城市之間的路程（或路費）。他要選定一條從駐地出發(fā)，經(jīng)過每個城市一遍，最后回到駐地的路線，使總的路程最小。5.1

回溯法的算法框架18旅行售貨商問題給定一個有n個頂點的帶權(quán)圖G=(V,E)，旅行售貨員問題要找出圖G的費用（權(quán)）最小的周游路線，下圖是一個4頂點無向帶權(quán)圖。頂點序列1，2，4，3，1；1，3，2，4，1和1，4，3，2，1是該圖中3條不同的周游路線。12343061020545.1

回溯法的算法框架19該問題的解空間可以組織成一棵樹，從樹的根結(jié)點到任一結(jié)點的路徑定義了圖G的一條周游路線。ACEFGHKLMNOPQ12B3D43443244I22J3325.1

回溯法的算法框架20回溯法的基本步驟(1)針對所給問題，定義問題的解空間；

(2)確定易于搜索的解空間結(jié)構(gòu)；(3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。常用剪枝函數(shù)：用約束函數(shù)在擴展結(jié)點處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹。5.1

回溯法的算法框架21回溯法的基本步驟用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。在任何時刻，算法只保存從根結(jié)點到當(dāng)前擴展結(jié)點的路徑。如果解空間樹中從根結(jié)點到葉結(jié)點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為

O(h(n))。而顯式地存儲整個解空間則需要O(2h(n))或O(h(n)!)內(nèi)存空間。5.1

回溯法的算法框架22233.

遞歸回溯回溯法對解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實現(xiàn)回溯法。void

backtrack

(int

t){if

(t>n)

output(x);elsefor

(int

i=f(n,t);i<=g(n,t);i++)

{x[t]=h(i);if

(constraint(t)&&bound(t))

backtrack(t+1);}}t-遞歸深度，即當(dāng)前擴展結(jié)點在解空間樹中的深度。n-用來控制遞歸深度，即解空間樹的高度。當(dāng)t>n時，算法已搜索到一個葉結(jié)點output(x)對得到的可行解x進(jìn)行記錄或輸出處理。f(n,t)和g(n,t)分別表示在當(dāng)前擴展結(jié)點處搜索過的子樹的起始編號和終止編號。h(i)表示在當(dāng)前擴展結(jié)點處x[t]的第i個可選值。constraint(t)和bound(t)表示在當(dāng)前擴展結(jié)點處的約束函數(shù)和限界函數(shù)f(

n,

1)f(

n,

2)g(

n,

2)5.1

回溯法的算法框架24迭代回溯采用樹的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個非遞歸迭代過程。void

iterativeBacktrack

(){int

t=

1;while

(

t

>

0

){if

(

f

(

n,

t

)

<=

g

(

n,

t

)

)for(

int

i

=

f(

n,

t

);

i<=g(

n,

t);

i++){x[

t

]

=

h(

i

);if(

constraint(

t

)&&bound(

t)){if

(solution(

t

)

)

output(

x

);else

t++;}}else

t--;}}Solution(t)判斷當(dāng)前擴展結(jié)點處是否已到問題的一個可行解。返回值為

true表示在當(dāng)前可擴展結(jié)點處x[1:t]是問題的一個可行解。若返回值為

false則表示在當(dāng)前擴展結(jié)點處x[1:t]只是問題的一個部分解，還需要向縱深方向繼續(xù)搜索。f(n,t)和g(n,t)分別表示在當(dāng)前擴展結(jié)點處未搜索過的子樹的起始編號和終止編號。h(i)表示在當(dāng)前擴展結(jié)點處x[t]的第i個可選值。5.1

回溯法的算法框架25子集樹遍歷子集樹需O(2n)計算時間void

backtrack

(

int

t

){if

(

t

>n

)

output(

x

);elsefor

(

int

i

=

0;

i

<=

1;

i

++){x[

t

]

=

i;if

(

legal(

t

)

)

backtrack(

t

+

1

);}}當(dāng)所給的問題是從n個元素的集合S中找出滿足某種性質(zhì)的子集時，相應(yīng)的為子集樹。例如0-1背包問題所相應(yīng)的解空間樹就是一棵子集樹，通常有2n個葉結(jié)點，其結(jié)點個數(shù)為2n+1-1。5.1

回溯法的算法框架26排列樹遍歷排列樹需要O(n!)計算時間void

backtrack

(

int

t

){if

(

t

>

n

)

output(

x

);elsefor

(

int

i

=

t;

i

<=

n;

i

++

){swap(

x[

t

],

x[

i

]

);if

(legal(t))

backtrack(t+1);swap(x[t],

x[i]);}}當(dāng)所給的問題是確定n個元素滿足某種性質(zhì)的排列時，相應(yīng)的解空間樹稱為排列樹，通常有n！個葉結(jié)點，如旅行售貨商問題。5.1

回溯法的算法框架27排列問題的遞歸算法template<class

T>void

Perm(T

list[

],

int

k,

int

m){//生成list

[k：m]的所有排列方式

int

i;if

(k

==

m){//輸出一個排列方式for

(i

=

0;

i

<=

m;

i++)cout

<<

list

[i];cout

<<

endl;}else//list[k：m]有多個排列方式//遞歸地產(chǎn)生這些排列方式for

(i=k;

i

<=

m;

i++){Swap

(list[k],

list[i]);Perm

(list,

k+1,

m);Swap

(list

[k],

list

[i]);}}5.1

回溯法的算法框架5.2

裝載問題5.2

裝載問題281.問題描述n有一批共n個集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i

的重量為wi，且

wi

￡

c1

+

c2裝載問題要求確定是否有一個合理的裝載方案可將這個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。i

=1例如，當(dāng)n=3,c1=c2=50,且w=[10,40,40]，則可以將集裝箱1和2裝到第一艘輪船上，而將集裝箱3裝到第二艘輪船上；如果w=[20,40,40]，則無法將這3個集裝箱都裝上輪船。5.2

裝載問題2930如果一個給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。(1)首先將第一艘輪船盡可能裝滿；

(2)將剩余的集裝箱裝上第二艘輪船。裝載問題等價于以下特殊的0-1背包問題。nns.t.

wixi

￡

c1i

=1xi

?

{0,1},1

￡

i

￡

nmax

wi

xii

=1用動態(tài)規(guī)劃算法解這個特殊的0-1背包問題，所需的計算時間是

O(min{c1,2n})用回溯法設(shè)計解裝載問題的O(2n)計算時間算法。在某些情況下該算法優(yōu)于動態(tài)規(guī)劃算法。5.2

裝載問題31例w={

16,

15,

15},

c

=

300160000163001615151000000111150

113131用子集樹表示其解空間，用可行性約束函數(shù)可剪去不處，用cw記當(dāng)前的裝載重量，即

cw=，則當(dāng)cw>c1時，以結(jié)點Z為根的子

樹中所有結(jié)點都不滿足約束條件，因而該子樹中的解均為不可行解，故可將該子樹剪去。

i

iw

xi

=1n滿足條件

wi

xi

￡

c1

的子樹。在子集樹的第j+1層的結(jié)點Zi

=1j5.2

裝載問題2.算法描述template<class

Type>class

Loading{friend

Type

MaxLoading(Type[],Type,int);private:void

Backtrack(int

i);int

n;

//集裝箱數(shù)Type

*

w,//集裝箱重量數(shù)組c,

//第一艘輪船的載重量cw,

//當(dāng)前載重量bestw;

//當(dāng)前最優(yōu)載重量};函數(shù)MaxLoading負(fù)責(zé)該類成員的初始化，返回不超過c的最大子集和，但未給出達(dá)到這個最大子集和的相應(yīng)子集Backtrack實現(xiàn)回溯搜索，

Backtrack(1)實現(xiàn)對整個解空間的回溯搜索，

Backtrack(i)搜索子集樹中第i層子樹。5.2

裝載問題32template<

class

Type

>Type

MaxLoading(

Type

w[

],Type

c,

int

n

){//返回最優(yōu)載重量Loading

<

Type>

x;x.

w

=

w;x.

c

=

c;x.

n

=

n;x.

bestw

=

0;x.

cw

=

0;//計算最優(yōu)載重量x.Backtrack(

1

);return

x.

bestw;}5.2

裝載問題3334Backtrack(

int

i

){//搜索第i層結(jié)點如果到達(dá)葉結(jié)點，則判斷當(dāng)前的cw，如果比前面得到的最優(yōu)解bestw好，則替換原最優(yōu)解。//搜索左子樹如果當(dāng)前剩余空間可以放下當(dāng)前物品，也就是，

cw

+

w[

i

]

<=

c，則把當(dāng)前載重

cw+=w[

i]，遞歸訪問其左子樹，Backtrack(i+1)，訪問結(jié)束，回到調(diào)用點，

cw-=w[

i]//搜索右子樹

Backtrack(

i+1);}5.2

裝載問題35template<class

Type>return;

}//搜索子樹if(

cw

+

w[

i

]

<=

c

){

//x[i]=1cw

+=

w[

i

];Backtrack(

i

+

1

);cw

-

=

w[

i

];}Backtrack(

i

+

1

);

//x[i]=0}0160001515100160001151i

=

1i

=

2i

=

316i

=

40

130void

Loading<Type>::

Backtrack(

int

i

){//搜索第i層結(jié)點if

(

i

>

n

){

//到達(dá)葉結(jié)點

?

w={

16,

15,

15},

c

=

30if(

cw

>

bestw

)

bestw

=cw;即使把剩余物品都裝里也不會得到比當(dāng)前的最優(yōu)解更好5.2

裝載問題右子樹永遠(yuǎn)可行！016003001615151510000011i

=

1i

=

2i

=

316i

=

40

1引入一個上界函數(shù)，用于剪去不含最優(yōu)解的子樹，設(shè)Z是解空間樹第i層上的當(dāng)前擴展結(jié)點。cw是當(dāng)前載重量；bestw是當(dāng)前最優(yōu)載重量；r是剩余集裝箱的重量和；定義上界函數(shù)為cw+r。在以Z為根的子樹中任一結(jié)點所相應(yīng)的載重量均不超過

cw+r。因此，當(dāng)cw+r<=

bestw時，可將Z的右子樹剪去。5.2

裝載問題363.上界函數(shù)在改進(jìn)算法中，引入類Loading的一個私有變量

r，用于計算上界函數(shù)，引入上界函數(shù)后，在達(dá)到一個葉結(jié)點時就不必再檢查該葉結(jié)點是否優(yōu)于當(dāng)前最優(yōu)解。因為上界函數(shù)使算法搜索到的每個葉結(jié)點都是

迄今為止找到的最優(yōu)解，時間復(fù)雜性沒有變化，但在平均情況下改進(jìn)后的算法檢查的結(jié)點數(shù)較

少。5.2

裝載問題37Template<class

Type>class

Loading{friend

Type

MaxLoading(Type[

],Type,

int

);private:void Backtrack(int

i);int

n;

//集裝箱數(shù)Type

*

w,

//集裝箱重量數(shù)組c,

//第一艘輪船的載重量cw,

//當(dāng)前載重量bestw，

//當(dāng)前最優(yōu)載重量r;

//剩余集裝箱重量};5.2

裝載問題3839template<class

Type>Type

MaxLoading(

Type

w[

],Type

c,

int

n

){//返回最優(yōu)載重量Loading

<

Type

>

x;x.

w

=

w;x.

c

=

c;x.

n

=

n;x.

bestw

=

0;x.

cw

=

0;x.

r

=

0;for(int

i

=1;i

<=

n;i

++)x.r+=w[i];//初始時r為全體物品的重量和//計算最優(yōu)載重量

x.Backtrack(1);return

x.bestw;}5.2

裝載問題Backtrack(

int

i

){//搜索第i層結(jié)點如果到達(dá)葉結(jié)點，bestw=cw。//修改剩余重量rr=r-w[i]//搜索左子樹如果當(dāng)前剩余空間可以放下當(dāng)前物品也就是，cw+w[i]<=c，則把當(dāng)前載重cw+=w[i]，遞歸訪問其左子樹，Backtrack(

i+1)，訪問結(jié)束，回到調(diào)用點，cw-=w[i]。//搜索右子樹如果剩余重量加上當(dāng)前載重大于最優(yōu)值，遞歸訪問右子樹，Backtrack(

i+1)。//回到上一層調(diào)用點

r=r+w[i]}5.2

裝載問題40template<

class

Type

>void

Loading<

Type

>::

Backtrack(

int

i

){//搜索第i層結(jié)點if(i>n){//到達(dá)葉結(jié)點

bestw=cw;return;

}//搜索子樹

r-=w[i];if(

cw

+

w[

i

]

<=

c){

//x[i]=1cw

+=

w[

i];Backtrack(

i

+

1

);cw

-

=w[

i

];

}if(

cw

+

r

>

bestw)

//x[i]=0Backtrack(i+1);r

+

=

w[i];}i

=

1cw

=

0bestw

=

0r

=46cw

=

0bestw

=

0r

=30i

=

2cw

=

16bestw

=

0r

=15i

=

3cw

=

16bestw

=

0r

=0i

=

4cw

=

16bestw

=

161000cw

=

0bestw

=

16r

=151cw

=

15bestw

=

16r

=0cw

=

0bestw

=

16r

=301cw

=

30bestw

=

30cw

=

15bestw

=

30r

=0cw

=

0bestw

=

30r

=15cw

=

0bestw

=

30r

=30cw

=

16bestw

=

16r

=0cw

=

16bestw

=

16r

=1541w={

16,

15,

15},

c

=

30Template<class

Type>class

Loading{friend

Type

MaxLoading(Type[

],Type,

int

,

int

[]);private:void

Backtrack(int

i);int

n;

//集裝箱數(shù)*x,

//當(dāng)前解*bestx;

//當(dāng)前最優(yōu)解Type

*

w,

//集裝箱重量數(shù)組c,

//第一艘輪船的載重量cw,

//當(dāng)前載重量bestw，

//當(dāng)前最優(yōu)載重量r;

//剩余集裝箱重量};5.2

裝載問題4243template<class

Type>Type

MaxLoading(

Type

w[

],Type

c,

int

n,

int

bestx[]

){//返回最優(yōu)載重量Loading

<

Type

>X;X.x

=

new

int[

n+1

];X.w

=

w;X.

c

=

c;X.

n=

n;X.bestx

=

bestx;X.bestw=

0;X.

cw

=

0;X.

r

=

0;for(int

i

=1;i

<=

n;i

++)X.r+=w[i];//初始時r為全體物品的重量和//計算最優(yōu)載重量

X.Backtrack(1);delete[]X.x;return

x.bestw;}5.2

裝載問題template<

class

Type

>void

Loading<

Type>::

Backtrack(

int

i

){//搜索第i層結(jié)點if(i>n){//到達(dá)葉結(jié)點for(

j

=1;

j<=n;

j++)

bestx[j]=x[j];

bestw

=

cw;return;

}//搜索子樹

r-=w[i];if(

cw

+

w[i

]

<=

c){x[i]=1;cw+=

w[

i

];Backtrack(

i+1

);cw

-=w[

i

];

}if(

cw+r

>bestw){x[i]=0;Backtrack(i+1);}r

+=w[i];}5.2

裝載問題44bestx可能被更新O(2n)次，算法計算時間復(fù)雜性為

O(n2n)。采用兩種策略之一改進(jìn)算法使其復(fù)雜度減至O(2n)首先運算只計算最優(yōu)值的算法，計算出最優(yōu)裝載量W，所需計算時間為O(2n)，然后再運行改進(jìn)后的backtrack，并在算法中將bestw置為W。動態(tài)地更新bsetx，在第i層的當(dāng)前結(jié)點處，當(dāng)前最優(yōu)解由x[j],j<i，和bestx[j]，i<=j組成，每當(dāng)算法回溯一層時，將x[i]存入bestx[i],這樣一來，在每個結(jié)點處更新bestx只需O(1)時間，從而算法中跟新bestx所需的時間為O(2n)。5.2

裝載問題45迭代回溯非遞歸的方式可以省去O(n)的遞歸棧空間template<class

Type>Type

MaxLoading(

Type

w[

],Type

c,

int

n,

int

bestx[

]

){//迭代回溯int

i=1;

//當(dāng)前層//x[1:

i-1]為當(dāng)前路徑

int

*x=new

int[

n+1];Type

bestw=0,//當(dāng)前最優(yōu)裝載重量cw

=

0;r

=

0;//當(dāng)前載重量//剩余集裝箱重量for(

int

j

=

1;

j

<=n;

j++)r

+=

w[j];5.2

裝載問題4647//搜索子樹while(

true

){while(

i<=

n

&&

cw

+

w[i]

<=

c)

{//進(jìn)入左子樹r

-=

w[

i

];cw

+=

w[i];x[i]

=

1;i++;}if(

i>n){//到達(dá)葉結(jié)點for(

int

j

=

1;

j

<=

n;

j++)bestx[j]

=

x[j];bestw=cw;}else{

//進(jìn)入右子樹r

-=

w[i];x[i]

=

0;i++;}while(

cw

+

r

<=

bestw

){//剪枝回溯i

--;while

(

i

>

0

&&

!x[

i

]

){//從右子樹返回

r+=w[i];i

--;}if(

i

==

0)

{

delete

[]

x;return

bestw;

}//進(jìn)入右子樹x[

i

]

=

0;cw

-=

w[i];i

++;}}}48//搜索子樹

while(true){while(

i<=

n

&&

cw

+

w[i]

<=

c)

{//進(jìn)入左子樹r

-=

w[

i

];cw

+=

w[i];x[i]

=

1;i++;}if(

i>n){//到達(dá)葉結(jié)點for(

int

j

=

1;

j

<=

n;j++)bestx[j]

=

x[j];bestw

=

cw;}else{

//進(jìn)入右子樹

r-=w[i];x[i]

=

0;i++;}i

=

1cw

=

0bestw

=

0r

=46cw

=

0bestw

=

0r

=30i

=

2cw

=

16bestw

=

0r

=15i

=

3cw

=

16bestw

=

0r

=0i

=

4cw

=

16bestw

=

161005.2

裝載問題w={

16,

15,

15},

c

=

30i

=

1cw

=

0bestw

=

0r

=46cw

=

0bestw

=

0r

=30i

=

2cw

=

16bestw

=

0r

=15i

=

3cw

=

16bestw

=

0r

=0i

=

4cw

=

16bestw

=

161000cw

=

0bestw

=

16r

=151cw

=

15bestw

=

16r

=0cw

=

0bestw

=

16r

=301cw

=

30bestw

=

30cw

=

15bestw

=

30r

=0cw

=

0bestw

=

30r

=15cw

=

0bestw

=

30r

=30cw

=

16bestw

=

16r

=0cw

=

16bestw

=

16r

=15while(

cw

+

r

<=

bestw

){//剪枝回溯i

--;while

(

i

>

0

&&

!x[

i

]

)

{//從右子樹返回

r+=w[i];i

--;}if(

i

==

0)

{

delete

[]

x;return

bestw;

}//進(jìn)入右子樹x[

i

]

=

0;cw

-=

w[i];i

++;}}}5.2

裝載問題49w={

16,

15,

15},

c

=

305.3

0-1背包問題5.3

0-1背包問題5051例n=4,c=7,w={

3,5,2,1},

p

=

{9,10,7,4}0,03,90,086,203,97,173,95,101000001111用子集樹表示其解空間，左兒子如果可行，進(jìn)入左子樹，只有右子樹中有可能包含最優(yōu)解時才進(jìn)入右子樹搜索，否則將右子樹剪去。上界函數(shù)：cp+r≤bestp當(dāng)前獲得價值+剩余價值≤當(dāng)前最優(yōu)價值。13,95,160105.3

0-1背包問題有時即使?jié)M足了cp+r≤bestp

，但實際上背包并不能裝下所有剩余物品，也就是上界

cp+r大了?？s小上界可以提供另一個更好的上界函數(shù)。計算右子樹中解的上界時，將剩余物品依

其單位重量價值排序，然后依次裝入物品，直至裝不下時，再裝入該物品的一部分而

裝滿背包，由此得到的價值是右子樹的上

界，如果這個上界不能達(dá)到當(dāng)前得到的最

優(yōu)值，則不搜索該子樹。5.3

0-1背包問題52以物品單位重量價值的遞減序裝入物品。n=4,

c=

7,p

={9,

10,7,4},

w={3,

5,2,1}單位價值量{3,2,3.5,

4}。先裝入物品4，然后3，1，物品2最多裝0.2，得到一個解{1,0.2,1,1}，相應(yīng)的上界為22。5.3

0-1背包問題53將物品按單位價值量排序。在解空間樹的當(dāng)前擴展結(jié)點處，僅當(dāng)要進(jìn)入右子樹時才計算上界函數(shù)Bound，判斷是否可以將右子樹剪去。進(jìn)入左子樹時，不需要計算上界。5.3

0-1背包問題54例n=4,c=7,w={1，2，3，5},

p

=

{4，7，9

，

10}0,01,

43,111116,2006,2019<2019<2020=205.3

0-1背包問題552算法描述template<class

Typew,class

Typep>class

Knap{

//背包描述friend

Typep

Knapsack(Typep*,

Typew*,Type,

int);private:Typep

Bound(int

i);void

Backtrack(int

i);Typew

c;

//背包容量int

n;

//物品數(shù)Typew

*

w,//物品重量數(shù)組

Typep

*

p,//物品價值數(shù)組

Typew

cw;//當(dāng)前重量Typep

cp;//當(dāng)前價值Typep

bestp;//當(dāng)前最優(yōu)價值};Backtrack實現(xiàn)回溯搜索，

Backtrack(1)實現(xiàn)對整個解空間的回溯搜索，

Backtrack(i)搜索子集樹中第i層子樹。計算第i層結(jié)點的上界5.3

0-1背包問題56class

Object{

//物品friend

int

Knapsack(int

*,

int

*,

int,

int

);public:int

operator

<=

(Object

a)

const{

return

(d

>=

a.d);

}private:int

ID;float

d;

//單位重量價值};5.3

0-1背包問題5758template<class

Typew,

class

Typep>Typep

Knapsack(Typep

p[

],

Typew

w[

],

Typew

c,

int

n){//為Knap::Backtrack

初始化Typew

W

=

0;Typep

P

=0;Object

*

Q

=

new

Object[n];for

(

int

i

=

1;

i

<=

n;

i++

)

{Q[

i-1].

ID

=i;Q[

i-1].

d

=1.0*p[i]/w[i];P

+=p[i];W+=w[i];}if(W<=c)return

P;//裝入所有物品//依物品單位重量價值排序

Sort(Q,n);Knap

<

Typew,

Typep

>

K;K.p

=

new

Typep[

n

+1

];K.w

=

new

Typew[

n+1];for

(

int

i

=

1;

i

<=

n;

i++){K.p[i]

=

p[Q[i-1].ID];K.w[i]=

w[

Q[i-1].ID];}K.cp

=0;K.cw

=0;K.c

=c;K.n

=

n;K.bestp

=0;//回溯搜索K.Backtrack(1);delete

[

]

Q;delete

[

]

K.w;delete

[

]

K.p;return

K.bestp;}5.3

0-1背包問題59template<class

Typew,

class

Typep>Typep

Knap<Typew,

Typep>::

Backtrack(

int

i){if

(

i

>

n

)

{bestp

=

cp;return;}if(

cw

+

w[i]

<=

c){

//x[i]

=

1cw

+=

w[i];cp

+

=

p[i];Backtraccw

-=w[icp

-

=

p[ik(i+1);];];}if(

Bound(i+1)>

bestp)

//x[i]

=

0Backtrack(i+1);}5.3

0-1背包問題如何計算？60template<class

Typew,

class

Typep>Typep

Knap<Typew,

Typep>::

Bound(

int

i){

//計算上界Typew

cleft=c–cw;//剩余容量

Typep

b=cp;//以物品單位重量價值遞減序裝入物品while

(

i<=

n

&&

w[i]<=

cleft){cleft

-=

w[i];b

+=

p[i];i++;}//裝滿背包if(

i<=n

)

b+=

p[i]/w[i]*cleft;return

b;}5.3

0-1背包問題算法效率由于計算上界函數(shù)Bound需要O(n)時間，在最壞情況下有O(2n)個右兒子結(jié)點需要計算上界函數(shù)，故解0-1背包問題的回溯算法

Backtrack所需的計算時間為O(n2n)。5.3

0-1背包問題615.4

圖的m著色問題The

m-coloring

Problem5.4

圖的m著色問題62The

m-coloring

ProblemcdGiven

a

graph

and

an

integer

m,coloritsvertices

usingno

morethan

mcolors

sothatnotwo

adjacent

vertices

are

the

same

color.aeb63問題描述給定無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點著色，每個頂點著一種顏色。是否有一種著色法使G中每條邊的2個頂點著不同顏色。這個問題是圖的m可著色判定問題。若一個圖最少需要m種顏色才能使圖中每條邊連接的2個頂點著不同顏色，則稱這個數(shù)m為該圖的色數(shù)。求一個圖的色數(shù)m的問題稱為圖的m可著色優(yōu)化問題。5.4

圖的m著色問題64四色猜想：是圖的m可著色性判斷問題的一個特殊情形，表述為：在一個平面或球面上的任何地圖能夠只用4種顏色來著色，使得相鄰的國家在地圖上著有不同顏色。任何平面圖都是可以4著色的5.4

圖的m著色問題65討論一般連通圖的可著色性問題，不僅限于平面圖。給定了已知圖G

=(V,E)和m種顏色，如果這個圖不是m可著色的就給否定回答，如果這個圖是m可著色的，則要找出所有不同的著色法。圖的m著色問題5.4

圖的m著色問題66用回溯法解決這個問題，算法中用鄰接矩陣a來表示一個無向連通圖G

=(V,E)。若(i,j)屬于圖G

=(V,E)的邊集E，則a[i

][j]=1，否則a[i][j]=0。用整數(shù)1，2，…，m來表示m種不同的顏色，頂點

i所著顏色用x[i]來表示，因此，該問題的解向量可以表示為n元組x[1:n]。圖的m著色問題5.4

圖的m著色問題67解向量：(x1,x2,…,xn)表示頂點i所著顏色x[i]問題的解空間可表示為一棵高度為n+1的完全m叉樹。解空間樹的第i(1≤i≤n)層中每一結(jié)點都有m個兒子，每個兒子相應(yīng)于x[i]的m個可能的著色之一。第n+1層結(jié)點均為葉結(jié)點。下圖為n=3和m=3時問題的解空間樹。圖的m著色問題5.4

圖的m著色問題68算法設(shè)計設(shè)Backtrack(i)表示搜索解空間中第i層子樹。當(dāng)i>n時，表示算法已搜索至一個葉結(jié)點，得到一個新的m著色方案，因此當(dāng)前已找到的可m著色方案數(shù)sum增1。當(dāng)i≤n時，當(dāng)前擴展結(jié)點Z是解空間中的一個內(nèi)部結(jié)點。該結(jié)點有x[i]=1,2,…,m共m個兒子結(jié)點。對當(dāng)前擴展結(jié)點Z的每一個兒子結(jié)點，檢查其可行性，并以深度優(yōu)先的方式遞歸地對可行子樹進(jìn)行搜索，或剪去不可行子樹。5.4

圖的m著色問題69算法描述class

Color{friend int

mColoring(int,

int,

int

*

*);private:bool

Ok(

int

k);void

Backtrack(int

t);int

n;int

m,**a,//圖的頂點數(shù)//可用顏色數(shù)//圖的鄰接矩陣*x;

//當(dāng)前解long

sum;//當(dāng)前已找到的可m著色方案數(shù)};5.4

圖的m著色問題7071int

mColoring(

int

n,

int

m,

int

**

a){Color

X;//初始化XX.n

=

n;X.m

=

m;X.a

=

a;X.sum

=

0;int

*

p

=

new

int[n+1];for(

int

i

=

0;

i<=n;

i++)p[i]=

0;X.x

=

p;X.Backtrack(1);delete

[]

p;return

X.sum;}5.4

圖的m著色問題72bool

Color::

Ok(int

k){//檢查顏色可用性for

(

int

j

=

1;

j

<=

k-1;

j++)if(

(a[k][j]

==

1)&&

(

x[j]

==

x[k]))return

false;return

true;}void

Color::Backtrack(

int

t){if(

t>n

){sum

++;for(

int

i

=1;

i<=n;

i++)cout<<x[i]<<"

";cout

<<

endl;}elsefor(

int

i=1;

i<=m;

i++

){x[t]=i;if(Ok(t))

Backtrack(t+1);}}5.4

圖的m著色問題算法效率解圖的m可著色問題的回溯算法的計算時間上界可以通過計算解空間樹中內(nèi)結(jié)點個數(shù)來估計。圖n-1的可著色問題的解空間樹中內(nèi)結(jié)點個數(shù)是

mi

。i=0對于每個內(nèi)結(jié)點，Ok檢查每個兒子所相應(yīng)的顏色可用性需要O(mn)。因此回溯算法總的時間耗費是

n-1

mi

(mn)

nm(mn

1)

/(m

1)

O(nmn

)=

-

-

=i=05.4

圖的m著色問題735.5

旅行售貨員問題traveling salesman

problem設(shè)某售貨員要到若干城市去推銷商品，已知各城市之間的路程（或路費）。他要選定一條從駐地出發(fā)，經(jīng)過每個城市一遍，最后回到駐地的路線，使總的路程最小。5.5

旅行售貨員問題7475旅行售貨商問題1234給定一個有n個頂點的帶權(quán)圖G=(V,E)，旅行售貨員問題要找出圖G的費用（權(quán)）最小的周游路線，下圖是一個4頂點無向帶權(quán)圖。頂點序列1，2，4，3，1；1，3，2，4，1和1，4，3，2，1是該圖中3條不同的周游路線。3061020545.5

旅行售貨員問題該問題的解空間可以組織成一棵樹，從樹的根結(jié)點到任一結(jié)點的路徑定義了圖G的一條周游路線。ACEFGHKLMNOPQ12B3D43443244I22J3325.5

旅行售貨員問題76旅行售貨員問題的解空間是一顆排列樹。對于排列樹的回溯搜索與生成1,2,…,n的所有排列的遞歸算法Perm類似。設(shè)開始時x=[1,2,…,n]，則相應(yīng)的排列樹由x[1:n]的所有排列構(gòu)成。5.5

旅行售貨員問題77BacktrackBacktrack(i)搜索解空間中第i層子樹。

Backtrack(2)實現(xiàn)對整個解空間的回溯搜索。當(dāng)i=n時，當(dāng)前擴展節(jié)點是排列樹的葉結(jié)點的父節(jié)點。檢測是否同時存在從x[n-1]到x[n]的邊和從

x[n]到x[1]的邊。如果存在著兩條邊，則找到一個可行解。同時計算該費用是否小于當(dāng)前最優(yōu)的費用bestc。如果是，則更新最優(yōu)值bestc和最優(yōu)解bestx。算法描述5.5

旅行售貨員問題78Backtrack當(dāng)i<n時，當(dāng)前擴展節(jié)點位于排列樹的第i-1層。如果存在從x[i-1]到x[i]的邊，則x[1:i]構(gòu)成一條路徑。計算x[1:i]的費用，如果小于當(dāng)前最優(yōu)值，則算法進(jìn)入排列樹的第i層。否則剪去該子樹。算法描述5.5

旅行售貨員問題79template<

class

Type

>c