《算法設計與分析基礎》（Python語言描述） 課件 第5章回溯法1

第5章走不下去就回退—回溯法5.1回溯法概述5.3基于子集樹框架的問題求解CONTENTS提綱5.4基于排列樹框架的問題求解5.2深度優(yōu)先搜索1/1265.1.1問題的解空間5.1回溯法概述求所有解類型：給定一個約束函數(shù)，需要求所有滿足約束條件的解。求最優(yōu)解類型：除了約束條件外還包含目標函數(shù)，最后是求使目標函數(shù)最大或者最小的最優(yōu)解。問題類型2/126一個復雜問題的解決方案往往是由若干個小的決策（即選擇）步驟組成的決策序列。問題的解可以表示成解向量x=（x0，x1，…，xn-1），其中分量xi對應第i步的選擇，xi∈Si（0≤i≤n-1）。x中各個分量xi所有的取值的組合構成問題的解向量空間，簡稱為解空間，解空間一般用樹形式來組織，也稱為解空間樹或者狀態(tài)空間樹。3/126解空間的一般結(jié)構x0=v01A1結(jié)點B0結(jié)點A0x1=v1,0x0=v0,ax0=v0,0x0∈S0……………x1∈S1…葉子結(jié)點根結(jié)點x1=v1,bxn-1∈Sn-1高度為n+1包含問題的解4/12601234(a)一個連通圖x3=4x2=2x2=4x1=1012344(b)解空間x1=3i=1(根結(jié)點)i=2i=3i=4(葉子結(jié)點)例如，對于如圖5.1(a)所示的連通圖，現(xiàn)在要求從頂點0到頂點4的所有路徑（默認為簡單路徑），這是一個求所有解問題。5/126

【例】農(nóng)夫（人）過河問題是這樣的，在河東岸有一個農(nóng)夫、一只狼、一只雞和一袋谷子，只有當農(nóng)夫在現(xiàn)場時，狼不會吃雞，雞也不會吃谷子，否則會出現(xiàn)狼吃雞或者雞吃谷子的沖突。另有一條小船，該船只能由農(nóng)夫操作，且最多只能載下農(nóng)夫和另一樣東西。

設計一種將農(nóng)夫、狼、雞和谷子借助小船運到河西岸的過河方案。6/126解③④⑤⑥⑦②①人、狼、雞、谷雞、谷

人、狼狼、谷人、雞狼、雞

人、谷人、狼、谷雞谷人、狼、雞狼人、雞、谷人、雞、谷狼人、狼、谷

雞雞人、狼、谷人、雞狼、谷人、狼、雞、谷人、狼、雞谷…………從東岸到西岸從西岸到東岸從東岸到西岸從西岸到東岸從東岸到西岸從東岸到西岸從西岸到東岸東岸西岸7/126回溯法是在解空間樹中按照深度優(yōu)先搜索方法從根結(jié)點出發(fā)搜索解。x0=a0xn-1=an-1葉子結(jié)點根結(jié)點高度為n+1x1=a15.1.2什么是回溯法8/126幾個概念活結(jié)點：指自身已生成但其孩子結(jié)點沒有全部生成的結(jié)點。擴展結(jié)點：指正在產(chǎn)生孩子結(jié)點的結(jié)點。死結(jié)點：指其所有子結(jié)點均已產(chǎn)生的結(jié)點，此時應往回移動（回溯）至最近的一個活結(jié)點處?；厮葸^程×s1si…si+1回溯再找其他路徑9/126回溯算法設計關鍵點根據(jù)問題的特性確定結(jié)點是如何擴展的，不同的問題擴展方式是不同的。例如，在有向圖中搜索從頂點s到頂點t的一條路徑，其擴展十分簡單，就是從一個頂點找所有相鄰頂點。在解空間中按什么方式搜索解，實際上樹的遍歷主要有先根遍歷和層次遍歷，前者就是深度優(yōu)先搜索（DFS），后者就是廣度優(yōu)先搜索（BFS）。回溯法就是采用深度優(yōu)先搜索解，下一章介紹的分支限界法則是采用廣度優(yōu)先搜索解。解空間通常十分龐大，如何高效地找到問題的解，通常采用一些剪支的方法實現(xiàn)?；厮莘?DFS+剪支10/126剪支：在解空間中搜索時提早終止某些分支的無效搜索，減少搜索的結(jié)點個數(shù)但不影響最終結(jié)果，從而提高了算法的時間性能。剪支策略可行性剪支：在擴展結(jié)點處剪去不滿足約束條件的分支。例如，在雞兔同籠問題中，若a=3，b=8為例，兔數(shù)的取值范圍只能是0～2，因為3只或者更多只兔子時腿數(shù)就超過8了，不再滿足約束條件。最優(yōu)性剪支：用限界函數(shù)剪去得不到最優(yōu)解的分支。例如，在雞兔同籠問題中求雞最少的解，若已經(jīng)求出一個可行解的雞數(shù)為3，后面就不必搜索雞數(shù)大于3的結(jié)點。交換搜索順序：在搜索中改變搜索的順序，比如原先是遞減順序，可以改為遞增順序，或者原先是無序，可以改為有序，這樣可能減少搜索的總結(jié)點。11/126針對給定的問題確定其解空間，其中一定包含問題的解。確定結(jié)點的擴展規(guī)則。采用深度優(yōu)先搜索方法搜索解空間，并在搜索過程中盡可能采用剪支函數(shù)避免無效搜索。回溯法求解的一般步驟12/1265.1.4回溯法算法時間分析解空間樹共有n+1層（根結(jié)點為第0層，葉子結(jié)點為第n層）。第1層有m0個結(jié)點，每個結(jié)點有m1個子結(jié)點。第2層有m0m1個結(jié)點，同理，第3層有m0m1m2個結(jié)點，依此類推，第n層有m0m1…mn-1個結(jié)點。則采用回溯法求所有解的算法的執(zhí)行時間為

T(n)=m0+m0m1+m0m1m2+…+m0m1m2…mn-1。例如，在子集樹中有m0=m1=…=mn-1=c，對應算法的時間復雜度為O(cn)，在排列樹中有m0=n，m1=n-1，…，mn-1=1，對應算法的時間復雜度為O(n!)。13/1265.2深度優(yōu)先搜索深度優(yōu)先搜索是在訪問一個頂點v之后盡可能先對縱深方向進行搜索。在解空間中搜索時類似樹的先根遍歷方式。14/1265.2.1圖的深度優(yōu)先遍歷圖遍歷是從圖中某個起始點出發(fā)訪問圖中所有頂點并且每個頂點僅訪問一次的過程，其頂點訪問序列稱為圖遍歷序列。采用深度優(yōu)先搜索方法遍歷圖稱為圖的深度優(yōu)先遍歷，得到遍歷序列稱為深度優(yōu)先遍歷序列，其過程是從起始點v出發(fā)，以縱向方式一步一步沿著邊訪問各個頂點。15/126從頂點v出發(fā)求深度優(yōu)先遍歷序列ans的算法如下：1 defDFS1(adj,v): #深度優(yōu)先遍歷3 ans.append(v) #訪問頂點v4 visited[v]=15 foruinadj[v]:#找到v的相鄰點u6 ifvisited[u]==0: #若頂點u尚未訪問7 DFS1(adj,u) #從u出發(fā)繼續(xù)搜索89 defDFS(adj,v):11 ans=[] #存放一個DFS序列12 visited=[0]*len(adj)#初始化所有元素為013 DFS1(adj,v)14 returnans16/1265.2.2深度優(yōu)先遍歷和回溯法的差別【例5-1】對于圖(a)的連通圖，求從頂點0到頂點4的所有路徑。0123417/126解01234采用深度優(yōu)先遍歷求u到v的所有路徑時是從頂點u出發(fā)以縱向方式進行頂點搜索，用x存放一條路徑，用ans存放所有的路徑。如果當前訪問的頂點u=v時，將找到的一條路徑x添加到ans中，同時從頂點u回退以便找其他路徑，否則找到u的所有相鄰點w，若頂點w尚未訪問則從w出發(fā)繼續(xù)搜索路徑。當u出發(fā)的所有路徑搜索完畢，再從u回退。18/1261 importcopy2 defdfs11(adj,u,v,x): #深度優(yōu)先搜索4 x.append(u) #訪問頂點u5 visited[u]=16 ifu==v: #找到一條路徑7 ans.append(copy.deepcopy(x)) #將路徑x的拷貝添加到ans中8 visited[u]=0 #置u可以重新訪問9 x.pop() #路徑回退10 return11 forwinadj[u]: #找到u的相鄰點w12 ifvisited[w]==0: #若頂點w尚未訪問13 dfs11(adj,w,v,x) #從w出發(fā)繼續(xù)搜索14 visited[u]=0 #u出發(fā)的所有路徑找完后回退15 x.pop() #路徑回退基于深度優(yōu)先遍歷求解算法19/12617 defdfs1(adj,u,v): #求u到v的所有路徑18 globalvisited,ans19 ans=[]20 visited=[0]*len(adj) #初始化所有元素為021 x=[]22 dfs11(adj,u,v,x)23 returnans20/1261 defdfs21(adj,u,v,x): #回溯法3 ifu==v: #找到一條路徑4 ans.append(copy.deepcopy(x)) #將路徑x的拷貝添加到ans中5 else:6 forwinadj[u]: #找到u的相鄰點w7 ifvisited[w]==0: #若頂點w尚未訪問8 x.append(w)

#訪問v,將v添加到ans中9 visited[w]=110 dfs21(adj,w,v,x) #從w出發(fā)繼續(xù)搜索11 visited[w]=0 #從w回退到u12 x.pop()基于回溯法求解算法21/12614 defdfs2(adj,u,v): #求u到v的所有路徑15 globalvisited,ans16 ans=[] #存放所有路徑17 visited=[0]*len(adj) #初始化所有元素為018 x=[]19 x.append(u)

#起始點u添加中x中20 visited[u]=121 dfs21(adj,u,v,x)22 returnans22/126深度優(yōu)先遍歷主要考慮頂點u的前進和回退，不需要專門表示回退到哪個頂點?；厮莘ㄖ饕紤]頂點u擴展的子結(jié)點以及從子結(jié)點的回退，需要專門處理出發(fā)點u和子結(jié)點w之間的擴展和回退關系。盡管都是采用深度優(yōu)先搜索，但后者解決問題的思路更清晰，特別是對于復雜的問題求解要方便得多。x3=4x2=2x2=4x1=1012344x1=3i=1(根結(jié)點)i=2i=3i=4(葉子結(jié)點)23/1265.2.3實戰(zhàn)—二叉樹的所有路徑（LeetCode257★）問題描述：給定一棵含n（1≤n≤100）個結(jié)點的二叉樹的根結(jié)點

root，結(jié)點值在[-100，100]內(nèi)，設計一個算法按任意順序返回所有從根結(jié)點到葉子結(jié)點的路徑。

例如，對于如下圖的二叉樹，返回結(jié)果是{"1->2->5"，"1->3"}。

要求設計如下方法：

def

binaryTreePaths(self,

root)

->

List[str]:123524/126從根結(jié)點root出發(fā)搜索到每個葉子結(jié)點時構成一條路徑x，將其轉(zhuǎn)換為路徑字符串tmp后添加的ans中。由于是樹結(jié)構，不會重復訪問頂點，不必設置訪問標記數(shù)組。問題求解—深度優(yōu)先遍歷25/1261 class

Solution:2

def

binaryTreePaths(self,

root)

->

List[str]:3

if

root==None:return

[]4

self.ans=[]5

x=[]

#存放一條路徑6

self.dfs(root,x) #dfs求ans7

return

self.ans26/1269

def

dfs(self,root,x):

#深度優(yōu)先遍歷10

x.append(root.val)11

if

root.left==None

and

root.right==None:

#找到一路徑12

tmp=str(x[0])

#路徑轉(zhuǎn)換為字符串13

for

i

in

range(1,len(x)):14

tmp+="->"+str(x[i])15

self.ans.append(tmp)16

else:17

if

root.left!=None:18

self.dfs(root.left,x)19

if

root.right!=None:20

self.dfs(root.right,x)21

x.pop()

#從結(jié)點root回退123527/126將給定的一棵樹看成是解空間，存放一條路徑的x就是一個解向量。從根結(jié)點root出發(fā)搜索，當?shù)竭_一個葉子結(jié)點時構成一條路徑，將解向量x轉(zhuǎn)換為路徑字符串tmp后添加的ans中，否則，從root擴展出左右孩子結(jié)點，并從孩子結(jié)點回退的root。問題求解—回溯法28/1261 class

Solution:2

def

binaryTreePaths(self,root)

->

List[str]:3

if

root==None:return

[]4

self.ans=[]5

x=[]

#存放一條路徑6

x.append(root.val)7

self.dfs(root,x)

#dfs求ans8

return

self.ans29/12610

def

dfs(self,root,x):

#回溯算法11

if

root.left==None

and

root.right==None:

#找到一路徑12

tmp=str(x[0])

#路徑轉(zhuǎn)換為字符串13

for

i

in

range(1,len(x)):14

tmp+="->"+str(x[i])15

self.ans.append(tmp)16

else:17

if

root.left!=None:18

x.append(root.left.val)19

self.dfs(root.left,x)20

x.pop() #回溯21

if

root.right!=None:22

x.append(root.right.val)23

self.dfs(root.right,x)24

x.pop()

#回溯123530/1265.3.1子集樹算法框架概述解空間類型子集樹：所給的問題是從n個元素的集合S中找出滿足某種性質(zhì)的子集。例如在整數(shù)數(shù)組a中求和為目標值target的所有解，每個元素a[i]只有選擇和不選擇兩種方式。排列樹：所給的問題是確定n個元素滿足某種性質(zhì)的排列。例如求全排列問題的解空間就是典型的排列樹。5.3基于子集樹框架的問題求解31/126子集樹算法框架x=[0]*MAXN #x存放解向量，這里作為全局變量defdfs(i): #求解子集樹的遞歸框架 ifi>n: #搜索到葉子結(jié)點,輸出一個可行解

輸出一個解 else: forjinrange(下界,上界+1): #用j表示x[i]的所有可能候選值

x[i]=j

#產(chǎn)生一個可能的解分量

…

#其他操作 ifconstraint(i,j)andbound(i,j):

dfs(i+1) #滿足約束條件和限界函數(shù),繼續(xù)下一層

回溯x[i]

…

32/126問題描述：給定一個整數(shù)數(shù)組

nums，長度范圍是1～10，其中所有元素互不相同。求該數(shù)組所有可能的子集（冪集），結(jié)果中不能包含重復的子集，可以按任意順序返回冪集。

例如，nums=[1，2，3]，結(jié)果為[[]，[1]，[2]，[1，2]，[3]，[1，3]，[2，3]，[1，2，3]]。

要求設計如下成員方法：

def

subsets(self,

nums)

->

List[List[int]]5.3.2實戰(zhàn)—子集（LeetCode78★★）33/126解法1解向量為x，x[i]=1表示選取a[i]，x[i]=0表示不選取a[i]。01010101010101第0層第1層第2層第3層（葉子結(jié)點層）{1,2,3}{1,2}{1,3}{1}{2,3}{2}{3}{}34/1261 class

Solution:2

def

subsets(self,

nums)

->

List[List[int]]:3

self.ans,self.x=[],[]4

self.dfs(nums,0)5

return

self.ans35/1267

def

dfs(self,nums,i):

#回溯算法8

if

i==len(nums):

#到達一個葉子結(jié)點9

self.ans.append(copy.deepcopy(self.x))10

else:11

self.x.append(nums[i])

#選擇nums[i],

x中添加nums[i]12

self.dfs(nums,i+1)13

self.x.pop()

#回溯即刪除前面添加的nums[i]14

self.dfs(nums,i+1)

#不選擇nums[i],x中不添加nums[i]01010101010101第0層第1層第2層第3層（葉子結(jié)點層）{1,2,3}{1,2}{1,3}{1}{2,3}{2}{3}{}36/126解法2將x改為直接存放a的一個子集。設解向量x={x0，…，xi，…，xm-1}（m為x的長度，0≤m≤n）。x2=a[2]=3x1=3x1=a[1]=2x1=a[2]=3x0=a[0]=1x0=a[1]=2x0=a[2]=30,0,{}1,1,{1}2,2,{1,2}3,3,{1,2,3}2,3,{1,3}1,2,{2}1,3,{3}2,3,{2,3}i=0i=1i=2i=337/126每個結(jié)點的狀態(tài)為“i，j，x”，其中i為結(jié)點的層次，xi的取值范圍為a[j..n-1]，x為解向量。解空間中每個結(jié)點的x都是一個子集。0,0,{}x2=a[2]=3x1=3x1=a[1]=2x1=a[2]=3x0=a[0]=1x0=a[1]=2x0=a[2]=31,1,{1}2,2,{1,2}3,3,{1,2,3}2,3,{1,3}1,2,{2}1,3,{3}2,3,{2,3}i=0i=1i=2i=3ij38/1261 class

Solution:2

def

subsets(self,

nums)

->

List[List[int]]:3

self.ans,x=[],[]4

self.dfs(nums,x,0)5

return

self.ans39/1267

def

dfs(self,nums,x,i): #回溯算法8

self.ans.append(copy.deepcopy(x)) #找到一個解9

for

j

in

range(i,len(nums)):10

x.append(nums[j])11

self.dfs(nums,x,j+1)12

x.pop() #回溯即刪除前面添加的nums[j]40/126兩種解法的比較！41/126問題描述：給定n個整數(shù)數(shù)組nums，其中可能包含重復元素，請你返回該數(shù)組所有可能的子集（冪集）。解集不能包含重復的子集，返回的解集中子集可以按任意順序排列。

例如，nums={1，2，2}，結(jié)果為{{}，{1}，{1，2}，{1，2，2}，{2}，{2，2}}。

要求設計如下方法：

def

subsetsWithDup(self,

nums)

->

List[List[int]]:5.3.3實戰(zhàn)—子集Ⅱ（LeetCode90★★）42/126解法1由于這里nums中包含重復元素。如果直接采用5.3.2節(jié)的算法1會得到重復的子集。例如，nums[]={1，2，1}時，求解結(jié)果為{{1，2，1}，{1，2}，{1，1}，{1}，{2，1}，{2}，{1}，{}}，其中{1，2}和{2，1}重復，同時{1}出現(xiàn)兩次。兩個相同的{1}容易消除，但{1，2}和{2，1}如何消除呢？可以采用先將nums排序的方法，如nums[]={1，1，2}，其結(jié)果為{{1，1，2}，{1，1}，{1，2}，{1}，{1，2}，{1}，{2}，{}}，這樣重復的子集的順序均相同，剩下的問題是消除順序相同的重復子集。43/126采用5.3.2節(jié)求a的冪集的算法1的思路，利用集合set實現(xiàn)去重（其元素為由x轉(zhuǎn)換的元組）。1 class

Solution:2

def

subsetsWithDup(self,

nums)

->

List[List[int]]:3

nums.sort()

#nums遞增排序4

self.ans,self.x=set(),[]5

self.dfs(nums,0)6

return

list(self.ans)44/1268

def

dfs(self,nums,i):

#回溯算法9

if

i==len(nums):

#到達一個葉子結(jié)點10

self.ans.add(tuple(self.x))11

else:12

self.x.append(nums[i])

#選擇nums[i],

x中添加nums[i]13

self.dfs(nums,i+1)14

self.x.pop()

#回溯15

self.dfs(nums,i+1) #不選擇nums[i],x不加nums[i]上述程序提交時通過，執(zhí)行用時為44ms，內(nèi)存消耗為16.3MB。45/126解法2采用5.3.2節(jié)求a的冪集的算法2的思路更方便！46/126每個結(jié)點的狀態(tài)為“i，j，x”，其中i為結(jié)點的層次，xi的取值范圍為a[j..n-1]，x為解向量。解空間中每個結(jié)點的x都是一個子集。0,0,{}x2=a[2]=3x1=3x1=a[1]=2x1=a[2]=3x0=a[0]=1x0=a[1]=2x0=a[2]=31,1,{1}2,2,{1,2}3,3,{1,2,3}2,3,{1,3}1,2,{2}1,3,{3}2,3,{2,3}i=0i=1i=2i=3ij47/1261 class

Solution:2

def

subsetsWithDup(self,

nums)

->

List[List[int]]:3

nums.sort() #nums遞增排序4

self.ans,x=[],[]5

self.dfs(nums,x,0)6

return

self.ans48/1268

def

dfs(self,nums,x,i): #回溯算法9

self.ans.append(copy.deepcopy(x))10

for

j

in

range(i,len(nums)):11

if

j>i

and

nums[j]==nums[j-1]:continue13

x.append(nums[j])14

self.dfs(nums,x,j+1)15

x.pop()0,0,{}x0=a[0]=1x0=a[1]=1x0=a[2]=21,1,{1}1,2,{1}1,3,{3}i=0i=1ij………49/126上述程序提交時通過，執(zhí)行用時為36ms，內(nèi)存消耗為15.2MB。50/126解法2的時空性能更好，為什么？問題描述：給定n個整數(shù)的數(shù)組nums和一個整數(shù)target。向數(shù)組中的每個整數(shù)前添加'+'或'-'

，然后串聯(lián)起所有整數(shù)，可以構造一個表達式，例如，nums={2，1}，可以在2之前添加'+'，在1之前添加'-'，然后串聯(lián)起來得到表達式

“+2-1”。

設計一個算法求可以通過上述方法構造的運算結(jié)果等于target的不同表達式的數(shù)目。

要求設計如下方法：

def

findTargetSumWays(self,

nums,

target)

->

int:5.3.4實戰(zhàn)—目標和（LeetCode494★★）51/126解用ans表示滿足要求的解個數(shù)（初始為0），設置解向量x=（x0，x1，…，xn-1），xi表示nums[i]（0≤i≤n-1）前面添加的符號，xi只能在'+'和'-'符號在二選一，所以該問題的解空間為子集樹。用expv表示當前運算結(jié)果（初始為0）。對于解空間中第i層的結(jié)點A，若xi選擇'+'，則expv+=nums[i]；若xi選擇'-'，則expv-=nums[i]，在回退到A時要恢復expv。x[0]nums[0]x[1]nums[1]…

x[n-1]nums[n-1]52/126找到一個解，置ans+=1。由于該問題只需要求最后的解個數(shù)，所以不必真正設計解向量x，僅僅設計expv即可。53/1261 class

Solution:2

def

findTargetSumWays(self,

nums,

target)

->

int:3

self.ans=04

self.dfs(nums,target,0,0)5

return

self.ansdfs(nums,target,i,expv)54/1267

def

dfs(self,nums,target,i,expv):

#回溯算法8

if

i==len(nums):

#到達一個葉子結(jié)點9

if

expv==target:self.ans+=1

#找到一個解10

else:11

expv+=nums[i]

#nums[i]前選擇'+'12

self.dfs(nums,target,i+1,expv)13

expv-=nums[i]

#回溯：恢復expv14

expv-=nums[i]

#nums[i]前選擇'-'15

self.dfs(nums,target,i+1,expv)16

expv+=nums[i]

#回溯：恢復expv55/126說明：上述程序提交時出現(xiàn)超時現(xiàn)象，但同樣的思路采用C/C++或者Java編程時提交通過。56/126給定n個不同的正整數(shù)集合a=（a0，a1，…，an-1）和一個正整數(shù)t，要求找出a的子集s，使該子集中所有元素的和為t。例如，當n=4時，a=（3，1，5，2），t=8，則滿足要求的子集s為（3，5）和（1，5，2）。5.3.5子集和問題57/126解與求冪集問題一樣，該問題的解空間是一棵子集樹（因為每個整數(shù)要么選擇要么不選擇）。求滿足約束函數(shù)的所有解。58/1261）無剪支a=（3，1，5，2），t=8010100101010101010101010101011086631117552000011996444108853333結(jié)點層次i=0i=1i=2i=3i=4sum=3159/1261 cnt=0 #累計解個數(shù)2 sum=0 #累計搜索的結(jié)點個數(shù)3 defdisp(a): #輸出一個解4 globalcnt,x5 cnt+=1;print("第%d個解,"%(cnt),end='')6 print("選取的數(shù)為:",end='')7 foriinrange(0,len(x)):8 ifx[i]==1:print(a[i],end='')9 print()60/12611 defdfs1(a,t,cs,i): #回溯算法12 globalsum,x13 sum+=114 ifi>=len(a):

#到達一個葉子結(jié)點15 ifcs==t:disp(a) #找到一個滿足條件的解,輸出16 else: #沒有到達葉子結(jié)點17 x[i]=1 #選取整數(shù)a[i]18 dfs1(a,t,cs+a[i],i+1)19 x[i]=0 #不選取整數(shù)a[i]20 dfs1(a,t,cs,i+1)61/12622 defsubs1(a,t): #求解子集和問題23 globalx24 x=[0]*len(a) #解向量25 print("求解結(jié)果")26 dfs1(a,t,0,0) #i從0開始27 print("sum=",sum)62/1262）左剪支當搜索到第i（0≤i<n）層結(jié)點時，cs表示當前已經(jīng)選取的整數(shù)和（其中不包含a[i]），判斷選擇a[i]是否合適：若cs+a[i]>t，不必繼續(xù)該路徑，終止搜索，也就是左剪支。若cs+a[i]≤t，沿著該路徑繼續(xù)下去可能會找到解，不能終止。簡單地說，僅僅擴展?jié)M足cs+a[i]≤t的左孩子結(jié)點。a=（3，1，5，2），t=80101001010101010101010101011086631117552000096444108853333結(jié)點層次i=0i=1i=2i=3i=4cs=4sum=2763/1261 defdfs2(a,t,cs,i): #回溯算法2 globalsum,x3 sum+=14 ifi>=len(a):

#到達一個葉子結(jié)點5 ifcs==t:disp(a) #找到一個滿足條件的解,輸出6 else: #沒有到達葉子結(jié)點7 ifcs+a[i]<=t: #左孩子結(jié)點剪支8 x[i]=1 #選取整數(shù)a[i]9 dfs2(a,t,cs+a[i],i+1)10x[i]=0 #不選取整數(shù)a[i]11dfs2(a,t,cs,i+1)64/1263）右剪支考慮是否擴展右孩子結(jié)點。當搜索到第i（0≤i<n）層的某個結(jié)點時，用rs表示余下的整數(shù)和，即rs=a[i]+…+a[n-1]（包含a[i]）。如果不選擇a[i]，此時剩余的所有整數(shù)和為rs=rs-a[i]，若cs+rs<t成立，說明即便選擇所有剩余整數(shù)其和都不可能達到t。右剪支就是僅僅擴展?jié)M足cs+rs≥t的右孩子結(jié)點。a=（3，1，5，2），t=801010010101010110,118,06,06,21,21,70,70,89,24,24,710,08,08,23,23,73,8rs=8,rs=rs-1=70+rs=7<tsum=1065/1261 defdfs3(a,t,cs,rs,i): #回溯算法2 globalsum,x3 sum+=14 ifi>=len(a): #到達一個葉子結(jié)點5 ifcs==t:disp(a) #找到一個解,輸出6 else: #沒有到達葉子結(jié)點7 rs-=a[i] #求剩余的整數(shù)和8 ifcs+a[i]<=t: #左孩子結(jié)點剪支9 x[i]=1 #選取整數(shù)a[i]10 dfs3(a,t,cs+a[i],rs,i+1)11 ifcs+rs>=t: #右孩子結(jié)點剪支12 x[i]=0 #不選取整數(shù)a[i]13 dfs3(a,t,cs,rs,i+1)14 rs+=a[i] #恢復剩余整數(shù)和(回溯)66/12616 defsubs3(a,t): #求解子集和問題17 globalx18 x=[0]*len(a) #解向量19 rs=020 foreina:rs+=e #或者rs=sum(a)21 print("求解結(jié)果")22 dfs3(a,t,0,rs,0) #i從0開始23 print("sum=",sum)67/126盡管通過剪支提高了算法的性能，但究竟剪去了多少結(jié)點與具體的實例數(shù)據(jù)相關。上述算法最壞情況下算法的時間復雜度仍然為O(n×2n)。算法分析68/126有n個集裝箱要裝上一艘載重量為t的輪船，其中集裝箱i（0≤i≤n-1）的重量為wi。不考慮集裝箱的體積限制，現(xiàn)要選出重量和小于等于t并且盡可能重的若干集裝箱裝上輪船。例如，n=5，t=10，w={5，2，6，4，3}時，其最佳裝載方案有兩種即（1，1，0，0，1）和（0，0，1，1，0），對應集裝箱重量和達到最大值t。5.3.6簡單裝載問題69/126解與子集和問題類似。當搜索到第i（0≤i<n）層的結(jié)點時，cw表示當前選擇的集裝箱重量和，rw表示余下集裝箱的重量和，即 rw=w[i]+…+w[n-1]（含w[i]）此時處理集裝箱i，先從rw中減去w[i]即置rw-=w[i]。cw,rw第i層cw1,rw第i+1層rw=rw-w[i]70/126采用的剪支操作如下：左剪支：檢查當前集裝箱被選中后總重量是否超過t，若是則剪支，即僅僅擴展?jié)M足cw+w[i]≤t的左孩子結(jié)點。右剪支：如果不選擇集裝箱i，此時剩余的所有整數(shù)和為rw，若cw+rw≤bestw成立（bestw是當前找到的最優(yōu)解的重量和），說明即便選擇所有剩余集裝箱其重量和都不可能達到bestw，所有僅僅擴展?jié)M足cw+rw>bestw的右孩子結(jié)點。cw,rw第i層cw1,rw1第i+1層cw+w[i]≤t1cw,rw10cw+rw>bestw71/1262 defdfs(w,t,cw,rw,i): #回溯算法5 ifi>=len(w):

#到達一個葉子結(jié)點6 ifcw>bestw: #找到更優(yōu)解7 bestw=cw #保存更優(yōu)解8 bestx=copy.deepcopy(x) #深拷貝9 else: #尚未找完所有集裝箱10 rw-=w[i]

#求剩余集裝箱的重量和11 ifcw+w[i]<=t:

#左剪支12 x[i]=1 #選取集裝箱i13 cw+=w[i] #累計所選集裝箱的重量和14 dfs(w,t,cw,rw,i+1)15 cw-=w[i] #回溯cw16 ifcw+rw>bestw:

#右剪支17 x[i]=0 #不選擇集裝箱i18 dfs(w,t,cw,rw,i+1)19 rw+=w[i]

#回溯rw72/12621 defloading(w,t): #求解簡單裝載問題22 globalx,bestx,bestw,sum23 x=[0]*len(w) #解向量24 bestx=[0]*len(w) #存放最優(yōu)解向量25 bestw=0 #存放最優(yōu)解的總重量26 sum=0 #累計搜索的結(jié)點個數(shù)27 rw=028 foreinw:rw+=e29 dfs(w,t,0,rw,0)30 print("求解結(jié)果")31 foriinrange(0,len(w)): #輸出最優(yōu)解32 ifbestx[i]==1:print("選取第%d個集裝箱"%(i))33 print("總重量=",bestw)34 print("sum=",sum)73/126解空間樹中有2n+1-1個結(jié)點，葉子結(jié)點為2n個。每找到一個更優(yōu)解時需要將x復制到bestx（執(zhí)行時間為O(n)）。所以最壞情況下算法的時間復雜度為O(n×2n)。算法分析74/126有n個編號為0～n-1的物品，重量為w={w0，w1，…，wn-1}，價值為v={v0，v1，…，vn-1}，給定一個容量為W的背包。從這些物品中選取全部或者部分物品裝入該背包中，每個物品要么選中要么不選中，即物品不能被分割，找到選中物品不僅能夠放到背包中而且價值最大的方案（最大價值）。W=6結(jié)果為8物品編號重量w價值v0541342233115.2.30/1背包問題75/126解1）存儲結(jié)構設計1 classGoods: #物品類2 def__init__(self,x,y,z):3 self.no=x #物品的編號4 self.w=y #物品的重量5 self.v=z #物品的價值6 def__lt__(self,other): #用于按v/w遞減排序7 return1.0*self.v/self.w>=1.0*other.v/other.w物品編號重量w價值v054134223311g=[Goods(0,5,4),Goods(1,3,4),Goods(2,2,3),Goods(3,1,1)]76/126解向量x=（x0，x1，…，xn-1），xi=1表示選擇物品i，xi=0表示不選擇物品i。最優(yōu)解向量用bestx表示，最大價值用bestv表示（初始為0）。77/1262）左剪支左剪支與子集和問題的類似。當搜索到第i（0≤i<n）層的某個結(jié)點時，cw表示當前選擇的物品重量和（其中不包含w[i]）。檢查當前物品被選中后總重量是否超過W，若超過則剪支，即僅僅擴展?jié)M足cw+w[i]≤W的左孩子結(jié)點。選擇物品i第i層78/1263）右剪支采用限界函數(shù)（上界函數(shù)）。將所有物品g按單位重量價值遞減排序。例如前面表排序后的結(jié)果如下，序號i發(fā)生了改變，后面改為按i而不是物品編號no的順序搜索。序號i物品編號no重量w價值vv/w02231.511341.32311130540.879/126第i層結(jié)點出發(fā)的最大可能價值：cw表示當前選擇的物品重量和（不含w[i]），cv表示當前選擇的物品價值和（不含v[i]）。此時背包剩余容量為rw=W-cw，如果按背包容量連續(xù)選擇物品i及其后面的物品，直到裝滿，其價值一定是最大的（因為物品按v/w遞減排序），最大價值為r(i)：第i層第i+1層第k-1層第k層cv，cw試探：物品i～k-1可以整個裝入，物品k只能部分裝入80/126第i層結(jié)點：如果不選擇物品i時，此時背包剩余容量為rw=W-cw。余下重量的物品的最大價值r(i+1)：x[i]=0第i層第i+1層…第k-1層第k層cvr(i+1)81/1261 defbound(cw,cv,i): #計算第i層結(jié)點的上界函數(shù)值2 globalg,W,n3 rw=W-cw #背包的剩余容量4 b=cv #表示物品價值的上界值5 j=i6 whilej<nandg[j].w<=rw:7 rw-=g[j].w #選擇物品j8 b+=g[j].v #累計價值9 j+=110 ifj<n: #最后物品k=j+1只能部分裝入11 b+=1.0*g[j].v/g[j].w*rw12 returnb限界函數(shù)不選擇物品i時這條路徑走下去能夠選擇物品的最大價值為bound(cw,cv,i+1)。對于第i層結(jié)點實參為i+1剪支：僅僅擴展bound(cw,cv,i+1)>bestv的右孩子結(jié)點。82/126序號i物品編號no重量w價值vv/w02231.511341.32311130540.8右剪支實例0,06,85,72,36,8,65,7,7.811,122,3,6.40,0,6.6(cw,cv)(cw,cv,ub)bestv=8bound(cw,cv,i+1)≤bestv83/1261 defdfs(cw,cv,i): #回溯算法2 globalg,W,n,x,bestx,bestv,sum3 sum+=14 ifi>=n: #到達一個葉子結(jié)點5 ifcw<=Wandcv>bestv: #找到一個更優(yōu)解,保存它6 bestv=cv7 bestx=copy.deepcopy(x)8 else: #沒有到達葉子結(jié)點9 ifcw+g[i].w<=W:

#左剪支10 x[i]=1 #選取物品i11 dfs(cw+g[i].w,cv+g[i].v,i+1)12 b=bound(cw,cv,i+1) #計算限界函數(shù)值13 ifb>bestv:

#右剪支14 x[i]=0 #不選取物品i15 dfs(cw,cv,i+1)84/12617 defknap(g,W): #求0/1背包問題18 globaln,x,bestx,bestv,sum19 n=len(g) #物品個數(shù)20 x=[0]*n #解向量21 bestx=[0]*n #存放最優(yōu)解向量22 bestv=0 #存放最大價值,初始為023 sum=0 #累計搜索的結(jié)點個數(shù)24 print("求解結(jié)果")25 g.sort()26 dfs(0,0,0) #i從0開始27 foriinrange(0,n):28 ifbestx[i]==1:print("選取第%d個物品"%(g[i].no))29 print("總重量=%d,總價值=%d"%(W,bestv))30 print("sum=",sum)85/126【算法分析】上述算法在不考慮剪支時解空間樹中有2n+1-1個結(jié)點，求上界函數(shù)值和保存最優(yōu)解的時間為O(n)，所以最壞情況下算法的時間復雜度為O(n×2n)。程序驗證86/126有n種重量和價值分別為wi、vi（0≤i<n）的物品，從這些物品中挑選總重量不超過W的物品，每種物品可以挑選任意多件，求挑選物品的最大價值。該問題稱為完全背包問題。5.2.4完全背包問題87/126解

與0/1背包問題不同，完全背包問題中物品i指的是第i種物品，每種物品可以取任意多件。對于解空間中第i層的結(jié)點，用cw、cv表示選擇物品的總重量和總價值，這樣處理物品i的方式如下：不選擇物品i。當cw+w[i]≤W時，選擇物品i一件，下一步繼續(xù)選擇物品i。當cw+w[i]≤W時，選擇物品i一件，下一步開始選擇物品i+1。3種選擇88/126n=2，W=2，w=（1，2），v=（2，5），結(jié)點對應狀態(tài)是“(cw，cv，i)”，0,0,00,0,10,0,22,5,12,5,24,10,14,10,22,5,21,2,01,2,11,2,23,7,13,7,22,4,02,4,13,6,03,6,12,4,24,9,14,9,22,4,12,4,24,9,14,9,21,2,11,2,23,7,13,7,2不選擇物品i。選擇物品i一件，下一步繼續(xù)選擇物品i。選擇物品i一件，下一步開始選擇物品i+1。89/1261 defdfs(cw,cv,i): #回溯算法2 globalw,v,n,W,bestv3 ifi>=n:4 ifcw<=Wandcv>bestv: #找到一個更優(yōu)解5 bestv=cv6 else:7 dfs(cw,cv,i+1) #不選擇物品i8 ifcw+w[i]<=W:9 dfs(cw+w[i],cv+v[i],i) #剪支:選物品i,繼續(xù)選物品i10 ifcw+w[i]<=W:11 dfs(cw+w[i],cv+v[i],i+1) #剪支:選物品i,選下一件90/12613 defcompknap(w,v,n,W): #求解完全背包問題14 globalbestv15 bestv=0 #存放最大價值,初始為016 dfs(0,0,0)17 print("最大價值=",bestv)91/126程序驗證intn=2;intw[]={1,2};intv[]={2,5};intW=2;92/126問題描述：在n×n（1≤n≤9）的方格棋盤上放置n個皇后，并且每個皇后不同行、不同列、不同左右對角線（否則稱為有沖突）。如下圖所示是6皇后問題的一個解。

設計一個算法求n個皇后的解個數(shù)，例如n=6時6皇后問題有4個解，因此返回結(jié)果為4。214365654321要求設計如下方法：def

totalNQueens(self,

n:

int)

->

int:5.3.9實戰(zhàn)—皇后Ⅱ（LeetCode52★★★）93/126解解空間是一棵子集樹（每個皇后在1～n列中找到一個適合的列號，即n選一），并且要求所有解。用整數(shù)數(shù)組q[N]存放n皇后的解，因為每行只能放一個皇后，q[i]（1≤i≤n）的值表示第i個皇后所在的列號。q[1..6]={2，4，6，1，3，5}21436565432194/126若在(i，j)位置上放第i個的皇后，是否與已放好的i-1個皇后(k，q[k])有沖突呢？如果(i，j)位置與前面某個皇后同列，則有q[k]==j成立。如果(i，j)位置與前面某個皇后同對角線，則恰好構成一個等腰直角三角形，即有|q[k]-j|==|i-k|成立。歸納起來只要(i，j)位置滿足以下條件，則存在沖突，否則不沖突：(q[k]==j)||(abs(q[k]-j)==abs(i-k))

1≤k≤i-1沖突判斷q[k]-j(i，j)k-i(k，q[k])j-q[k]i-k(i，j)(k，q[k]（a）對角線1（b）對角線295/126求解皇后問題所有解的遞歸模型：queen(i，n)≡n個皇后放置完畢，輸出一個解

若i>nqueen(i，n)≡在第i行找到一個合適的位置(i，j)，

放置一個皇后; 其他 queen(i+1，n);96/1261 MAXN=20

#最多皇后個數(shù)2 q=[0]*MAXN

#q[i]存放第i個皇后的列號3 class

Solution:4

def

totalNQueens(self,

n:

int)

->

int:5

t=0

#累計解個數(shù)6

self.dfs(1,n)7

return

t97/1269

def

place(self,i,j):

#測試(i,j)位置能否放皇后10

if

i==1:

return

True

#第一個皇后總是可以放置11

k=112

while

k<i:

#k=1～i-1行已放置皇后13

if

q[k]==j

or

(abs(q[k]-j)==abs(i-k)):14

return

False15

k+=116

return

True沖突條件：

(q[k]==j)||(abs(q[k]-j)==abs(i-k))1≤k≤i-198/12618

def

dfs(self,i,n):

#回溯算法19

if

i>n:

#所有皇后放置結(jié)束20

t+=121

else:22

for

j

in

range(1,n+1):

#在第i行上試探每一個列j23

if

self.place(i,j):

#第i行找到合適位置(i,j)24

q[i]=j25

self.dfs(i+1,n)99/126每個皇后都要試探n列，共n個皇后，其解空間是一棵子集樹，每個結(jié)點可能有n棵子樹。每個皇后試探一個合適位置的時間為O(n)。所有算法的最壞時間復雜度為O(n×nn)。程序提交通過，執(zhí)行時間72ms，內(nèi)存消耗15MB。算法分析100/126問題描述：有n（n≥1）個任務需要分配給n個人執(zhí)行，每個任務只能分配給一個人，每個人只能執(zhí)行一個任務。第i個人執(zhí)行第j個任務的成本是c[i][j]（0≤i，j≤n-1）。求出總成本最小的一種分配方案。人員任務0任務1任務2任務309278164372581837694最小成本=135.3.10任務分配問題101/126解n個人和n個任務編號均用0～n-1表示。所謂一種分配方案就是由第i個人執(zhí)行第j個任務，每個人從n個任務中選擇一個任務，即n選一，所以本問題的解空間樹看成是一棵子集樹。求總成本最小解（最優(yōu)解是最小值），屬于求最優(yōu)解類型。用bestc表示最小成本，bestx為最優(yōu)分配方案。102/126used[j]=0xi=j表示人員i安排任務j第i層第i+1層第n層(葉子結(jié)點)…解空間中根結(jié)點層次i為0，當搜索到第i層每個結(jié)點時，表示為第i個人分配一個沒有分配的任務，即選擇滿足used[j]=0（0≤j≤n-1）的任務j。103/1263 defdfs1(cost,i): #回溯算法6 ifi>=n: #到達一個葉子結(jié)點7 ifcost<bestc: #比較求最優(yōu)解8 bestc=cost;bestx=copy.deepcopy(x)9 else:10 forjinrange(0,n): #為人員i試探任務j:0到n-111 ifused[j]:continue #跳過已經(jīng)分配的任務j12 used[j]=True13 x[i]=j #任務j分配給人員i14 cost+=c[i][j]15 dfs1(cost,i+1) #為人員i+1分配任務16 used[j]=False #回溯17 x[i]=-118 cost-=c[i][j]104/12620 defallocate1(c,n): #求解任務分配問題21 globalx,bestx,bestc,used,sum22 x=[0]*n23 bestx=[0]*n24 bestc=INF #初始化為∞25 used=[False]*n26 sum=027 dfs1(0,0) #從人員0開始28 print("求解結(jié)果")29 forkinrange(0,n):30 print("人員%d分配任務