由图论问题浅析算法优化,由图论问题浅析算法优化,图论问题,2,图论是数学的一个分支，它以图为研究对象，研究节点和边组成的图形的数学理论和方法。,图论问题与信息学竞赛联系紧密，经典的图论模型以及相关算法已成为竞赛中不可或缺的知识。,图论问题2 图论是数学的一个分支，它以图,算法优化,3,基础图论知识,优化是一个逐步发现并利用问题的特殊之处、使算法更有针对性的过程。,解决问题,原始算法,优秀算法,优化,针对性化,算法优化3基础图论知识优化是一个逐步发现并利用问题的特殊之,例 二分图的最大匹配,4,图的匹配：,图中任何两条边都没有共同顶点的子图。,二分图的最大匹配：,二分图中边数最多的匹配。,例 二分图的最大匹配4,网络流模型,5,在二分图中加入源点、汇点，改为网络。,网络流模型5在二分图中加入源点、汇点，改为网络。,网络流模型,6,在二分图中加入源点、汇点，改为网络。,S,T,0/1,0/1,0/1,0/1,0/1,0/1,0/1,0/1,0/1,0/1,网络流模型6在二分图中加入源点、汇点，改为网络。ST0/10,网络流算法,7,广搜可增广链,S,T,0/1,0/1,0/1,0/1,0/1,0/1,0/1,0/1,0/1,0/1,网络流算法7广搜可增广链ST0/10/10/10/10/10,优化方法,8,所有边的容量均为1,不记录容量,优化方法8所有边的容量均为1,优化方法,9,S,T,0/1,0/1,0/1,0/1,0/1,0/1,0/1,0/1,0/1,0/1,0,0,0,0,0,0,0,0,0,0,优化方法9ST0/10/10/10/10/10/10/10/,优化方法,10,S,T,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,优化方法10ST0000000000111111,优化方法,11,所有边的容量均为1,不记录容量,与源点、汇点相连的边的流量可由其他边的流量推出,改为记录点的匹配情况,优化方法11所有边的容量均为1,优化方法,12,1,1,2,3,4,5,6,S,T,0,0,0,0,1,1,1,1,1,5,0,4,3,1,0,优化方法121123456ST000011111504310,优化方法,13,所有边的容量均为1,不记录容量,与源点、汇点相连的边的流量可由其他边的流量推出,改为记录点的匹配情况,可增广链结构特殊,优化方法13所有边的容量均为1,优化方法,14,1,2,3,4,5,6,S,T,4,6,0,1,0,2,优化方法14123456ST460102,优化方法,15,所有边的容量均为1,不记录容量,与源点、汇点相连的边的流量可由其他边的流量推出,改为记录点的匹配情况,可增广链结构特殊,只搜索中间部分,优化方法15所有边的容量均为1,匈牙利算法,16,1,2,3,4,5,6,4,1,6,2,4,3,5,1,0,0,0,0,0,0,匈牙利算法1612345641624351000000,回顾,17,容量特殊,调整存储方式,网络结构特殊,改进搜索算法,设计网络流算法时的两个实用优化手段,减少存储空间,减少运行时间,回顾17容量特殊设计网络流算法时的两个实用优化手段减少存储空,小结,18,寻找特别之处 优化的根本途径,经验 耐心 灵感,小结18寻找特别之处 优化的根本途径经验 耐心,优化方向,19,速度慢,占用空间过大,难以实现,难以记忆,时间复杂度,空间复杂度,编写难度,思维难度,不能完全解决问题,正确率,优化方向19速度慢时间复杂度 不能完全解决问题正确率,应对有缺陷的算法,20,面对难题时，我们难免会有意或无意地设计出有漏洞的算法,简单处理、提高正确率,分析问题、纠正错误,放弃算法、另寻他解,应对有缺陷的算法20面对难题时，我们难免会有意或无意地设计出,快速处理,21,加入特殊判断过程,随机化重复求解,最优化问题,取重复求解得到的最优值,判定性问题,正确率大于50,可以正确判断,“,是,”,、,“,否,”,中的一个方面,快速处理21加入特殊判断过程,导致错误的原因,22,误解,模型的性质,猜想,错误,忽略,算法细节,Fishing Net,Flying Right,Cow Patterns,导致错误的原因22,例 Flying Right,23,一条航线上有N个机场，编号1到N。有K群牛等待乘坐飞机，第i群牛中有M,i,头牛，它们要从S,i,机场飞到E,i,机场（S,i,小于E,i,）。,请问一架可承载C头牛的飞机从1号机场飞到N号机场最多可以把多少头牛送到目的地？,这当中，可以将一群牛拆散，只将其中的一部分带到目的地。,例 Flying Right23 一,输入数据的规模,24,机场数：,牛群数：,每群中的牛数：,飞机容量：,1N10,000,1K50,000,1M,i,C,1C100,逐一考虑每个座位？,输入数据的规模24机场数：1N10,000逐一考虑每个座,最小费用流,容量：边所对应的群中牛的个数,费用：-1（为了适应最小费用流）,为空闲的座位加入辅助边,容量无穷大、费用为零,25,4,3,2,1,每个单位流对应一个座位,群A,群B,费用为-2,最小费用流容量：边所对应的群中牛的个数254321每个单位流,最小费用流,26,算法的时间复杂度为O(K*N*C),无法承受题目给出的数据规模,另一方面，在这个十分特殊的图上直接套用最小费用流的算法未免有些浪费,如何优化？,最小费用流26算法的时间复杂度为O(K*N*C),无法承受题,忽略后向边,27,寻找可增广链时考虑后向边使得后续过程可以调整已扩展的流，解决了后效性问题,忽略后向边相当于逐一为每个座位选择运送牛数最多的方案，选择后不再改动,用动态规划求解，时间复杂度为O(K*C)，可以接受,忽略后向边27寻找可增广链时考虑后向边使得后续过程可以调整已,反例,假设四条边都只代表一头牛，而飞机上有两个座位,对当前座位“同样优”的两条边可能会对最终结果有不同的影响,28,3,2,1,4,A牛,B牛,C牛,D牛,需要进一步判断边的优劣关系,反例假设四条边都只代表一头牛，而飞机上有两个座位283214,边的优劣关系,29,一条边含有两个参数：,起点、终点,假设飞机正停在某个机场,设法减少一个,选择目的地最近的！,c,b,a,d,-换个角度看问题-,选择这一条,边的优劣关系29一条边含有两个参数：设法减少一个cbad-,最终算法,30,将所有边按照终点排序,在每个机场携带目的地最近的C头牛继续飞行,直接实现的时间复杂度为O(N*C),问题解决,最终算法30将所有边按照终点排序问题解决,小结,分析错误的能力为大胆猜想提供了保障,31,思路受阻,猜想,错误算法,问题解决,小结分析错误的能力为大胆猜想提供了保障31思路受阻猜想错误算,小结,32,提高算法的正确率是一种十分灵活的优化,解题过程更流畅,小结32提高算法的正确率是一种十分灵活的优化解题过程更流畅,总结,33,算法优化,特殊信息,正确率,空间复杂度,时间复杂度,思维难度,编写难度,总结33算法优化特殊信息正确率空间复杂度时间复杂度思维难度编,结束语,34,每一次算法优化都是一次思维的旅程,无论结果怎样，思维都会有所收获,结束语34每一次算法优化都是一次思维的旅程,