算法設(shè)計(jì)與分析 看-

算法設(shè)計(jì)與分析山東師范大學(xué)信息科學(xué)與工程學(xué)院軟件工程研究所徐連誠E-Mail：lchxu@163.com2006年11月20日第五章回溯法2學(xué)習(xí)要點(diǎn)理解回溯法的深度優(yōu)先搜索策略掌握用回溯法解題的算法框架1）遞歸回溯最優(yōu)子結(jié)構(gòu)性質(zhì)2）迭代回溯貪心選擇性質(zhì)3）子集樹算法框架4）排列樹算法框架通過應(yīng)用范例學(xué)習(xí)回溯法的設(shè)計(jì)策略1）裝載問題；2）批處理作業(yè)調(diào)度；3）符號三角形問題4）n后問題；5）0-1背包問題；6）最大團(tuán)問題；7）圖的m著色問題8）旅行售貨員問題9）圓排列問題10）電路板排列問題11）連續(xù)郵資問題引言3有許多問題，當(dāng)需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時(shí)，往往要使用回溯法?；厮莘ǖ幕咀龇ㄊ撬阉?，或是一種組織得井井有條的、能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問題?；厮莘ㄔ趩栴}的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的

任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問題的解：如

果肯定不包含，則跳過對該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)

按深度優(yōu)先策略搜索。5.1回溯法的算法框架4本節(jié)介紹回溯法算法框架的有關(guān)問題：一、問題的解空間二、回溯法的基本思想三、遞歸回溯四、迭代回溯五、子集樹與排列樹一、問題的解空間

應(yīng)用回溯法解問題時(shí)，首先應(yīng)明確定義問題的解空間。問題的解空間應(yīng)至少包含問題的一個(gè)(最優(yōu))解。

問題的解向量：回溯法希望一個(gè)問題的解能夠表示成一個(gè)n元式(x1,x2,…,xn)的形式。顯約束：對分量xi的取值限定。隱約束：為滿足問題的解而對不同分量之間施加的約束。

解空間：對于問題的一個(gè)實(shí)例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實(shí)例的一個(gè)解空間。單，所需表解空間由長度·注意：同一個(gè)問示的狀態(tài)空間更小

例如，對于有n種為n的0-1向量組成題可以有多種表示，有些表示方法更簡（存儲(chǔ)量少，搜索方法簡單）。可選物品的0-1背包問題，其。n=3時(shí)的0-1背包問題用完全二叉樹表示的解空間5二、回溯法的基本思想6回溯法的基本步驟：(1)針對所給問題，定義問題的解空間；(2)確定易于搜索的解空間結(jié)構(gòu)；

(3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。常用剪枝函數(shù)：用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹。關(guān)于復(fù)雜性：

用回溯法解題的一個(gè)顯著特征是在搜索過程中動(dòng)態(tài)產(chǎn)生問題的解空間。在任何時(shí)刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。如

果解空間樹中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長路徑的長度為h(n)，則回溯法所需的計(jì)算空間通常為O(h(n))。而顯式地存儲(chǔ)整個(gè)解空間則需要

O(2h(n))或O(h(n)!)內(nèi)存空間。生成問題狀態(tài)的基本方法7擴(kuò)展結(jié)點(diǎn)：一個(gè)正在產(chǎn)生兒子的結(jié)點(diǎn)稱為擴(kuò)展結(jié)點(diǎn)

活結(jié)點(diǎn)：一個(gè)自身已生成但其兒子還沒有全部生成的節(jié)點(diǎn)稱做活結(jié)點(diǎn)死結(jié)點(diǎn)：一個(gè)所有兒子已經(jīng)產(chǎn)生的結(jié)點(diǎn)稱做死結(jié)點(diǎn)

深度優(yōu)先的問題狀態(tài)生成法：如果對一個(gè)擴(kuò)展結(jié)點(diǎn)R，一旦產(chǎn)生了它的一個(gè)兒子C，就把C當(dāng)做新的擴(kuò)展結(jié)點(diǎn)。在完成對子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴(kuò)展結(jié)點(diǎn)，繼續(xù)生成R的下一個(gè)兒子（如果存在）

寬度優(yōu)先的問題狀態(tài)生成法：在一個(gè)擴(kuò)展結(jié)點(diǎn)變成死結(jié)點(diǎn)之前，它一直是擴(kuò)展結(jié)點(diǎn)

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

0-1背包問題n=3,

C=30,

w={16,

15,

15},

v={45,

25,

25}開始時(shí)，Cr=C=30，V=0，A為唯一活結(jié)點(diǎn)，也是當(dāng)前擴(kuò)展結(jié)點(diǎn)擴(kuò)展A，先到達(dá)B結(jié)點(diǎn)· Cr=Cr-w1=14，V=V+v1=45此時(shí)A、B為活結(jié)點(diǎn)，B成為當(dāng)前擴(kuò)展結(jié)點(diǎn)擴(kuò)展B，先到達(dá)DCr<w2，D導(dǎo)致一個(gè)不可行解，回溯到B再擴(kuò)展B到達(dá)EE可行，此時(shí)A、B、E是活結(jié)點(diǎn)，E成為新的擴(kuò)展結(jié)點(diǎn)Cr<w3，J導(dǎo)致一個(gè)不可行解，回溯到EK不可擴(kuò)展，成為死結(jié)點(diǎn)，返回到EE沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，返回到B· B沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，返回到AA再次成為擴(kuò)展結(jié)點(diǎn)，擴(kuò)展A到達(dá)C· Cr=30，V=0，活結(jié)點(diǎn)為A、C，C為當(dāng)前擴(kuò)展結(jié)點(diǎn)· 擴(kuò)展C，先到達(dá)FCr=Cr-w2=15，V=V+v2=25，此時(shí)活結(jié)點(diǎn)為A、C、F，F(xiàn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)擴(kuò)展F，先到達(dá)Lr

r

3

3C

=C

-w

=0，V=V+v

=50L是葉結(jié)點(diǎn)，且50>45，皆得到一個(gè)可行解x=(0,1,1)，V=50L不可擴(kuò)展，成為死結(jié)點(diǎn)，返回到F再擴(kuò)展F到達(dá)MM是葉結(jié)，且25<50，不是最優(yōu)解M不可擴(kuò)展，成為死結(jié)點(diǎn)，返回到FF沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，返回到· 再擴(kuò)展C到達(dá)G擴(kuò)展G，先到達(dá)N，N是葉結(jié)點(diǎn)，且25<50，不是最優(yōu)解，又N不可擴(kuò)展，返回到G再擴(kuò)展G到達(dá)O，O是葉結(jié)點(diǎn)，且0<50，不是最優(yōu)解，又O不可擴(kuò)展，返回到GG沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，返回到C· C沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，返回到AA沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，算法結(jié)束，最優(yōu)解X=(0,1,1)，最優(yōu)值V=50ACr=C=30，V=0B11wJ

=16，v

=45擴(kuò)展E，先到達(dá)再次擴(kuò)展E到達(dá)CK由于K是葉r結(jié)點(diǎn)，即得到一個(gè)可行解x=(1,0,0)，V=45=14，V=45CrC

=30，V=0DrC

<w2不可行解JrC

點(diǎn)<w3不可行解KCr=14VC

=45H

IECr=14V=45Lw3=15，v3=25Cr=0，V=50Cr=30，V=0，活結(jié)點(diǎn)為A、C、G，G為當(dāng)前x擴(kuò)=展(結(jié)1點(diǎn),0,0)50>45x=(0,1,1)Fw2=15，v2=25rC

=15，V=25M25<50不是最優(yōu)解8示例2旅行售貨員問題問題描述：某售貨員要到若干城市去推銷商品，一直各城市之間的路程，他要選定一條從駐地出發(fā)，經(jīng)過每個(gè)城市一遍，最后回到住地的路線，使總的路程最短。該問題是一個(gè)NP完全問題，有(n-1)!條可選路線最優(yōu)解(1,3,2,4,1)，最優(yōu)值252633015410420ACEL

M

NO

P

Q2944

34

23

21B3D3

4

2

4

2

3F

G

H

I

J

K三、遞歸回溯10回溯法對解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實(shí)現(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);}}四、迭代回溯11采用樹的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個(gè)非遞歸迭代過程。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--;}}五、子集樹與排列樹遍歷子集樹需O(2n)計(jì)算時(shí)間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);}}遍歷子集樹需O(n!)計(jì)算時(shí)間void

backtrack

(int

t){if

(t>n)

output(x);elsefor

(int

i=t;i<=n;i++)

{x[t]=i;if

(legal(t))

backtrack(t+1);}}125.2裝載問題13一、問題描述二、問題分析三、算法設(shè)計(jì)四、算法描述一、問題描述14有一批共n個(gè)集裝箱要裝上2艘載重量分別為

C1和C2的輪船，其中集裝箱i的重量為wi，且∑wi≤C1+C2裝載問題要求確定是否有一個(gè)合理的裝載方案可將這個(gè)集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。容易證明，如果一個(gè)給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案：(1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上第二艘輪船。二、問題分析將第一艘輪船盡可能裝滿等價(jià)于選取全體集裝箱的一個(gè)子集，使該子集中集裝箱重量之和最接近。由此可知，裝載問題等價(jià)于以下特殊的0-1背包問題。15三、算法設(shè)計(jì)16解空間：子集樹可行性約束函數(shù)(選擇當(dāng)前元素)：上界函數(shù)(不選擇當(dāng)前元素)：當(dāng)前載重量CW+剩余集裝箱的重量R≤當(dāng)前最優(yōu)載重量BestW用回溯法設(shè)計(jì)解裝載問題的O(2n)計(jì)算時(shí)間算法。在某些情況下該算法優(yōu)于動(dòng)態(tài)規(guī)劃算法。四、算法描述n;樹void

backtrack

(int

i){//搜索第i層結(jié)點(diǎn)if(i>n)//到達(dá)葉結(jié)點(diǎn)更新最優(yōu)解bestx,bestw;returr-=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];}175.3批處理作業(yè)調(diào)度18一、問題描述二、實(shí)例分析三、算法描述一、問題描述19給定n個(gè)作業(yè)的集合{J1,J2,…,Jn}。每個(gè)作業(yè)必須先由機(jī)器1處理，然后由機(jī)器2處理。作

業(yè)Ji需要機(jī)器j的處理時(shí)間為tji。對于一個(gè)確定的作業(yè)調(diào)度，設(shè)Fji是作業(yè)i在機(jī)器j上完成處理的時(shí)間。所有作業(yè)在機(jī)器2上完成處理的時(shí)

間和稱為該作業(yè)調(diào)度的完成時(shí)間和。批處理作業(yè)調(diào)度問題要求對于給定的n個(gè)作業(yè)，制定最佳作業(yè)調(diào)度方案，使其完成時(shí)間和達(dá)到最小。二、實(shí)例分析20這3個(gè)作業(yè)的6種可能的調(diào)度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它們所相應(yīng)的完成時(shí)間和分別是19，18，20，21，19，19。最佳調(diào)度方案是1,3,2，其完成時(shí)間和為18。tji機(jī)器1機(jī)器2作業(yè)121作業(yè)231作業(yè)323三、算法描述21void

Flowshop::Backtrack(int

i){if

(i

>

n)

{for

(int

j

=

1;

j

<=

n;

j++)bestx[j]

=

x[j];bestf

=

f;}elsefor

(int

j

=

i;

j

<=

n;

j++)

{f1+=M[x[j]][1];f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2];f+=f2[i];if

(f

<

bestf)

{Swap(x[i],

x[j]);Backtrack(i+1);Swap(x[i],

x[j]);}f1-

=M[x[j]][1];f-

=f2[i];}}解空間：排列樹復(fù)雜性：T(n)=O(n!)5.4符號三角形問題22一、問題描述二、問題分析三、算法描述一、問題描述23右圖是由14個(gè)“+”和14個(gè)“-”組成的符號三角形。

2個(gè)同號下面都是“+”，2個(gè)異號下面都是“-”。++-+-+--++-++---++在一般情況下，符號三角形的第一行有n個(gè)符號。符號三角形問題要求對于給定的n，計(jì)算有多少個(gè)不同的符號三角形，使其所--++-++---含的“+”和“-”的個(gè)數(shù)相同。二、問題分析24解向量：用n元組x[1:n]表示符號三角形的第一行?？尚行约s束函數(shù)：當(dāng)前符號三角形所包含的“+”個(gè)數(shù)與“-”個(gè)數(shù)均不超過n*(n+1)/4無解的判斷：n*(n+1)/2為奇數(shù)復(fù)雜度分析：計(jì)算可行性約束需要O(n)時(shí)間，在最壞情況下有O(2n)個(gè)結(jié)點(diǎn)需要計(jì)算可行性約束，故解符號三角形問題的回溯算法所需的計(jì)算時(shí)間為

O(n2n)。三、算法描述voidTriangle::Backtrack(int

t){if

((count>half)||(t*(t-1)/2-count>half))

return;if

(t>n)

sum++;elsefor

(int

i=0;i<2;i++)

{p[1][t]=i;count+=i;for

(int

j=2;j<=t;j++)

{p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];count+=p[j][t-j+1];}Backtrack(t+1);for

(int

j=2;j<=t;j++)count-=p[j][t-j+1];count-=i;}}255.5

n后問題26一、問題描述二、問題分析三、算法描述一、問題描述在n×n格的棋盤上放置彼此不受攻擊的n個(gè)皇

后。按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問題等價(jià)于在n×n格的棋盤上放置n個(gè)皇后，任何2個(gè)皇后不放在同

一行或同一列或同一斜線上。1234567827QQQQQQQQ1

2

3

4

5

6

7

8二、問題分析28解向量：(x1,x2,…,xn)顯約束：xi=1,2,…,n隱約束：不同列：xi≠xj不處于同一正、反對角線：|i-j|≠|(zhì)xi-xj|三、算法描述29bool

Queen::Place(int

k){for

(int

j=1;j<k;j++)if

((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))

return

freturn

true;}void

Queen::Backtrack(int

t){if

(t>n)

sum++;elsefor

(int

i=1;i<=n;i++)

{x[t]=i;if

(Place(t))

Backtrack(t+1);}}5.6

0-1背包問題解空間：子集樹可行性約束函數(shù)：∑w

x

≤Ci

i上界函數(shù)：Bound()算法：略template<class

Typew,

class

Typep>Typep

Knap<Typew,

Typep>::Bound(int

i){//計(jì)算上界Typew

cleft=c-cw;//剩余容量Typep

b=cp;//以物品單位重量價(jià)值遞減序裝入物品while(i<=n

&&

w[i]<=cleft){cleft

-=

w[i];b

+=

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

(i

<=

n)

b

+=

p[i]/w[i]

*

cleft;return

b;}305.7最大團(tuán)問題31一、基本概念二、問題分析三、算法描述四、進(jìn)一步改進(jìn)一、基本概念完全子圖：給定無向圖G=(V，E)。如果U V，且對任意u，v U有(u，v) E，則稱U是G的完全子圖。團(tuán)：G的完全子圖U是G的團(tuán)當(dāng)且僅當(dāng)U不包含在G的更大的完全子圖中。G的最大團(tuán)：是指G中所含頂點(diǎn)數(shù)最多的團(tuán)。獨(dú)立集：G的空子圖U是G的獨(dú)立集當(dāng)且僅當(dāng)U不包G的最大獨(dú)立集：是G中所含頂點(diǎn)數(shù)最多的獨(dú)立集。補(bǔ)圖：對于任一無向圖G=(V，E)其補(bǔ)圖G=(V1，E1)定義為：V1=V，且(u，v) E1當(dāng)且僅當(dāng)(u，v) E。U是G的最大團(tuán)當(dāng)且僅當(dāng)U是G的最大獨(dú)立集。則稱U是G的空子圖。3含4在G的更5大的空子圖中。1

2

1

2空子圖：如果U V且對任意u，v U有(u，v)

E，34

532二、問題分析33解空間：子集樹可行性約束函數(shù)：頂點(diǎn)i到已選入的頂點(diǎn)集中每一個(gè)頂點(diǎn)都有邊相連。上界函數(shù)：有足夠多的可選擇頂點(diǎn)使得算法有可能在右子樹中找到更大的團(tuán)。復(fù)雜度分析：最大團(tuán)問題的回溯算法backtrack所需的計(jì)算時(shí)間顯然為O(n2n)。三、算法描述void

Clique::Backtrack(int

i)//計(jì)算最大團(tuán){if(i>n){//到達(dá)葉結(jié)點(diǎn)for

(int

j

=

1;

j

<=

n;

j++)

bestx[j]

=

x[j];bestn

=

cn;

return;}int

OK=1;//檢查頂點(diǎn)i與當(dāng)前團(tuán)的連接for

(int

j=1;j<i;j++)if

(x[j]

&&

a[i][j]

==

0)

{//i與j不相連OK=0;break;}if

(OK){//進(jìn)入左子樹x[i]=1;cn++;Backtrack(i+1);x[i]=0;cn--;}if

(cn+n-i>bestn){//進(jìn)入右子樹x[i]=0;Backtrack(i+1);}}34四、進(jìn)一步改進(jìn)35選擇合適的搜索順序，可以使得上界函數(shù)更有效的發(fā)揮作用。例如在搜索之前可以將頂點(diǎn)按度從小到大排序。這在某種意義上相當(dāng)于給回溯法加入了啟發(fā)性。定義Si={vi,vi+1,...,vn}，依次求出Sn,Sn-1,..解。從而得到一個(gè)更精確的上界函數(shù)，若

cn+Si<=max則剪枝。同時(shí)注意到：從Si+1到Si，如果找到一個(gè)更大的團(tuán)，那么vi必然屬于找到的團(tuán)，此時(shí)有Si=Si+1+1，否則Si=Si+1。因此只要max的值被更新過，就可以確定已經(jīng)找到最大值，不必再往下搜索了。5.8圖的m著色問題36一、基本概念二、問題分析三、算法描述四、復(fù)雜性分析一、基本概念37給定無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點(diǎn)著色，每個(gè)頂點(diǎn)著一種顏色。是否有一種著色法使G中每條邊的2個(gè)頂點(diǎn)著不同顏色。這個(gè)問題是圖的m可著色判定問題。若一個(gè)圖最少需要m種顏色才能使圖中每條邊連接的2個(gè)頂點(diǎn)著不同顏色，則稱這個(gè)數(shù)m為該圖的色數(shù)。求一個(gè)圖的色數(shù)m的問題稱為圖的m可著色優(yōu)化問題。二、問題分析解向量：(x1,x2,…,xn)表示頂點(diǎn)i所著顏色

x[i]可行性約束函數(shù)：頂點(diǎn)i與已著色的相鄰頂點(diǎn)顏色不重復(fù)。38三、算法描述39void

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);}}bool

Color::Ok(int

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

for

(int

j=1;j<=n;j++)if

((a[k][j]==1)&&(x[j]==x[k]))

return

false;return

true;}四、復(fù)雜性分析40圖m可著色問題的解空間樹中內(nèi)結(jié)點(diǎn)個(gè)數(shù)是∑mi(0≤i≤n-1)。對于每一個(gè)內(nèi)結(jié)點(diǎn)，在最壞情況下，用ok檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個(gè)兒子所相應(yīng)的顏色可用性需耗時(shí)O(mn)。因此，回溯法總的時(shí)間耗費(fèi)是∑mi(mn)=nm(mn-1)/(m-1)=O(nmn)(0≤i≤n-1)5.9旅行售貨員問題41void

Backtrack(int

i){

if

(i

==

n)

{if

(a[x[n-1]][x[n]]

!=

NoEdge

&&a[x[n]][1]

!=

NoEdge

&&

(cc

+

a[x[n-1]][x[n]]

+

a[x[n]][1]

<

bestc

||

bestc

==NoEdge))

{for

(int

j

=

1;

j

<=

n;

j++)

bestx[j]

=

x[j];bestc

=

cc

+

a[x[n-1]][x[n]]

+

a[x[n]][1];}}else{//是否可進(jìn)入x[j]子樹?for

(int

j=i;j<=n;j++)//搜索子樹

if

(a[x[i-1]][x[j]]!=NoEdge

&&(cc+a[x[i-1]][x[i]]<bestc

||

bestc==

NoEdge)){Swap(x[i],

x[j]);cc

+=

a[x[i-1]][x[i]];Backtrack(i+1);cc

-=

a[x[i-1]][x[i]];Swap(x[i],

x[j]);}}}解空間：排列樹復(fù)雜度分析：算法backtrack在最壞情況下可能需要更新當(dāng)前最優(yōu)解O((n-1)!)次，每次更新bestx需計(jì)算時(shí)間O(n)，從而整個(gè)算法的計(jì)算時(shí)間復(fù)雜性為O(n!)。5.10圓排列問題42一、問題描述二、算法描述三、算法改進(jìn)一、問題描述

給定n個(gè)大小不等的圓c1,c2,…,cn，現(xiàn)要將這n個(gè)圓排進(jìn)一個(gè)矩形框中，且要求各圓與矩形框的底邊相切。圓排列問題要求從n個(gè)圓的所有排列中找出有最小長度的圓排列。

例如，當(dāng)n=3，且所給的3個(gè)圓的半徑分別為1，1，2時(shí)，這3個(gè)圓的最小長度的圓排列如圖所示。其最小長度為2+4√2。43二、算法描述44{if

(t>n)

Compute();elsefor

(int

j

=

t;

j

<=

n;

j++)

{Swap(r[t],

r[j]);{//下界約束x[t]=centerx;Backtrack(t+1);}Swap(r[t],r[j]);}}void

Circle::Backtrack(int

t)float

Circle::Center(int

t){//計(jì)算當(dāng)前所選擇圓的圓心橫坐標(biāo)float

temp=0;for

(int

j=1;j<t;j++)

{floatvaluex=x[j]+2.0*sqrt(r[t]*r[j])if

(valuex>temp)

temp=valuex;}return

temp;float

centerx=Center(t);}if

(centerx+r[t]+r[1]<minvo)id

Circle::Compute(void){//計(jì)算當(dāng)前圓排列的長度float

low=0,high=0;for

(int

i=1;i<=n;i++)

{if

(x[i]-r[i]<low)

low=x[i]-r[iif

(x[i]+r[i]>high)

high=x[i]+r}if

(high-low<min)

min=high-low;}三、算法改進(jìn)45上述算法尚有許多改進(jìn)的余地。例如，象

1,2,…,n-1,n和n,n-1,…,2,1這種互為鏡像的列具有相同的圓排列長度，只計(jì)算一個(gè)就夠

了，可減少約一半的計(jì)算量。另一方面，如果所給的n個(gè)圓中有k個(gè)圓有相同的半徑，則這k個(gè)圓產(chǎn)生的k!個(gè)完全相同的圓排列，只計(jì)算一個(gè)就夠了。5.11電路板排列問題46一、問題描述二、算法設(shè)計(jì)三、算法描述四、復(fù)雜性分析一、問題描述47設(shè)B={1,2,…,n}是n塊電路板的集合。集合L={N1,N2,…,Nm}是這n塊電路板的m個(gè)連接塊。其中每個(gè)連接塊Ni是B的一個(gè)子集，且Ni中的電路板用一根導(dǎo)線連接在一起。不同的連接快可能包含相同的電路板。設(shè)x是n塊電路板的一個(gè)排列，則電路板的排列密度Density(x)定義為跨越相鄰電路板插槽的最大連線數(shù)。電路板排列問題要求度與給定的電路板連接條件(連接塊)，確定電路板的最佳排列，使其具有最小密度。二、算法設(shè)計(jì)48問題空間：排列樹三、算法描述49P152-154四、復(fù)雜性分析50每個(gè)結(jié)點(diǎn)處Backtrack函數(shù)的計(jì)算時(shí)間：O(m)結(jié)點(diǎn)數(shù)：O(n!)總的計(jì)算時(shí)間：O(mn!)5.12連續(xù)郵資問題51本節(jié)要點(diǎn)回顧回溯法的基本思想連續(xù)郵資問題描述問題分析算法設(shè)計(jì)一、回溯法的基本思想521、確定問題的解空間子集樹問題：裝載問題、符號三角形問題、0-1背包問題最大團(tuán)問題排列樹問題：批處理作業(yè)調(diào)度、n后問題、旅行售貨員問題、圓排列問題、電路板排列問題其他：圖的m著色問題2、找出適當(dāng)?shù)募糁瘮?shù)約束函數(shù)限界函數(shù)3、以深度優(yōu)先的方式搜索解空間遞歸回溯迭代回溯二、問題描述53假設(shè)國家發(fā)行了n種不同面值的郵票，并且規(guī)定每張信封上最多只允許貼m張郵票。連續(xù)郵資問題要求

對于給定的n和m的值，給出郵票面值的最佳設(shè)計(jì)，在1張信封上可貼出從郵資1開始，增量為1的最大連續(xù)郵資區(qū)間。(NOIP99)例如，當(dāng)n=2、m=3時(shí)，如果面值分別為1、4，則在

l-6之間的每一個(gè)郵資值都能得到(當(dāng)然還有8、9和12如果面值分別為1、3，則在1-7之間的每一個(gè)郵資值都能得到。可以驗(yàn)證當(dāng)n=2、m=3時(shí)，7就是可以得到連續(xù)的郵資最大值，面值為l、3。又如，當(dāng)n=5和m=4時(shí)，面值為(1,3,11,15,32)的5種郵票可以貼出郵資的最大連續(xù)郵資區(qū)間是1到70。三、問題分析54基本思路：搜索所有可行解，找出最大連續(xù)郵資區(qū)間的方案

解向量：用n元組x[1:n]表示n種不同的郵票面值，并約定它們從小到大排列。x[1]=1是唯一的選擇。

可行性約束函數(shù)：已選定x[1:i-1]，最大連續(xù)郵資區(qū)間是1—接下來x[i]的可取值范圍是x[i-1]+1—r+1。

如何確定r的值：計(jì)算X[1:i]的最大連續(xù)郵資區(qū)間在本算法中被頻繁使用到，因此勢必要找到一個(gè)高效的方法?？紤]到直接遞歸的求解復(fù)雜度太高，我們不妨嘗試計(jì)算用不超過m張

面值為x[1:i]的郵票貼出郵資k所需的最少郵票數(shù)y[k]。通過

y[k]可以很快推出r的值。事實(shí)上，y[k]可以通過遞推在O(n)時(shí)間內(nèi)解決：for

(int

j=0;

j<=

x[i-2]*(m-1);j++)if

(y[j]<m)for

(int

k=1;k<=m-y[j];k++)if

(y[j]+k<y[j+x[i-1]*k])

y[j+x[i-1]*k]=y[j]+k;while

(y[r]<maxint)

r++;四、算法設(shè)計(jì)55P155-1565.13回溯法的效率分析56本節(jié)要點(diǎn)：一、影響回溯算法效率的因素二、重排原理三、回溯法的效率四、概率方法一、影響回溯算法效率的因素57通過前面具體實(shí)例的討論容易看出，回溯算法的效率在很大程度上依賴于以下因素：(