《算法設(shè)計與分析基礎(chǔ)》（Python語言描述） 課件 第5章回溯法2

第5章走不下去就回退—回溯法5.1回溯法概述5.3基于子集樹框架的問題求解CONTENTS提綱5.4基于排列樹框架的問題求解5.2深度優(yōu)先搜索1/365.4.1排列樹算法框架概述當(dāng)求解問題是確定n個元素滿足某種條件的排列時，相應(yīng)的解空間樹稱為排列樹。解空間為排列樹的遞歸框架是以求全排列為基礎(chǔ)的。5.4基于排列樹框架的問題求解2/36

【例5-2】（LeetCode46★★）有一個含n個整數(shù)的數(shù)組a，所有元素均不相同，求其所有元素的全排列。

例如，a={1，2，3}，得到結(jié)果是（1，2，3）、（1，3，2）、（2，3，1）、（2，1，3）、（3，1，2）、（3，2，1）。3/36解用數(shù)組a存放初始數(shù)組a的一個排列。設(shè)f(a，n，i)表示求a[i..n-1]（共n-i個元素）的全排列，為大問題，f(a，n，i+1)表示求a[i+1..n-1]（共n-i-1個元素）的全排列，為小問題。ai：ai與ai交換，f(a，n，i+1)

以ai開頭的a[i..n-1]的全排列ai+1：ai與ai+1交換，f(a，n，i+1)

以ai+1開頭的a[i..n-1]的全排列…an-1：ai與an-1交換，f(a，n，i+1)

以an-1開頭的a[i..n-1]的全排列a0

a1

…

ai

f(a，n，i)：大問題f(a，n，i+1)：小問題ai+1

…

an-1ai位置取ai～an-1中每個元素，再組合f(a，n，i+1)得到f(a，n，i)4/36求a的全排列的遞歸模型f(a，n，i)f(a，n，i)

輸出產(chǎn)生的解

當(dāng)i=n-1時f(a，n，i)

對于j=i～n-1：

其他 a[i]與a[j]交換位置;

f(a，n，i+1);

將a[i]與a[j]交換位置（回溯）a0

a1

…

ai

f(a，n，i)：大問題f(a，n，i+1)：小問題ai+1

…

an-1ai位置取ai～an-1中每個元素，再組合f(a，n，i+1)得到f(a，n，i)5/36a[0]

a[2]a[1]

a[2]a[1]

a[2]a[1]

a[2]a={1,2,3}a={1,2,3}a={1,2,3}a={1,3,2}a[1]

a[1]輸出123輸出132a={2,1,3}a={2,1,3}a={2,3,1}a[1]

a[1]輸出213輸出231a[0]

a[0]a[0]

a[1]a={3,2,1}a={3,2,1}a={3,1,2}a[1]

a[1]輸出321輸出312求a={1，2，3}全排列6/363{1,2,3}2{1,2,3}{1,3,2}{1,3,2}{1,2,3}{1,2,3}3321{2,1,3}{2,3,1}{2,3,1}{2,1,3}{2,1,3}3312{3,2,1}{3,1,2}{3,1,2}{3,2,1}{3,2,1}11221第0層第1層第2層第3層（葉結(jié)點）標(biāo)準(zhǔn)解空間7/361 defdfs(x,i): #回溯算法2 ifi==len(x):3 print(x)4 else:5 forjinrange(i,len(x)):6 x[i],x[j]=x[j],x[i] #x[i]后x[j]交換7 dfs(x,i+1)8 x[i],x[j]=x[j],x[i] #回溯910 defperm(a): #求a的全排列11 x=a #解向量12 dfs(x,0)求數(shù)組a（不含重復(fù)整數(shù)）的全排列8/361 class

Solution:2

def

permute(self,

nums:

List[int])

->

List[List[int]]:3

self.ans=[]

#存放nums的全排列4

x=nums5

self.dfs(x,0)6

return

self.ans78

def

dfs(self,x,i):

#回溯算法9

if

i==len(x):10

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

else:12

for

j

in

range(i,len(x)):13

x[i],x[j]=x[j],x[i]14

self.dfs(x,i+1)15

x[i],x[j]=x[j],x[i]LeetCode46:用于求數(shù)組nums的全排列。9/36上述程序提交時通過，執(zhí)行用時為32ms，內(nèi)存消耗為15.2MB。10/36問題描述：給定一個可包含重復(fù)數(shù)字的序列

nums，設(shè)計一個算法按任意順序

返回所有不重復(fù)的全排列。

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

要求設(shè)計如下方法：def

permuteUnique(self,

nums)

->

List[List[int]]:5.4.2實戰(zhàn)—含重復(fù)元素的全排列II（LeetCode47★★）11/36該問題與求非重復(fù)元素全排序問題類似，解空間是排列樹，并且屬于求所有解類型。先按求非重復(fù)元素全排序的一般過程來求含重復(fù)元素的全排序，假設(shè)a={1，1，2}，其中包含兩個1，為了區(qū)分，后面一個1用紅色表示，求其全排列的過程如下圖所示。解2

21

11

2{1,1,2}1

1{1,1,2}{1,2,1}{1,2,1}{1,1,2}{1,1,2}2

21

21

11

1{1,1,2}{1,2,1}{1,2,1}{1,1,2}{1,1,2}1

21

11

1{2,1,1}{2,1,1}{2,1,1}{2,1,1}{2,1,1}1

11

11

11

1第3層（葉子）第0層第1層第2層12/362

21

11

2{1,1,2}1

1{1,1,2}{1,2,1}{1,2,1}{1,1,2}{1,1,2}2

21

21

11

1{1,1,2}{1,2,1}{1,2,1}{1,1,2}{1,1,2}1

21

11

1{2,1,1}{2,1,1}{2,1,1}{2,1,1}{2,1,1}1

11

11

11

1第3層（葉子）第0層第1層第2層13/36ABxi=xjxi=xn-1xi=xixi=xk第i層第i+1層……第0層C…當(dāng)j從i到n-1循環(huán)時，每次循環(huán)執(zhí)行swap(x[i]，x[j])為i位置選取元素x[j]，如果x[j]與x[i..j-1]中某個元素相同則會出現(xiàn)重復(fù)的排列，則跳過（稱為同層去重）。也就是說，在執(zhí)行swap(x[i]，x[j])之前先判斷x[j]是否在前面元素x[i..j-1]的中出現(xiàn)過，如果沒有出現(xiàn)過，則繼續(xù)做下去，否則跳過x[j]的操作。14/361 class

Solution:2

def

permuteUnique(self,

nums)

->

List[List[int]]:3

self.ans=[]

#存放nums的全排列4

x=nums5

self.dfs(x,0)6

return

self.ans15/368

def

dfs(self,x,i):

#回溯算法9

if

i==len(x):10

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

else:12

for

j

in

range(i,len(x)):13

if

self.judge(x,i,j):continue

#檢測x[j]14

x[i],x[j]=x[j],x[i]15

self.dfs(x,i+1)16

x[i],x[j]=x[j],x[i]1718

def

judge(self,x,i,j):

#判斷x[j]是否出現(xiàn)在x[i..j-1]中19

if

j>i:20

for

k

in

range(i,j):

#x[j]是否與x[i..j-1]相同

21

if

x[k]==x[j]:return

True

#若相同則返回真22

return

False

#全部不相同返回假16/36上述程序提交時通過，執(zhí)行用時為52ms，內(nèi)存消耗為15.2MB。17/36問題描述：有n（n≥1）個任務(wù)需要分配給n個人執(zhí)行，每個任務(wù)只能分配給一個人，每個人只能執(zhí)行一個任務(wù)。第i個人執(zhí)行第j個任務(wù)的成本是c[i][j]（0≤i，j≤n-1）。求出總成本最小的一種分配方案。人員任務(wù)0任務(wù)1任務(wù)2任務(wù)3092781643725818376945.4.3任務(wù)分配問題18/36解n個人和n個任務(wù)編號均用0～n-1表示。每個合適的分配方案x一定是0～n-1的一個排列，可以求出0～n-1的全排列，每個排列作為一個分配方案，求出其成本，比較找到一個最小成本bestc即可。19/36cost這里swap(x[i],x[j])即xi=xj表示人員i安排任務(wù)xj第i層第i+1層第n層(葉子結(jié)點)minsum…剪支：僅僅擴(kuò)展bound(cost,i+1)<bestc的孩子結(jié)點。下界=cost+minsum20/3622 defbound(cost,i): #求下界算法24 minsum=025 fori1inrange(i,n): #求c[i..n-1]行中最小元素和26 minc=INF27 forj1inrange(0,n):28 ifnotused[x[j1]]andc[i1][x[j1]]<minc: minc=c[i1][x[j1]]29 minsum+=minc30 returncost+minsum人員任務(wù)0任務(wù)1任務(wù)2任務(wù)309278164372581837694例如：i=2人員0已分配任務(wù)1人員1已分配任務(wù)0minsum=1+4=521/363 defdfs3(cost,i): #回溯算法4 globalc,n,x,bestx,bestc,used,sum5 sum+=16 ifi>=n: #到達(dá)一個葉子結(jié)點7 ifcost<bestc: #比較求最優(yōu)解8 bestc=cost9 bestx=copy.deepcopy(x)22/3610 else:11 forjinrange(i,n): #為人員i試探任務(wù)x[j]12 ifused[x[j]]:continue #跳過已經(jīng)分配的任務(wù)j13 x[i],x[j]=x[j],x[i] #為人員i分配任務(wù)x[j]14 used[x[i]]=True15 cost+=c[i][x[i]]16 ifbound(cost,i+1)<bestc: #剪支17 dfs3(cost,i+1) #為人員i+1分配任務(wù)18 cost-=c[i][x[i]] #cost回溯19 used[x[i]]=False #used回溯20 x[i],x[j]=x[j],x[i]#x回溯23/3632 defallocate3(c,n): #求解任務(wù)分配問題33 globalx,bestx,bestc,used,sum34 x=[]35 foriinrange(0,n):x.append(i)

#初始化解向量x36 bestx=[0]*n #最優(yōu)解向量37 bestc=INF #最優(yōu)成本初始化為∞38 used=[False]*n39 sum=040 dfs3(0,0) #從人員0開始41 print("求解結(jié)果")42 forkinrange(0,n):43 print("人員%d分配任務(wù)%d"%(k,bestx[k]))44 print("總成本=",bestc)45 print("sum=",sum)24/36程序驗證算法的解空間是一棵排列樹，同時復(fù)制更優(yōu)解和求下界的時間為O(n)，所以最壞的時間復(fù)雜度為O(n×n!)。例如，上述實例中n=4，經(jīng)測試不剪支時搜索的結(jié)點個數(shù)為65，而剪支后搜索的結(jié)點個數(shù)為9。算法分析人員任務(wù)0任務(wù)1任務(wù)2任務(wù)30927816437258183769425/36任務(wù)分配問題在5.3.9節(jié)采用基于子集樹框架時最壞時間復(fù)雜度為O(n2×nn)。采用基于排列樹框架的最壞時間復(fù)雜度為O(n2×n!)。顯然n>2時，O(n!)優(yōu)于O(nn)，實際上由于前者通過used判重，剪去了重復(fù)的分支，其解空間本質(zhì)上也是一棵排列樹。兩種算法的最壞時間復(fù)雜度都是O(n2×n!)。說明26/36假設(shè)有一個貨郎擔(dān)要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發(fā)的城市，要求路徑長度最短的路徑。89736858602135875路徑1：0→1→2→3→0：28路徑2：0→1→3→2→0：29路徑3：0→2→1→3→0：26路徑4：0→2→3→1→0：23路徑5：0→3→2→1→0：59路徑6：0→3→1→2→0：595.4.4貨郎擔(dān)問題（TSP）27/36解用鄰接矩陣A存儲帶權(quán)圖。起點為s。設(shè)計解向量x=（x0，x1，…，xn-1），每個xi表示一個圖中頂點，實際上每個x表示一條路徑，初始時x0置為起點s，x1～xn-1為其他n-1個頂點編號。28/36算法dfs(x，d，s，i)基于排列樹框架，設(shè)計的幾個重點如下：d表示當(dāng)前路徑的長度，用bestx保存最短路徑，bestd表示最短路徑長度，其初始值置為∞。x0固定作為起點s，不能取其他值，所以應(yīng)該從i=1（此時d=0）開始調(diào)用dfs。x1～xn-1為1～n-1的排列0……………0……假設(shè)s=0x1xn-1x0…x0A[x0][x1]A[x1][x2]A[xn-2][xn-1]A[xn-1][x0]29/36假設(shè)s=0，x初始時為（0，1，…，n-1），i=1時x1會取x[1..n-1]的每一個值：當(dāng)x1=x1（1）時，對應(yīng)路徑長度為d+A[0][1]，當(dāng)x1=x2（2）時，對應(yīng)路徑長度為d+A[0][2]，以此類推。0→1，x1=1d+=A[0][x1]0→n-1，x1=n-1d+=A[0][x1]第1層（x1）第2層……第i層：xi取x[i..n-1]中的某個值后當(dāng)前路徑長度為d+A[x[i-1]][x[i]]。30/36當(dāng)搜索到達(dá)某個葉子結(jié)點時（i≥n），對應(yīng)的TSP路徑長度應(yīng)該是d+A[x[n-1]][s]（因為TSP路徑是閉合的回路），對應(yīng)的路徑是x∪{s}。通過長度的比較求最優(yōu)解。剪支：若當(dāng)前已經(jīng)求出最短路徑長度bestd，如果xi取xj值，對應(yīng)的路徑長度為d+A[x[i-1]][x[j]]，僅僅擴(kuò)展?jié)M足d+A[x[i-1]][x[j]]<bestd的路徑。31/363 defdfs(d,s,i): #回溯算法5 ifi>=n: #到達(dá)一個葉子結(jié)點6 ifd+A[x[n-1]][s]<bestd: #比較求最優(yōu)解7 bestd=d+A[x[n-1]][s] #求TSP路徑長度8 bestx=copy.deepcopy(x) #更新bestxsx[n-1]sdA[x[n-1][s]32/369else:10 forjinrange(i,n): #試探x[i]到x[j]11 ifA[x[i-1]]