2013集训队论文答辩(乔明达)演示文稿

《2013集训队论文答辩(乔明达)演示文稿》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、搜索问题中的meetinthemiddle技巧南京外国语学校乔明达meetinthemiddle思想两人分别从A地和B地出发，向对方的出发点走去当他们都走了L/2米的时候“在中间相遇”(meetinthemiddle)找到了一条长度为L米的路径有向图模型有向图G中寻找点A到点B的长度为L的路径路径长度定义为边数求路径的数目点数多，重复子问题较少→不适合动态规划算法流程时间复杂度方程模型方程的解数，NOI2001ABCDEF,SPOJEllysBulls,TopCoderSRM572小结普遍问题：有向图模型&方程模型特殊问题：meetinthemiddle的变种

2、例题：BalancedCowSubsets例题：BalancedCowSubsets例题：BalancedCowSubsets根据需要在散列表中存储其他相关信息特殊性：不均匀划分可能得到更好效果例题：AlphabetPaths例题：AlphabetPaths例题：AlphabetPaths起点和终点未知中间点数目较少两边向中间→中间向两边总结核心思想：将问题分成两部分分别搜索，快速地合并两部分搜索结果优点：容易实现不足：时间复杂度仍然是指数级别，消耗大量的空间总结实际问题→meetinthemiddle思想有向图模型→方程模型（普遍性）两个特殊例题（特殊性）同

3、一个技巧在不同题目中的使用方法多种多样根据情况灵活地使用meetinthemiddle技巧，达到优化算法的目的感谢感谢CCF组织NOI系列活动，提供了与大家交流的机会！感谢亲人和朋友对我的鼓励与支持！感谢各位指导老师对我的指导！感谢众多学习信息竞赛的同学对我的帮助和启发！参考文献ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,CliffordStein,IntroductiontoAlgorithms.vexorian,TopCoderAlgorithmProblemSetAnalysis.BruceMerry

4、,USACO2012USOpenGoldDivision,BalancedCowSubsetsSolution.ZhipengJia,TopCoderSRM450~499Solution.谢谢大家，欢迎提问！