计算与人工智能概论（第2版）（微课版）课件 第5章 算法设计3 递归与分治

计算与人工智能概论第5章算法思维第三节递归与分治

分治的

基本概念1PART在右边的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大，路径上的每一步都只能往左下或右下走，只需求出最大的和，不需要给出具体路径。思考一下，可能的路径一共有多少？分析后可知，对于n层的数字，一共有2n-1条不同的路径。直接用循环来求出每条路径的和是非常困难的，这里我们用分治策略来解决这个问题。数字三角形游戏数字三角形问题是个典型的最优化问题。最优化问题指的是，问题可以有多个解，每个解有一个值，我们希望找到最优的那个值，称为一个最优解（最优解可能有多个）。数字三角形问题中，从上往下有很多不同的路径，这些不同的路径就是不同的解，其中路径上的数字和最大的解，就是我们要寻找的最优解。最优化问题与最优解分治策略的核心是：1

将大的问题分解为形式相同的更小的子问题，子问题继续分解为更小的子问题...一直分解下去，直到问题小到可以直接求解（自顶向下分解）；2

直接解决最小的问题。3

最小问题求解后的结果依次进行合并，解决较大的问题，一直进行下去，直到解决原问题（自底向上合并）。这个过程就是分治(Divideandconquer)注意，前面讲的二分法也是一种分治，是一种尽量将问题分为规模相同的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个问题的形式完全相同，问题规模不同分解分解（divide）f(1,0)和f(1,1)如何求解？当然是继续分解 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的问题都无法直接求出结果，需要继续分解，直到层数为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）最小子问题求解之后，根据规则组合成上一层的子问题的解，一直进行下去，可以将原问题的解求出。右图中，右上角的小数字表示以大数字为顶点的子问题的解，都是用大数字加上左下角的小数字和右下角小数字中的较大者，例如:f(0,0)=7+max(f(1,0),f(1,1))=7+max(23,21)=30从下往上仔细查看图中的小数字，分析合并的过程。合并（merge）

用递归

实现分治2PART有两种实现分治的方法：递归（自顶向下）、递推（自底向上），本节介绍递归方法什么是递归函数调用自身的操作例如，下面的代码用递归方式求n的阶乘defFactorial(n):ifn==1:return1#最小子问题，递归的出口else:returnn*Factorial(n-1)#递归调用print(Factorial(10)) 一定要为递归函数设计出口，否则会陷入死循环，最后会导致栈溢出。什么是递归用分治策略完成n的阶乘。1分解方法：n!=n*(n-1)!2统一表达式：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)掌握用函数统一表达子问题的方法 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]为顶点的三角形的最大路径和。用递归解决三角形问题用函数描述用正确的函数来统一描述原问题和子问题。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))这是一种递归的定义，即一个函数借助调用自身来完成子任务，当然参数不一样，调用自身时解决的是规模较小的子问题。用递归解决三角形问题完整的程序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层时，可明显观察到程序的执行需要一定的时间，下面随机生成一个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传说古老印度的一个圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的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，其中包含正数和负数，找到一个连续子序列，使得该子序列中元素的和是最大的；输出这个最大的和。注意，只有序列中存在负数时，这个问题才有意义；如果只有正数，整个序列的和就是最大的。例如，对于下图中的序列，第8到第11个元素之和，是所有可能的子序列中最大的。最大子序列和暴力求解的思路很简单，从第1个元素开始，尝试长度为1、2、...n的子序列，然后从第2个元素开始，尝试长度为1、2、...n-1的子序列......，时间复杂度是O(n2)。观察一下，1000个数需要的时间（结果为137602）算法1：使用循环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]的任何连续子序列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都是区间更小的子问题。情形3并非原问题的子问题，因为子序列跨越了2个区间。对于情形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)，观察程序的执行效率，发现效率比暴力法大大提高。这个问题的关键是，分解出来的3个部分中，只有2个是和原问题形式相同的子问题，第3个情形的形式和原问题不相同，需要进行特别处理。时间复杂度分析例4：

平面最近点对5PART给定二维平面中n个点的坐标（整数），找出距离最近的2个坐标点之间的距离，n<=10000。暴力求解的思路很简单，求出所有的两个坐标之间的距离，找出其中最小的值即可。后面的代码设置了n为2000，观察其执行时间。平面最近点对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：使用循环解题思路把所有的点按照横坐标排序

用一条竖直的线将所有的点分成两等份

递归算出左半部分的最近两点距离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的区间中的坐标点，找出最小距离(筛除掉纵坐标>=d1的)即可，这个最小距离就是情形3的解。显然，情形3因为区间较小，执行效率也会很高。算法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表示区间里面只有一个点或没有点，计算距离无意义。算法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