計算與人工智能概論第5章算法思維第三節(jié)遞歸與分治

分治的

基本概念1PART在右邊的數字三角形中尋找一條從頂部到底邊的路徑，使得路徑上所經過的數字之和最大，路徑上的每一步都只能往左下或右下走，只需求出最大的和，不需要給出具體路徑。思考一下，可能的路徑一共有多少？分析后可知，對于n層的數字，一共有2n-1條不同的路徑。直接用循環(huán)來求出每條路徑的和是非常困難的，這里我們用分治策略來解決這個問題。數字三角形游戲數字三角形問題是個典型的最優(yōu)化問題。最優(yōu)化問題指的是，問題可以有多個解，每個解有一個值，我們希望找到最優(yōu)的那個值，稱為一個最優(yōu)解（最優(yōu)解可能有多個）。數字三角形問題中，從上往下有很多不同的路徑，這些不同的路徑就是不同的解，其中路徑上的數字和最大的解，就是我們要尋找的最優(yōu)解。最優(yōu)化問題與最優(yōu)解分治策略的核心是：1

將大的問題分解為形式相同的更小的子問題，子問題繼續(xù)分解為更小的子問題...一直分解下去，直到問題小到可以直接求解（自頂向下分解）；2

直接解決最小的問題。3

最小問題求解后的結果依次進行合并，解決較大的問題，一直進行下去，直到解決原問題（自底向上合并）。這個過程就是分治(Divideandconquer)注意，前面講的二分法也是一種分治，是一種盡量將問題分為規(guī)模相同的2個子問題的分治。分治=分解+解決+合并以7為頂點(頂點為第0行第0列)的三角形問題，記為f(0,0)），可分解成2個較小的問題：1

以3為頂點(頂點為第1行第0列)的問題，記為f(1,0)2

以8為頂點(頂點為第1行第1列)的問題，記為f(1,1)可知，f(0,0)=7+max(f(1,0),f(1,1))，這是個分解動作。即：一個三角形問題=該問題頂點的數字+下面兩個子問題的解的較大者注意，下面3個問題的形式完全相同，問題規(guī)模不同分解分解（divide）f(1,0)和f(1,1)如何求解？當然是繼續(xù)分解 f(1,0)=3+max(f(2,0),f(2,1)) f(1,1)=8+max(f(2,1),f(2,2))因此f(0,0)=7+max(3+max(f(2,0),f(2,1)),

8+max(f(2,1),f(2,2)))一直分解下去，直到f(4,x)，x為列號；由于是最后一層，可知f(4,x)=A[4][x]。分解（divide）層數大于等于2的問題都無法直接求出結果，需要繼續(xù)分解，直到層數為1考察原問題左下角的層數為2的問題的分解f(3,0)=2+max(f(4,0),f(4,1))=2+max(A[4][0],A[4][1])=2+5=7下圖中，只有一層的問題可以直接求解，結果就是該層上的數字，這就是解決。分解解決（conquer）最小子問題求解之后，根據規(guī)則組合成上一層的子問題的解，一直進行下去，可以將原問題的解求出。右圖中，右上角的小數字表示以大數字為頂點的子問題的解，都是用大數字加上左下角的小數字和右下角小數字中的較大者，例如:f(0,0)=7+max(f(1,0),f(1,1))=7+max(23,21)=30從下往上仔細查看圖中的小數字，分析合并的過程。合并（merge）

用遞歸

實現分治2PART有兩種實現分治的方法：遞歸（自頂向下）、遞推（自底向上），本節(jié)介紹遞歸方法什么是遞歸函數調用自身的操作例如，下面的代碼用遞歸方式求n的階乘defFactorial(n):ifn==1:return1#最小子問題，遞歸的出口else:returnn*Factorial(n-1)#遞歸調用print(Factorial(10)) 一定要為遞歸函數設計出口，否則會陷入死循環(huán)，最后會導致棧溢出。什么是遞歸用分治策略完成n的階乘。1分解方法：n!=n*(n-1)!2統(tǒng)一表達式：f(i)是i的階乘3最小子問題：f(1)=1用遞歸函數表達分治策略：f(n)=n*f(n-1)f(1)=1階乘問題分治是思想，遞歸是實現分治的手段之一（另一種方式是遞推，以后介紹）。掌握正確的問題拆解方法 n!=n*(n-1)!-->f(n)=n*f(n-1)掌握用函數統(tǒng)一表達子問題的方法 f(i)是i的階乘為原問題定義最小子問題 f(1)=1階乘問題首先，設計數據結構來存儲三角形數據

最簡單直觀的方式，是使用嵌套的列表：A=[[7],[3,8],[8,1,0],[2,7,4,4],[4,5,2,6,5]]對A中任一數字A[i][j]，其左下角的數為A[i+1][j]，右下角的數為A[i+1][j+1]遞歸方式：f(0,0)=A[0,0]+max(f(1,0),f(1,1))f(n-1,x)=A[n-1][x];最底層的三角形，可直接求解；x為列號。f(0,0)是原問題，表示以A[0][0]為頂點的三角形的最大路徑和。用遞歸解決三角形問題用函數描述用正確的函數來統(tǒng)一描述原問題和子問題。defMaxRoute(i,j):定義一個函數MaxRoute，完成如下功能：

計算以第i行第j列為頂點的三角形的最大路徑和，數據在嵌套列表A中。表述原問題：MaxRoute(0,0)表述下一層的子問題：MaxRoute(1,0)和MaxRoute(1,1)表述最底層：MaxRoute(4,0),...MaxRoute(4,0)的值是4所有的子問題（含原問題）都可以用這個函數表達，而且函數用來解決這些問題的機制都一樣。用遞歸解決三角形問題用遞歸描述問題分解使用MaxRoute函數可以描述問題分解：

對于1個以第i行、第j列元素為頂點的三角形的問題，若i不是最后一行，可以按如下方式分解：

MaxRoute(i,j)=A[i][j]+max(MaxRoute(i+1,j),MaxRoute(i+1,j+1))這是一種遞歸的定義，即一個函數借助調用自身來完成子任務，當然參數不一樣，調用自身時解決的是規(guī)模較小的子問題。用遞歸解決三角形問題完整的程序A=[[7],[3,8],[8,1,0],[2,7,4,4],[4,5,2,6,5]]#以A中的第i層第j列為頂點的三角形的解，i和j從0開始defMaxRoute(i,j):ifi==len(A)-1:#可直接求解的最小子問題（遞歸函數的出口）

result=A[i][j]else:#問題分解，子問題的形式和原問題相同，用遞歸調用

result=A[i][j]+max(MaxRoute(i+1,j),MaxRoute(i+1,j+1))returnresultprint(MaxRoute(0,0))用遞歸解決三角形問題時間復雜度分析對于n層的數字三角形，T(n)=2*T(n/2)=22*T(n/22)=...=2n-1*T(1)即，時間復雜度為O(2n)當n超過為21層時，可明顯觀察到程序的執(zhí)行需要一定的時間，下面隨機生成一個24層的數字三角形，觀察一下需要運行多長時間。如果100層呢？用遞歸解決三角形問題#生成一個24層的數字三角形importrandomrandom.seed(7)#固定隨機數種子，每次產生相同序列n=24A=[]foriinrange(n):layer=[]forjinrange(i+1):layer.append(random.randint(0,100))A.append(layer)print(MaxRoute(0,0))#結果為1585例2：漢諾塔問題3PART傳說古老印度的一個圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必在大片上面。當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，梵塔、廟宇和眾生都將同歸于盡。我們的任務是，編寫程序，輸出將所有的金片從A移動到C的詳細步驟。漢諾塔問題原問題：將n個金片從A移動到C（借助B）。分解：將上面的n-1個金片從A移動到B（借助C）；將最下面的金片直接從A移動到C；將n-1個金片從B移動到C（借助A）。合并：上述3個動作的結果一起構成原問題的解。最小問題：當移動的金片只有一個時，可直接移動。解題思路定義函數：move(n,a,b,c)表示將n個金片從a(第2個參數是起點)移動到c(第4個參數是終點)，以b為中介(第3個參數是中轉站)。可分解為3個子問題：1move(n-1,a,c,b)2move(1,a,b,c)3move(n-1,b,a,c)解題思路defmove(n,a,b,c):ifn==1:print(a,"--->",c)else:move(n-1,a,c,b)move(1,a,b,c)move(n-1,b,a,c)n=10move(n,"A","B","C")代碼實現例3：

最大子序列和4PART對于一個整數序列A，其中包含正數和負數，找到一個連續(xù)子序列，使得該子序列中元素的和是最大的；輸出這個最大的和。注意，只有序列中存在負數時，這個問題才有意義；如果只有正數，整個序列的和就是最大的。例如，對于下圖中的序列，第8到第11個元素之和，是所有可能的子序列中最大的。最大子序列和暴力求解的思路很簡單，從第1個元素開始，嘗試長度為1、2、...n的子序列，然后從第2個元素開始，嘗試長度為1、2、...n-1的子序列......，時間復雜度是O(n2)。觀察一下，1000個數需要的時間（結果為137602）算法1：使用循環(huán)importrandomrandom.seed(7)#固定隨機種子每次產生相同序列A=[]n=1000foriinrange(n):A.append(random.randint(-10000,10000))result=-1e50#負無窮大foriinrange(n):#i是子序列開始位置

forjinrange(i+1,n+1):#j是子序列結束位置

result=max(result,sum(A[i:j]))print(result)解題思路使用分治技術來求解該問題，對于序列A[low..high]，找到中間位置mid，用mid將原序列分解為A[low..mid]和A[mid+1..high]，

則A[low..high]的任何連續(xù)子序列A[i..j]所處位置必然是下列情況之一：1

完全位于子序列A[low..mid]中，因此low≤i≤j≤mid。2完全位于子序列A[mid+1..high]中，因此mid≤i≤j≤high。3跨越中點mid，因此low≤i≤j≤high。這個特殊問題可直接求解。因此，A[low..high]的最大子序列所處位置也必然是上述3種情況之一，實際上，A[low..high]的最大子序列是上述3種情況中的最大者。算法2：使用分治解題思路情形1和情形2都是區(qū)間更小的子問題。情形3并非原問題的子問題，因為子序列跨越了2個區(qū)間。對于情形3，A[i..j]可分解為A[i..mid]和A[mid+1..j]，因此，若能在A[low..mid]中求出和最大的A[i..mid]，在A[mid+1..high]中求出和最大的A[mid+1..j]，將二者合并即可。算法2：使用分治遞歸方式f(low,high)=A[low]；low==high時f(low,high)=max(f(low,mid), f(mid+1,,high),cross(low,mid,high));其他情況算法2：使用分治#求A[low..high]中跨越mid的最大序列和defFindMaxCrossing(A,low,mid,high):leftSum=-1e50#負無窮大

sum0=0foriinrange(mid,low-1,-1):sum0+=A[i]ifsum0>leftSum:

leftSum=sum0rightSum=-1e50#負無窮大

sum0=0foriinrange(mid+1,high+1):sum0+=A[i]ifsum0>rightSum:

rightSum=sum0returnleftSum+rightSum情形3的實現函數#求A[low..high]中的最大序列和defFidMax(A,low,high):iflow==high:returnA[low]#最小子問題mid=(low+high)//2leftSum=FidMax(A,low,mid)rightSum=FidMax(A,mid+1,high)crossSum=FindMaxCrossing(A,low,mid,high)returnmax(leftSum,rightSum,crossSum)importrandomrandom.seed(7)#固定隨機數種子，每次產生相同序列A=[]n=1000foriinrange(n):A.append(random.randint(-10000,10000))result=FidMax(A,0,len(A)-1)print(result)實現遞歸函數新程序的時間復雜度為O(nlogn)，觀察程序的執(zhí)行效率，發(fā)現效率比暴力法大大提高。這個問題的關鍵是，分解出來的3個部分中，只有2個是和原問題形式相同的子問題，第3個情形的形式和原問題不相同，需要進行特別處理。時間復雜度分析例4：

平面最近點對5PART給定二維平面中n個點的坐標（整數），找出距離最近的2個坐標點之間的距離，n<=10000。暴力求解的思路很簡單，求出所有的兩個坐標之間的距離，找出其中最小的值即可。后面的代碼設置了n為2000，觀察其執(zhí)行時間。平面最近點對importrandom,mathrandom.seed(7)#固定隨機數種子，每次產生相同序列A=[]n=2000foriinrange(n):x,y=random.randint(-10000,10000),random.randint(-10000,10000)A.append((x,y))defDistance(a,b):returnmath.sqrt((a[0]-b[0])**2+(a[1]-b[1])**2)result=1E50#無窮大foriinrange(n-1):forjinrange(i+1,n):dis=Distance(A[i],A[j])result=min(result,dis)print(result)#結果為2.23606797749979算法1：使用循環(huán)解題思路把所有的點按照橫坐標排序

用一條豎直的線將所有的點分成兩等份

遞歸算出左半部分的最近兩點距離d1，右半部分的最近兩點距離d2，取d=min(d1,d2)

算出“一個在左半部分，另一個在右半部分”這樣的點對的最短距離d3。結果＝min(d1,d2,d3)

算法1：使用分治解題思路要求A[low...high]中最小的點距，可將坐標點按照x坐標從小到大排序，選取索引號在最中間的點mid，將序列分為A[low...mid]、A[mid+1,high]兩部分，設最小點距的兩個坐標的索引號分別為i和j，最小點距必然在下列3種情形中：1

兩個點都位于子序列A[low..mid]中，因此low≤i≤j≤mid。2

兩個點都位于子序列A[mid+1..high]中，因此mid<i≤j≤high。3

兩個點跨越中點mid（或包含mid），因此low≤i≤mid<j≤high。可見，這個題目和最大序列和非常相似。算法1：使用分治情形3如圖所示，求出左邊最短距離d1和右邊的最短距離d2后，選取他們較小者作為依據（設為d1），可知，只需對以mid為中心，左右各寬為d1的區(qū)間中的坐標點，找出最小距離(篩除掉縱坐標>=d1的)即可，這個最小距離就是情形3的解。顯然，情形3因為區(qū)間較小，執(zhí)行效率也會很高。算法1：使用分治遞歸方式f(low,high)=∞;low≥high時f(low,high)=min(f(low,mid-1), f(mid+1,high),cross(low,mid,d));其他情況

其中d=min(f(low,mid-1),f(mid+1,,high))注意：low≥high表示區(qū)間里面只有一個點或沒有點，計算距離無意義。算法1：使用分治情形3的實現代碼#設mid對應橫坐標為A[mid].x，求A[mid].x-d到A[mid].x+d范圍內的最小點距crossDis=1e50#無窮大foriinrange(mid,low-1,-1):

ifA[mid][0]-A[i][0]>d:break#左邊界

forjinrange(mid+1,high+1):ifA[j][0]-A[i][0]>d:break#右邊界

ifA[j][1]-A[i][1]>d:continue#不可能的點

dis