算法合集之《浅谈类比思想》.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,浅谈类比思想,长沙长郡中学,周戈林,内容摘要,信息学是一门变幻莫测的艺术。它包含着海量的知识点。我们不能奢求掌握所有的知识；只能在已有知识的基础上，尽可能的把不熟悉的问题转化为熟悉的问题。类比思想，就是一种非常优秀的转化方法。,什么是类比呢？,类比是最有创造力的一种思维方法。它关注两个对象在某些方面的相同或相似之处，从而推测它们在其它方面也可能存在相同或相似之处。,这就为我们解决复杂问题创造了条件。,什么是类比呢？（续）,铅笔与钢笔,铅笔与毛笔,简单类比与科学类比,铅笔和钢笔恰好都是硬笔，类比成功具有偶然性，它是基于直观上的感性认识，称之为简单类比,注意到铅笔与毛笔的不同点，类比成功带有某种必然性，它是基于逻辑上的理性认识，称之为科学类比,科学类比！,常见的类比模式,具体事物类比抽象模型,图形类比数式,相似算法之间的类比,餐巾问题(餐巾花费类比费用流),下面的例子,差分约束系统(不等式类比约束图),相似算法之间的类比,有些算法是相似的：,在算法,思想,上相似,在算法,依据,上相似,在算法,实现,上相似,例：,最小最大边问题(,USACO),有,n,座城市，,p,条双向道路把这些城市连接起来，一对城市之间可能有多条道路连接。,FJ,要找到,k,条从城市,1,到城市,n,的路径，,不同,的路径不能包含,相同,的道路。在这一前提条件下，,FJ,希望所有路径中经过的,最长的道路最短,。,输入样例,7 9 2,1 2 2,2 3 5,3 7 5,1 4 1,4 3 1,4 5 7,5 7 1,1 6 3,6 7 3,有7座城市，9条双向道路，,FJ,希望找到2条路径,分别给出每条道路连接的城市编号和道路长度,1,6,7,2,3,4,5,3,3,2,5,1,5,1,1,7,输出样例,5,1,6,7,2,3,4,5,3,3,2,5,5,1,1,1,7,Max3,3,2,5,5=5,初步分析,这是一个关于流的问题。题目给定,n,个点和,p,条容量为,1,的无向边，每条边都拥有一个边权,，,要求找到一个流量至少为,k,的流，同时流通过的边权最大的边最小。,似曾相识?,最小最大匹配!,最小最大匹配,这个匹配是在一个,带权二分图,上进行；,是一个,完备匹配,；,是满足上述条件的匹配中,最大边权最小,的匹配。,即定义,x,=max,匹配边的权,，,求使,x,最小的完备匹配。,算法1,利用参数搜索的思想，二分枚举一个,x，,再判定这个,x,是否可以得到。根据判定的结果适当改变枚举区间。,设当前区间为,min,max,x=(min+max)div 2,若,x,不行，则区间调整为,x+1,max,若,x,可行，则区间调整为,min,x-1,算法1（续）,类比,使用最大流算法判定能否得到不小于,k,的流,使用匈牙利算法判定能否得到完备匹配,算法1效率分析,边数有,p,条，对其进行二分需要,每次判定需要执行一次最大流算法,O(logp),O(kp),O(,k,plogp),O(logp)*O(kp)=,至多找,k,次增广路,每次找增广路复杂度,O(p),小结,利用简单类比，我们得到了一个不错的算法。,这种“二分枚举法”十分,直观,但是我们的类比停留在,形式,上！,继续寻找算法的相似点,最短路问题,最小生成树问题,最小最大边问题要求最大边权最小,最小费用最大流问题要求通过每条边的边权和最小,连续最短路算法,1,.,初始流分布使每条边,e,都为,f(e)=0;,2.,在当前的容许流分布下修改各边(,i,j),的费用,aij,aij,=,wij,0=,fij,0,3.,以,aij,为边长，找一条,s,到,t,的最短增广路,连续最短路算法（续）,4.,若能找到增广路就转2，否则转5,5.输出结果,如果利用普里姆算法的思想寻找增广路会怎么样？,算法2,1.初始流分布使每条边都为,f(e)=0；,2.,设立临时距离标号,di，,表示当前能扩展到,i,的增广轨中最长边长度的最小值。初始时除源点以外的临时距离标号都为正无穷大。,3.在计算距离标号时，假设,du,已经被扩展，正在考察边(,u,v)：,算法2（续）,假设正在考察边(,u,v)：,(,I).,若,u,到,v,的流量为0且,v,到,u,的流量为0，那么,dvmindv,maxdu,w(u,v)；,(,II).,若,v,到,u,的流量为1，那么,dvmindu,dv；,4.在求得所有的,dv,同时记录路径,5.当扩展次数超过,t,时结束，否则转2,引理1的证明,引理,1,：在算法依次找到的每条增广路中，,n,的距离标号是单调不减的。,证明：算法优先扩展最短的增广路。若存在增广路,Path,与,Path,满足,dna)，2,种方式的价格分别为,fa、fb,，,购买一条新毛巾价格为,f(ffafb)，,求用,最少的钱满足每天的需要。,