算法合集之《由图论问题浅析算法优化》.ppt

《算法合集之《由图论问题浅析算法优化》.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、由图论问题浅析算法优化武钢三中贾由图论问题图论是数学的一个分支，它以图为研究对象，研究节点和边组成的图形的数学理论和方法。图论问题与信息学竞赛联系紧密，经典的图论模型以及相关算法已成为竞赛中不可或缺的知识。2006年1月2由图论问题浅析算法优化算法优化基础图论知识优化是一个逐步发现并利用问题的特殊之处、使算法更有针对性的过程。解决问题原始算法优秀算法优化针对性化2006年1月3由图论问题浅析算法优化例·二分图的最大匹配图的匹配：图中任何两条边都没有共同顶点的子图。二分图的最大匹配：二分图中边数最多的匹配。2006年1月4由图论问题浅析算法优化网络流模型在二分图中加入源点、汇点，

2、改为网络。2006年1月5由图论问题浅析算法优化网络流模型ST0/10/10/10/10/10/10/10/10/10/1在二分图中加入源点、汇点，改为网络。2006年1月6由图论问题浅析算法优化网络流算法广搜可增广链ST0/10/10/10/10/10/10/10/10/10/12006年1月7由图论问题浅析算法优化优化方法所有边的容量均为1不记录容量2006年1月8由图论问题浅析算法优化优化方法ST0/10/10/10/10/10/10/10/10/10/100000000002006年1月9由图论问题浅析算法优化优化方法ST00000000001111112006年1月1

3、0由图论问题浅析算法优化优化方法所有边的容量均为1不记录容量与源点、汇点相连的边的流量可由其他边的流量推出改为记录点的匹配情况2006年1月11由图论问题浅析算法优化1优化方法123456ST0000111115043102006年1月12由图论问题浅析算法优化优化方法所有边的容量均为1不记录容量与源点、汇点相连的边的流量可由其他边的流量推出改为记录点的匹配情况可增广链结构特殊2006年1月13由图论问题浅析算法优化优化方法123456ST4601022006年1月14由图论问题浅析算法优化优化方法所有边的容量均为1不记录容量与源点、汇点相连的边的流量可由其他边的流量推出改为记

4、录点的匹配情况可增广链结构特殊只搜索中间部分2006年1月15由图论问题浅析算法优化12345641624351匈牙利算法0000002006年1月16由图论问题浅析算法优化回顾容量特殊调整存储方式网络结构特殊改进搜索算法设计网络流算法时的两个实用优化手段减少存储空间减少运行时间2006年1月17由图论问题浅析算法优化小结寻找特别之处－优化的根本途径经验耐心灵感2006年1月18由图论问题浅析算法优化优化方向速度慢占用空间过大难以实现难以记忆时间复杂度空间复杂度编写难度思维难度不能完全解决问题正确率2006年1月19由图论问题浅析算法优化应对有缺陷的算法面对难题时，我们难免会有

5、意或无意地设计出有漏洞的算法简单处理、提高正确率分析问题、纠正错误放弃算法、另寻他解2006年1月20由图论问题浅析算法优化快速处理加入特殊判断过程随机化＋重复求解最优化问题取重复求解得到的最优值判定性问题正确率大于50％可以正确判断“是”、“否”中的一个方面……2006年1月21由图论问题浅析算法优化导致错误的原因误解模型的性质猜想错误忽略算法细节《FishingNet》《FlyingRight》《CowPatterns》2006年1月22由图论问题浅析算法优化例·FlyingRight一条航线上有N个机场，编号1到N。有K群牛等待乘坐飞机，第i群牛中有Mi头牛，它们要从Si

6、机场飞到Ei机场（Si小于Ei）。请问一架可承载C头牛的飞机从1号机场飞到N号机场最多可以把多少头牛送到目的地？这当中，可以将一群牛拆散，只将其中的一部分带到目的地。2006年1月23由图论问题浅析算法优化输入数据的规模机场数：牛群数：每群中的牛数：飞机容量：1≤N≤10,0001≤K≤50,0001≤Mi≤C1≤C≤100逐一考虑每个座位？2006年1月24由图论问题浅析算法优化最小费用流容量：边所对应的群中牛的个数费用：-1（为了适应最小费用流）为空闲的座位加入辅助边容量无穷大、费用为零4321每个单位流对应一个座位群A群B费用为-22006年1月25由图论问题浅析算法优化

7、最小费用流算法的时间复杂度为O(K*N*C),无法承受题目给出的数据规模另一方面，在这个十分特殊的图上直接套用最小费用流的算法未免有些浪费如何优化？2006年1月26由图论问题浅析算法优化忽略后向边寻找可增广链时考虑后向边使得后续过程可以调整已扩展的流，解决了后效性问题忽略后向边相当于逐一为每个座位选择运送牛数最多的方案，选择后不再改动用动态规划求解，时间复杂度为O(K*C)，可以接受2006年1月27由图论问题浅析算法优化反例假设四条边都只代表一头牛，而飞机上有两个座位对当前座位“同样优”