第5章-回溯法-New剖析(1)复习课程.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,5,章 回溯法,第5章-回溯法-New剖析(1),引入问题,关键：找到回溯的条件。,算法思想：,通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索往前试探，若试探成功，就得到解，若试探失败，就逐步往回退，换别的路线再往前试探。,实际上是,广度与深度搜索结合,的搜索，深度搜索过程中碰到条件不满足，则退回上一层，在每一层上也进行全面的搜索。,回溯法的基本思想,回溯法是带优化的穷举法。,回溯法的基本思想：在一棵含有问题全部可能解的,状态空间树,上进行深度优先搜索，,解为叶子结点,。搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。,在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是,在搜索过程中逐步构造出状态空间树,，即,边搜索，边构造,。,回溯法是一个既带有,系统性,又带有,跳跃性,的搜索算法。,它在包含问题的所有解的解空间树中，按照,深度优先,的策略，从根结点出发搜索解空间树。,算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。,（,1,）如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。,（,2,）否则，进入该子树，继续按深度优先的策略进行搜索。,回溯法在用来,求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。,回溯法在用来,求问题的任一解时，,只要,搜索,到问题的,一个解,就可以,结束。,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,1,1,1,0,0,0,1,1,1,1,0,0,0,0,例如，对于有,n,种可选物品的,0-1,背包问题，其解空间由长度为,n,的,0-1,向量组成。,以,3,件物品实例,扩展结点,：一个,正在产生儿子的结点,称为扩展结点,活结点,：一个,自身已生成但其儿子还没有全部生成的结点,称做活结点,死结点,：一个,所有儿子已经产生的结点,称做死结点,从开始结点（根结点）出发，以,深度优先,的方式搜索整个解空间。这个开始结点,-,活结点,，同时也成为当前的,扩展结点,。,在当前的扩展结点处，搜索,向纵深方向,移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。,如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为,死结点,。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。,回溯法即以这种工作方式,递归,地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。,深度优先的问题状态生成法,：如果对一个扩展结点,R,，一旦产生了它的一个儿子,C,，就把,C,当做新的扩展结点。在完成对子树,C,（以,C,为根的子树）的穷尽搜索之后，将,R,重新变成扩展结点，继续生成,R,的下一个儿子（如果存在）,宽度优先的问题状态生成法,：在一个扩展结点变成死结点之前，它一直是扩展结点,回溯法,：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用,限界函数,(bounding function),来剔除那些实际上不可能产生所需解的活结点，以减少问题的计算量。,具有限界函数的深度优先生成法称为回溯法。,示例,1 0-1,背包问题,n=3,C=30,w=16,15,15,v=45,25,25,A,C,r,=C=30,，,V=0,L,N,M,B,w,1,=16,，,v,1,=45,C,r,=14,，,V=45,G,C,r,=30,，,V=0,C,C,r,w,2,不可行解,E,C,r,45,x=(0,1,1),H,w,2,=15,，,v,2,=25,C,r,=15,，,V=25,J,2550,不是,最优,解,示例,1 0-1,背包问题,开始时，,Cr=C=30,，,V=0,，,A,为唯一活结点,，也是当前,扩展结点,扩展,A,，先到达,B,结点,Cr=Cr-w1=14,，,V=V+v1=45,；此时,A,、,B,为活结点，,B,成为当前扩展结点,；扩展,B,，先到达,C,Crw2,，,C,导致一个不可行解，回溯到,B,再扩展,B,到达,D,D,可行，此时,A,、,B,、,D,是活结点，,D,成为新的扩展结点,；扩展,D,，先到达,E,Cr45,，皆,得到一个可行解,x=(0,1,1),，,V=50,I,不可扩展，成为死结点，返回到,H,再扩展,H,到达,J,J,是叶结点，且,2550,，不是最优解,J,不可扩展，成为死结点，返回到,H,H,没有可扩展结点，成为死结点，返回到,G,再扩展,G,到达,L,Cr=30,，,V=0,，活结点为,A,、,G,、,L,，,L,为当前扩展结点,扩展,L,，先到达,M,，,M,是叶结点，且,2550,，不是最优解,，又,M,不可扩展，返回到,L,再扩展,L,到达,N,，,N,是叶结点，且,0n)output(x);/,当搜索到叶结点，输出可行解,else,for(int i=f(n,t);in)output(x);,else,for(int i=0;in)output(x);,else,for(int i=t;i=n;i+),swap(xt,xi);,if(legal(t),backtrack(t+1);,swap(xt,xi);,八皇后问题,是一个古老而著名的问题。该问题是十九世纪著名的数学家,高斯,1850,年提出。,在,8X8,格的国际象棋上摆放八个皇后，使其不能互相攻击，即,任意两个皇后都不能处于同一行、同一列或同一斜线上,，问有多少种摆法。,高斯认为有,76,种方案。,1854,年在柏林的象棋杂志上不同的作者发表了,40,种不同的解，后来有人用图论的方法解出,92,种结果。,N,皇后问题,问题描述,在*的棋盘上，放置个皇后，要求每一横行，每一列，每一对角线上均只能放置一个皇后，求可能的方案及方案数。,问题的状态即棋盘的布局状态，状态空间树的根为空棋盘，每个布局的下一步可能布局为该布局结点的子结点；,任意两个王后不放在同一行或同一列或同一斜线。因此为了简化状态空间树，采用逐行布局的方式，即每个布局有,n,个子结点；,N,皇后问题,一、回溯过程分析：,1,、从空棋盘起，,逐行,放置棋子。,2,、每在一个布局中放下一个棋子，即推演到一个新的布局。,3,、如果当前行上没有可合法放置棋子的位置，则,回溯,到上一行，重新布放上一行的棋子。,N,皇后问题,N,皇后问题,二、存储结构,(1),二维数组,ANN,存储皇后位置,若第,i,行第,j,列放,有皇后,则,Aij,为非,0,值,否则值为,0,。,(2),一维数组,Mk,、,Lk,、,Rk,分别表示竖列、左斜线、右斜线是否放有棋子,有则值为,1,否则值为,0,。,j,i,0,1,2,3,0,1,2,3,M0,M1,M2,M3,j,i,0,1,2,3,0,1,2,3,k,值和皇后位置坐标,i,，,j,的关联？,k=i+j k=0 2*(N-1),j,i,0,1,2,3,0,1,2,3,k,值和皇后位置坐标,i,，,j,的关联？,k=i-j k,会出现负值,k=i-j+N k=1 2*(N+1),右,右,j,i,0,1,2,3,0,L0,R4,L1,R3,L2,R2,L3,R1,1,L1,R5,L2,R4,L3,R3,L4,R2,2,L2,R6,L3,R5,L4,R4,L5,R3,3,L3,R7,L4,R6,L5,R5,L6,R4,M0,M1,M2,M3,Mk,（,k=j,）,Lk,（,k=i+j,）,Rk,（,k=i-j+N,）,三、算法描述,初始化,for(,某一行的每个位置,)if(,安全,),放皇后,;if(,已到最后一行,),输出,;else,试探下一行,;,去皇后,;,N,皇后问题,安全算法：,!Mj,放皇后：,Aij=Mj=Ri-j+N=Li+j=1;,去皇后：,Aij=Mj=Ri-j+N=Li+j=0;,#define N 4 /*N,为皇后个数*,/,int count=0;,int MN=0,L2*N=0,R2*N=0;,int ANN=0;/*,皇后位置*,/,void print(int ANN);,int mytry(int i,int MN,int L2*N,int R2*N,int ANN);,void main(),int n=mytry(0,M,L,R,A);/,代表从,0,行开始试探,cout“n count=”n;/n,可行解数目,/*,试探每一行皇后的位置*,/,int mytry,(,int i,int MN,int L2*N,int R2*N,int ANN,),for(int j=0;jN;j+),/,放置在,i,行,j,列,if(!Mj&!Li-j+N&!Ri+j),/,安全检查,Aij=i+1;,/,放皇后,Mj=Li-j+N=Ri+j=1;,if(i=N-1),print(A);coutendl;count+;,else mytry(i+1,M,L,R,A);,/,试探下一行,Aij=0;,/,去皇后,Mj=Li-j+N=Ri+j=0;,return count;,void print(int ANN)/*,输出*,/,int i,j;,for(i=0;iN;i+),for(j=0;jN;j+),cout Aij;,coutendl;,图的m着色问题,给定无向连通图,G,和,m,种不同的颜色。用这些颜色为图,G,的各顶点着色，每个顶点着一种颜色。是否有一种着色法使,G,中,每条边的,2,个顶点着不同颜色,。这个问题是图的,m,可着色判定问题。若一个图最少需要,m,种颜色才能使图中每条边连接的,2,个顶点着不同颜色，则称这个数,m,为该图的色数。求一个图的色数,m,的问题称为,图的,m,可着色优化问题,。,把,n,个板块抽象为一个图的,n,个顶点,图的着色问题是由地图的着色问题引申而来的，用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。,一、产生背景,二、问题描述,给定无向连通图,G,和,m,种不同的颜色。用这些颜色为图,G,的各顶点着色，每个顶点着一种颜色。是否有一种着色法使,G,中每条边的,2,个顶点着不同颜色。如果有则称这个图是m可着色，否则称这个图不是m可着色。若一个图最少需要k种颜色才能使图中每条边连接的,2,个顶点着不同颜色，则称这个数k为该图的色数。,三、算法设计,输入：,颜色,种类m,输出：如果这个图不是m可着色，给出否定回答；如果这个图是m可着色的，找出所有不同的着色法。,思考？,如何将给定的无向图存储在计算机中？,1,4,2,3,可以用以下邻接矩阵来表示,1 1 1 1 0,1 1 1 1 1,1 1 1 1 0,1 1 1 1 1,0 1 0 1 1,邻接矩阵中通常用二维数组来存放边之间的关系，用一维数组来存放顶点的信息。所以在接下来的求解问题中我们将用到二维数组a来存放两边是否相邻，,用一维数组x来存放每个顶点的颜色;xi=j表示第i个节点图第j中颜色,。,5,我们可以把问题简化为3个点来分析，现给定如下图,，怎样求解呢？,1,2,3,该图的色数是多少？怎样用解空间树来表示呢？,由图可知，对于每一个顶点可选的颜色可以有3种不同的选择，所以每一个节点有3个儿子节点，有4层。,判断条件是什么？,新加入的节点t取某一种颜色i时，依次和上层的每一个节点j(jt)比较。如果atj=1并且xt=xj,=i,那么它是不可着色的。,int OK(int t),int j;,for(j=1;jt;j+),if(atj=1&xj=xt),return 0;,return 1;,模拟演示,t=1,t=2,t=3,t=4,void Backtrace(int t,，,int m),当前节点,颜色的种类,当搜索的当前节点,tN,），即可输出一种方案,for(i=1;iN),sum+;,printf(,第,%d,种方案：,n,sum);,for(i=1;i=N;i+),printf(%d,xi);,四、程序代码,#include,#include,#define N 3/图中节点的个数,int aN+1N+1=,0,0,0,0,0,1,1,1,0,1,1,1,0,1,1,1,;/邻接矩阵,int xN+1;/记录颜色,int sum=0;/保存可以着色的方案数,int OK(int t,int i)/判断函数,int j;,for(j=1;jN)/算法搜索至叶子节点,sum+;,printf(第%d种方案：n,sum);,for(i=1;i=N;i+),printf(%d,xi);,printf(n);,else,for(i=1;i=m;i+),if(OK(t,i),xt=i;,Backtrace(t+1,m);,int main(),int m;,int i;,printf(请输入颜色种类：n);,scanf(%d,for(i=1;in)/*n:,顶点数*,/,sum+;,输出,xi,；,else,for(int i=1;i=m;i+),xt=i;/*,设置颜色*,/,if(ok(t)backtrack(t+1);,int Color:,ok,(int k),/*,检查颜色可用性*,/,for(int j=1;j=n;j+),if(akj=1)&(xj=xk),/*k,j,间有边且颜色相同*,/,return 0;/*,所用颜色非法*,/,return 1;,Akj,1,2,3,4,5,1,0,1,1,1,0,2,1,0,1,1,1,3,1,1,0,1,0,4,1,1,1,0,1,5,0,1,0,1,0,xt,1,2,3,4,5,1,2,3,4,1,图的m着色问题,复杂度分析,图,m,可着色问题的解空间树中内结点个数是,对于每一个内结点，在最坏情况下，用,ok,检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时,O(mn),。因此，回溯法总的时间耗费是,考场安排图的着色原理之运用,【,问题描述,】,设学校共有,n,门课，需要进行期末考试，因为不少学生不止选修一门课程，所以不能把同一个学生选修的两门课程安排在同一场次进行考试，问学期的期末考试最少需多少场次考完？,【,问题分析,】,本问题可转换成是对一平面图的顶点着色问题判定，采用回溯法求解。将所选的每门课程变成一个结点，若一个同学选了,m(1mn),门课程时，则这,m,门课程所对应的结点互相用一条边连接起来。则相邻边的顶点不能着同一种颜色，既不能安排在同一场次考试。但本题又不同于,m-,着色问题，而是要求最少场次考完，故本问题是求,min-,着色问题，既所有的顶点最少可用多少种颜色来着色，则本问题可解。,【,数据结构,】,图的邻接矩阵,testMAXMAX,来表示一个图,G,，其中若（,i,，,j,）是,G,的一条边，则,testij=testji=1,，否则,testij=testj i=0,，因为本问题只关心一条边是否存在，所以用邻接矩阵。,颜色总数用总课程数目,N,表示,。生成解则用数组,valueMAX,来记录，其中,valuei,是结点,i,的颜色，即课程,i,可安排在第,valuei,场考试，,resultMAX,用来记录最优解。程序中,N,表示课程总数，,minSum,表示最少的考试场次。,【,主要算法,】,testArrange()/,找一个图的考试方案,if(k=N),if(jminSum)/,记录最少的考试场数,minSum=j;,for(t=1;t=N;t+),resultt=valuet;/,记录最优解,else,testArrange(k+1);/,递归调用,回溯法求解,0-1,背包问题,解空间：子集树,可行性约束函数：,解题的基本指导思想,:,按贪心法的思路，优先装入,价值,/,重量比,大的物品。当剩余容量装不下最后考虑的物品时，再用回溯法修改先前的装入方案，直到得到全局最优解为止。,/*,数据结构*,/,#define N 5 /,物品数目,int v=6,3,6,5,4,w=2,2,4,6,5;,int C=10;/,背包容量,int cp;/,当前价值,int bestp=0;/,最优价值,int xN;/,当前解,int bestxN;/*,当前最优解*,/,void,main(),/,按物品价值重量比排降序,/,输出物品初始价值、重量（略）,knap(0);,cout,最优价值,:bestpt;,cout,此时放入背包物品,:;,for(j=0;jN;j+),if(bestxj=1),coutj+1 ;,cout=N),if(bestpcp),bestp=cp;,/,保存最优解,for(int j=0;jN;j+),bestxj=xj;,putout();,else,if(wt=C),/,搜索左枝,xt=1;cp+=vt;C-=wt;,knap(t+1);,/,继续向下深度搜索,xt=0;C+=wt;cp-=vt;,/,回退,xt=0;,/,搜索右枝,knap(t+1);,/*,输出*,/,void,putout(),cout,物品放入背包状态为：,;,for(int i=0;iN;i+),coutsetw(5)xi;,cout,获得的价值,=cp;,coutendl;,实际搜索解空间树,策略,:,只要其左儿子结点是一个可行结点，搜索就进入其左子树。,约束函数,当右子树,有可能包含最优解,时才进入右子树搜索，否则将右子树剪去。,限界函数,前面算法完全搜索解空间树,:,即用约束条件确定是否搜索其左子树；,对右子树没有任何判断，,一定,进入右子树搜索。,-,耗时,剪枝方法：,r:,当前,剩余物品价值总和,；,cv:,当前获得价值；,bestp:,当前最优价值。,当,cv+r=bestp,时，可剪去右子树。,计算右子树上界方法,:,将,剩余物品,依其,单位重量价值排序,，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。由此得到的价值是右子树中解的,上界,。,int Bound(int i)/计算当前结点处上界,int left=C-cw;/剩余容量,int b=cv;/cv当前价值,while(wi=left&i=N),b+=vi;,left-=wi;,i+;,/*装满背包*/,if(iN)/*,到叶结点*,/,for(j=1;j=N;j+),bestxj=xj;,bestv=cv;,else if(cw+wibestv)/*,搜索右子树*,/,xi=0;,Backtrack(i+1);,void putout(),cout,放入背包的物品是,:;,cw=0;,for(int i=1;i=N;i+),if(bestxi=1),coutit;cw+=wi;,coutendl,放入背包物品总重为：,cwt;,cout,最大价值和为,:bestvendl;,0-1,背包课件演示,.cpp,w=,2,2,4,6,5,N=5,C=10,v=,6,3,6,5,4,0,C,r,=C=10,，,V=0,1,w,1,=2,v,1,=6,C,r,=8,cv=6,5,2,w,2,=2,v,2,=3,C,r,=6,cv=9,Bound=15bestp,Bound=16,3,1:bestp=15,10,Bound=12,4,w3=4,v3=6,Cr=2,cv=15,6,Cr=2,cv=15,7,Bound=15,Cr=2,cv=15,8,Bound=14 n)/,到达叶结点,更新最优解,bestx,bestw;return;,r-=wi;,if(cw+wi bestw),xi=0;/,搜索右子树,backtrack(i+1);,r+=wi;,批处理作业调度,给定,n,个作业的集合,J,1,J,2,J,n,。每个作业必须,先由机器,1,处理，然后由机器,2,处理,。机器,j,处理作业,J,i,需要时间为,t,ij,（,i=1,2n;j=1,2,）。对于一个确定的作业调度，设,F,ij,是作业,i,在机器,j,上完成处理的时间。,所有作业在机器,2,上完成处理的时间和称为该作业调度的完成时间和,。,批处理作业调度问题要求对于给定的,n,个作业，制定最佳作业调度方案，使其完成时间和达到最小。,批处理作业调度,t,ij,机器,1,机器,2,作业,1,2,1,作业,2,3,1,作业,3,2,3,这,3,个作业的,6,种可能的调度方案是,1,2,3,；,1,3,2,；,2,1,3,；,2,3,1,；,3,1,2,；,3,2,1,；它们所相应的完成时间和分别是,19,，,18,，,20,，,21,，,19,，,19,。易见，最佳调度方案是,1,3,2,，其完成时间和为,18,。,批处理作业调度,0 2 5 7,0 2 3 5 6 7 10,调度方案是,1,2,3,，相应的完成时间和是,19=3+6+10,调度方案是,1,3,2,，相应的完成时间和是,18=3+7+8,0 2 4 7,0 2 3 4 7 8,解空间：排列树,void Flowshop:Backtrack(int i),if(i n),for(int j=1;j=n;j+),bestxj=xj;,bestf=f;,else,for(int j=i;j f1)?f2i-1:f1)+Mxj2;,f+=f2i;,if(f bestf),Swap(xi,xj);,Backtrack(i+1);,Swap(xi,xj);,f1-=Mxj1;,f-=f2i;,int *M,/,各作业所需的处理时间,*,x,/,当前作业调度,*,bestx,/,当前最优作业调度,*,f2,/,机器,2,完成处理时间,f1,/,机器,1,完成处理时间,f,/,完成时间和,bestf,/,当前最优值,n;/,作业数,连续邮资问题,【,问题描述,】,假设国家发行了,N,种不同面值的邮票，并且规定每张信封上最多只允许贴,M,张邮票。连续邮资问题要求对于给定的,N,和,M,的值，给出,邮票面值的最佳设计,，在,1,张信封上可贴出从邮资,1,开始，增量为,1,的最大连续邮资区间。,例如，当,N=5,和,M=4,时，面值为,(1,3,11,15,32),的,5,种邮票可以贴出邮资的最大连续邮资区间是,1,到,70,。,x1,：,N,：表示,N,种不同的邮票面值，并约定它们从小到大排列。,x1=1,是惟一的选择。,（,1,）在未确定剩余其它,N,1,种邮票面值的情况下，只用,x1,一种邮票面值，所能得到的最大连续邮资区间是,1,：,M,。,（,2,）确定,x2,的取值范围,x2,的值最小可以取到,2,，最大可以取到,M+1,。,（,3,）一般的情况下，若已选定,x1,到,xi-1,，最大连续邮资区间是,1,：,r,时，接下来,xi,的可取值范围是,xi-1+1,：,r+1,。,连续邮资问题,若,x1,到,xi-1,，最大连续邮资区间是,1,：,r,时，接下来,xi,的可取值范围是,xi-1+1,：,r+1,。,例如，当,N=3,和,M=2,时,可选值,最大连续邮资,X1,1,1,，,2,X2,2,1,，,4,3,1,，,4,X3,3,1,，,2,，,3 1,，,6,4,1,，,2,，,4 1,，,6,1,，,3,，,4 1,，,8,5,1,，,2,，,5 1,，,7,1,，,3,，,5 1,，,6,【,解决方案及基本思想,】,（,1,）基本思路：搜索所有可行解，当,i=N,时，当前结点,Z,是解空间中的内部结点。在该结点处,x1:i-1,能贴出最大连续区间为,r,。因此，在结点,Z,处，,x,的可能取值范围是,xi-1+1,：,r+1,，从而，结点,Z,有,r-xi-1+1,个儿子结点。算法对当前结点,Z,的每一个儿子结点以深度优先遍历的方式递归的对应子树进行搜索，从而找出最大连续邮资区间的方案。,（,2,）解向量：用,n,元组,x1:n,表示,N,种不同的邮票面值，并约定它们从小到大排列。,x1=1,是唯一的选择。（,x,表第,i,张邮票的面值）,【,解决方案及基本思想,】,（,3,）可行性约束函数：已选定,x1:i-1,，最大连续邮资区间是,1r,下来,x,的可取值范围是,xi-1+1r+1,。（,r,表,x1:i-1,所能达到的连续区间的上界）,连续邮资问题,如何确定,r,的值？,(1),计算,X1:i,的最大连续邮资区间在本算法中被频繁使用到，因此势必要找到一个高效的方法。,(2),直接递归的求解复杂度太高，尝试计算用不超过,M,张面值为,x1:i,的邮票贴出邮资,k,所需的最少邮票数,yk,。通过,yk,可以很快推出,r,的值。,(3)yk,可以通过递推在,O(n),时间内解决：,具体代码参见附件回溯法“连续邮资问题”,回溯和递归的区别,递归法,好比是一个军队要通过一个迷宫，到了第一个分岔口，有,3,条路，将军命令,3,个小队分别去探哪条路能到出口，,3,个小队沿着,3,条路分别前进，各自到达了路上的下一个分岔口，于是小队长再分派人手各自去探路,只要人手足够（对照而言，就是计算机的堆栈足够），最后必将有人找到出口，从这人开始只要层层上报直属领导，最后，将军将得到一条通路。,回溯法则是一个人走迷宫的思维模拟,，只寄希望于自己的记忆力。回溯实际上是递归的展开。,练习,问题描述,原始部落居民为了争夺资源经常发生冲突，几乎每个居民都有仇敌。部落酋长为了组织一支队伍，希望从部落中挑出最多的居民入伍，并保证队伍中任何两个人都不是仇敌。,任务,给定居民间仇敌关系，输出组成队伍的最佳方案。,输入,居民人数，居民间仇敌个数，仇敌关系,输出,部队人数，那些居民入选,居民,1,2,3,4,5,6,7,1,1,1,2,1,1,1,1,1,3,1,1,1,4,1,1,1,5,1,1,1,1,6,1,1,1,7,The End,此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢,