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