1、数据结构与算法1北京工业大学北京工业大学 计算机学院计算机学院软件学科部软件学科部 陈文博陈文博 数据结构与算法2数据结构与算法3 算法设计与分析内容介绍算法设计与分析内容介绍 算法分析的方法算法分析的方法 递归与分治算法递归与分治算法 回溯算法回溯算法 贪心算法贪心算法 数据结构与算法4 从引例看算法设计从引例看算法设计 表达算法的抽象机制表达算法的抽象机制 数学算法与数据结构算法数学算法与数据结构算法 算法与数据结构的关系算法与数据结构的关系 算法分析的方法算法分析的方法 常用算法模式常用算法模式数据结构与算法5010203040506071234123456712345670111111
2、100011010011001010100111101111001011000110从引例看算法设计从引例看算法设计11数据结构与算法612341234123412341234Backtracking Algorithm Idea数据结构与算法7public boolean backtrack()Stack S=new ArrayStack();/Initialize system;i=1;/the i is number of a task j=1;/the j is item number of choice do (!whole project has completed)数据结构与算法
3、8do while(!The choice exceeds the scope)&(!whole project has completed)if(!matchConstraint(i,j)j+;else break;if(!The choice exceeds the scope)S.push(i,j);i+;j=1;/new task in beginning else if(!S.empty()(i,j)=S.pop();j+;/test new choice else return false;if(whole project has completed)return true;(!w
4、hole project has completed)12 341 2 341 2 341 2 341 2 34数据结构与算法9 ADT Stack 数据对象数据对象：ai|ai ElemSet,i=1,2,.,n,n0 数据关系数据关系：|ai-1,aiD,i=2,.,n 约定约定an 端为端为，a1 端为端为。ADT Stack 基本操作：基本操作：数据结构与算法10表达算法的抽象机制表达算法的抽象机制数数 据据 模模 型型初始状态初始状态结果状态结果状态算算 法法顶层算法顶层算法底层算法底层算法宏观步骤宏观步骤 算法骨干算法骨干变量抽象变量抽象 运算粗化运算粗化微观步骤微观步骤 算法细节
5、算法细节变量具体变量具体 运算细化运算细化ADT(抽象抽象)运算步骤运算步骤数据结构与算法11数学层面的算法与数据结构层面的算法数学层面的算法与数据结构层面的算法 数据结构层面的算法数据结构层面的算法public Object pop()if(empty()throw new EmptyStackException();Object topElement=stacktop;return topElement;涉及对具体数据结构的操作涉及对具体数据结构的操作数据结构与算法12 数学层面的算法数学层面的算法不涉及对具体数据结构的操作不涉及对具体数据结构的操作只使用数据结构只使用数据结构ADT的接口
6、的接口数据结构与算法13算法与数据结构的关系算法与数据结构的关系算法算法 vsvs 抽象的逻辑的数据结构抽象的逻辑的数据结构 四染色算法四染色算法 vsvs 具体的数据结构具体的数据结构 四染色算法四染色算法 vsvs 逻辑的数据结构逻辑的数据结构 （往往由（往往由控制结构控制结构得到体现）得到体现）12341234123412341234whileif else if do 数据结构与算法14 渐进时间复杂度渐进时间复杂度 平均时间复杂度平均时间复杂度v 一般的分析方法一般的分析方法v 递归方程的求解递归方程的求解数据结构与算法15例例 四染色回溯算法四染色回溯算法4*4*44n=4nT(n
7、)=O(4n)数据结构与算法16void hanoi(int n,char x,char y,char z)/将塔座将塔座x x上按直径由小到大且至上而下编号为上按直径由小到大且至上而下编号为1 1至至n n/的的n n个圆盘按规则搬到塔座个圆盘按规则搬到塔座z z上，上，y y可用作辅助塔座。可用作辅助塔座。if(n=1)move(x,1,z);/将编号为的圆盘从将编号为的圆盘从x移到移到z else hanoi(n-1,x,z,y);/将将x上编号为至上编号为至n-1的圆盘移到的圆盘移到y,z作辅助塔作辅助塔 move(x,n,z);/将编号为将编号为n的圆盘从的圆盘从x移到移到z han
8、oi(n-1,y,x,z);/将将y上编号为至上编号为至n-1的圆盘移到的圆盘移到z,x作辅助塔作辅助塔 Hanoi塔塔数据结构与算法17T(n)T(n-1)T(n-1)O(1)T(n)=T(n-1)+O(1)+T(n-1)=2 T(n-1)+O(1)递归方程的求解递归方程的求解数据结构与算法18T(n)=2 T(n-1)+O(1)=2(2T(n-2)+O(1)+O(1)=4T(n-2)+3O(1)=4(2T(n-3)+O(1)+3O(1)=8T(n-3)+7O(1)=8(2T(n-4)+O(1)+7O(1)=16T(n-4)+15O(1)T(n)=2kT(n-k)+(2k-1)O(1)数据结
9、构与算法19T(n)=2kT(n-k)+(2k-1)O(1)n-k=1 k=n-1 T(n)=2n-1 T(1)+(2 n-1-1)O(1)=2n-1 O(1)+(2 n-1-1)O(1)=22n-1 O(1)-O(1)=(2n 1)O(1)T(n)=O(2n)数据结构与算法20 递归与分治算法递归与分治算法 动态规划动态规划 贪心算法贪心算法 回溯算法回溯算法 分支限界算法分支限界算法 概率算法概率算法 遗传算法遗传算法数据结构与算法21数据结构与算法22 后置递归后置递归法法(Postponing the work)的设计思想为的设计思想为:假如某个问题的求解过程可以分成假如某个问题的求解
10、过程可以分成若干步进行，并且当前这一步的解可以若干步进行，并且当前这一步的解可以直接求得，则直接求得，则先求出当前这一步的解先求出当前这一步的解，对于对于余下的问题余下的问题，若问题的性质和原问，若问题的性质和原问题类似，则又可题类似，则又可递归求解递归求解。数据结构与算法23 递归的递归的终结状态终结状态是，当前的问题可是，当前的问题可以以直接求解直接求解，对原问题而言，则是已走，对原问题而言，则是已走到了求解的到了求解的最后一步最后一步。链表是可以如此求解的一个典型例子。链表是可以如此求解的一个典型例子。例如例如:编写编写“删除单链表中所有值为删除单链表中所有值为x 的的数据元素数据元素”
11、的算法。的算法。数据结构与算法24 1)单链表是一种顺序结构，必须从第一个单链表是一种顺序结构，必须从第一个结点起，逐个检查每个结点的数据元素结点起，逐个检查每个结点的数据元素;分析分析:2)从另一角度看，链表又是一个递归结构，从另一角度看，链表又是一个递归结构，若若 L 是线性链表是线性链表(a1,a2,an)的头指针，的头指针，则则 L-next是线性链表是线性链表(a2,an)的头指针。的头指针。数据结构与算法25 a1 a2 a3 an L例如例如:a1 a2 a3 an L a1 a2 a3 an L已知下列链表已知下列链表1)“a1=x”,则则 L 仍为删除仍为删除 x 后的链表头
12、指针后的链表头指针2)“a1x”,则余下问题是考虑以则余下问题是考虑以 L-next 为头指针的为头指针的链表链表 a1 L-nextL-next=p-nextp=L-next数据结构与算法26void delete_L(LinkList&L,ElemType x)/删除以删除以L L为头指针的带头结点的单链表中为头指针的带头结点的单链表中 /所有值为所有值为x x的数据元素的数据元素 if(L-next)if(L-next-data=x)p=L-next;L-next=p-next;delete(p);delete_L(L,x);else delete_L(L-next,x);/delete
13、数据结构与算法27void delete_L(LinkList&L,ElemType x)/L L为无头结点的单链表的头指针为无头结点的单链表的头指针 if(L)if(L-data=x)p=L;L=L-next;delete(p);delete_L(L,x);else delete_L(L-next,x);4.递归函数中的递归函数中的尾递归尾递归容易消除。容易消除。数据结构与算法28void delete(LinkList&L,ElemType x)/L L为带头结点的单链表的头指针为带头结点的单链表的头指针 p=L-next;pre=L;while(p)if(p-data=x)pre-nex
14、t=p-next;free(p);p=pre-next;else pre=p;p=p-next;上述递归算法可改写为迭代的形式上述递归算法可改写为迭代的形式数据结构与算法29数据结构与算法30 若求解问题的规模为若求解问题的规模为n 其次，逐步其次，逐步合并合并子问题的子问题的解解，直到，直到获得原问题的解。获得原问题的解。首先，把问题首先，把问题分解分解为为k 个个性质相同性质相同、但规模但规模 较小的较小的子问题子问题（1 k n)，并，并求解这些子问题。（如果这些子问题求解这些子问题。（如果这些子问题的规模还不够的规模还不够“小小”，则可以，则可以进一步进一步分解分解，直到可以求解为止）
15、，直到可以求解为止）数据结构与算法31PP1P2PkT1(n)T2(n)Tk(n)T(n)时间复杂度：时间复杂度：T(n)=T1(n)+T2(n)+Tk(n)+C(n)C(n)数据结构与算法32void mergeSort(RcdType&SR,int s,int t)/将将SRs.t 归并排序归并排序 if(s=t)return;int m=(s+t)/2;mergeSort(SR,s,m);mergeSort(SR,m+1,t);merge(SR,s,m,t);/mergeSort 例例 归并排序归并排序 数据结构与算法33T(n)T(n/2)T(n/2)Cn数据结构与算法34T(n)=T
16、(n/2)+T(n/2)+Cn=2T(n/2)+Cn=2(2T(n/4)+C(n/2)+Cn=4T(n/4)+Cn+Cn=4T(n/4)+2Cn =8T(n/8)+3Cn =2kT(n/2k)+kCn 2k=n k=log2nT(n)=nT(1)+log2nCn=Cnlog2n+d nT(n)=O(nlog2n)数据结构与算法35分治算法的设计模式分治算法的设计模式divide-and-conquer(P)if(|P|)=n0)adhocery(P);divide P into smaller subinstances P1,P2,Pk;for(i=1;i=k;i+)yi=divide-and
17、-conquer(Pi);return merge(y1,yk);数据结构与算法36最接近点对问题最接近点对问题分析分析（直线上直线上n个点，假设只有一对符合条件）个点，假设只有一对符合条件）算出每两个点的距离算出每两个点的距离.若排序若排序,需需O(n2),希望希望O(nlog2n)mS1S2p1p2p3q3q1q2d=min|p1-p2|,|q1-q2|数据结构与算法37public static double nearPair(S)n=|S|;if(n2)return ;m=S中各点坐标的中位数；中各点坐标的中位数；构造构造S1和和S2；/S1=x S|xm d1=nearPair(S1
18、);d2=nearPair(S2);d=min(d1,d2,q-p);return d;T(n)=2T(n/2)+O(n)=O(nlog2n)数据结构与算法38数据结构与算法39 在解决某一问题的过程中，贪心算在解决某一问题的过程中，贪心算法总是做出在法总是做出在当前看来当前看来最好的选择最好的选择。也就是说，贪心算法并不从整体最也就是说，贪心算法并不从整体最优考虑，它所做出的选择只是在某种意优考虑，它所做出的选择只是在某种意义上的义上的局部最优选择局部最优选择。（最终结果并不。（最终结果并不总是总是整体最优整体最优）数据结构与算法40四种硬币四种硬币 0.25 0.10 0.05 0.01
19、找顾客找顾客0.61 0.61-0.25=0.360.36-0.25=0.110.11-0.10=0.010.01-0.01=0.00整体最优（整体最优（币数最少币数最少）本例的币值结构具有最优子结构性质本例的币值结构具有最优子结构性质找钱问题找钱问题数据结构与算法41若四种硬币若四种硬币 0.11 0.05 0.01 找顾客找顾客0.15 0.15-0.11=0.040.04-0.01=0.030.03-0.01=0.020.02-0.01=0.01一般可以得到整体一般可以得到整体近似近似最优解最优解0.01-0.01=0.000.15-3*0.05=0.00数据结构与算法42贪心算法的设计
20、模式贪心算法的设计模式Greedy(inputSet,Solution,target)Solution=;target=;while(!findSolution)x=select(inputSet);if feasible(Solution,x)Solution=Solutionx;change(target,x)return Solution;数据结构与算法43最小生成树问题最小生成树问题(ST G=(V,E)public static void prim(int n,floatc)T=;S=1;while(S!=V)(i,j)=min(cij)|iS&j V-S T=T(i,j);S=S
21、j;数据结构与算法44abcdegf例如例如:195141827168213ae12dcbgf7148531621所得生成树权值和所得生成树权值和=14+8+3+5+16+21=67数据结构与算法45数据结构与算法4612341234123412341234数据结构与算法47 回溯算法术语 1.解向量解向量：问题解的向量表示形式。：问题解的向量表示形式。(x1,x2,xk)k n,n:问题的规模。问题的规模。2.约束条件约束条件 1）显式约束：对分量）显式约束：对分量xi的取值限定。的取值限定。2）隐式约束：为满足问题的解，）隐式约束：为满足问题的解，不同分不同分 量之间应遵守量之间应遵守的约
22、束。的约束。3.解空间：对于问题的一个实例，解向量满足解空间：对于问题的一个实例，解向量满足 显式约束条件的所有多元组，构成了该显式约束条件的所有多元组，构成了该 实例的一个实例的一个解空间解空间。数据结构与算法48v 状态空间树状态空间树 用于描述解空间的逻辑结构树用于描述解空间的逻辑结构树 v 目标函数与最优解目标函数与最优解 1.目标函数：衡量问题解目标函数：衡量问题解“优劣优劣”的标准的标准 2.最优解：使目标函数取极值的解最优解：使目标函数取极值的解 数据结构与算法49回溯算法的基本思想回溯算法的基本思想 回溯算法回溯算法有有“通用解题法通用解题法”之称，系统之称，系统搜索问题的所有
23、解，从中筛出符合条件的解搜索问题的所有解，从中筛出符合条件的解 它在问题的解空间树中，按它在问题的解空间树中，按深度优先深度优先的的策略进行搜索。搜索至某一结点时，判断其策略进行搜索。搜索至某一结点时，判断其是否包含问题的解。不包含，跳过对其子树是否包含问题的解。不包含，跳过对其子树的搜索，向其祖先的搜索，向其祖先回溯回溯；否则进入该子树，；否则进入该子树，继续按继续按深度优先深度优先的策略搜索的策略搜索 回溯算法可以求回溯算法可以求单一解单一解、所有解所有解，也可，也可以在所有解中求出以在所有解中求出最优解最优解数据结构与算法50 最佳分配问题最佳分配问题 假设有假设有n个人和个人和n项课题
24、项课题.其中第其中第 i个人干第个人干第j项课题的经费消耗为项课题的经费消耗为COST(i,j).解决分配解决分配,使每使每个课题只有一个人来承担个课题只有一个人来承担,一人一项一人一项,且完成这且完成这n项课题的总经费消耗最低项课题的总经费消耗最低.测试数据测试数据:123131625433493人人员员课课 题题COSTCOST(1,2)COST(2,3)COST(3,1)8数据结构与算法51数据结构与算法52void backtrack(int i,int n)/假设已求得满足约束条件的部分解假设已求得满足约束条件的部分解(x1,.,xi-1)，本函，本函 /数从数从 xi 起继续搜索，直到求得整个解起继续搜索，直到求得整个解(x1,x2,xn)。if(in)output(x);else while(!Empty(Si)从从 Si 中取中取 xi 的一个值的一个值 vi Si;if (x1,x2,xi)满足约束条件满足约束条件 backtrack(i+1,n);/继续求下一个部分解继续求下一个部分解 从从 Si 中删除值中删除值 vi;/backtrack数据结构与算法53D S+AlgorithmsC+/C#Java
