搜索入门.ppt

2017-3-27 1ACM 程序设计计算机学院刘春英 2017-3-27 2今天, 今天, 你了吗? ? AC 2017-3-27 3每周一星( 每周一星( 7 7): ): NPEG-MP4 && OPPO MP4 2017-3-27 4第八讲第八讲一招制敌之搜索题 2017-3-27 5 根据“信息学初学者之家”网站的统计, Ural (俄罗斯的 Ural 州立大学的简称,那里设立了一个 Ural Online Problem Set ,并且支持 Online Judge 。)的题目类型大概呈如下的分布: 搜索动态规划贪心构造图论约10% 约 15% 约 5% 约 5% 约10% 计算几何纯数学问题数据结构其它约 5% 约 20% 约 5% 约 25% 统计信息: 2017-3-27 6搜索题特点分析搜索题特点分析: : ?题意容易理解?算法相对固定?编程有路可循?竞赛必备知识 2017-3-27 7 ————摘自《摘自《 ACM ACM 竞赛之新人向导竞赛之新人向导》“算法中最基本和常用的是搜索,主要是回溯和分支限界法的使用。这里要说的是,有些初学者在学习这些搜索基本算法是不太注意剪枝, 这是十分不可取的,因为所有搜索的题目给你的测试用例都不会有很大的规模,你往往察觉不出程序运行的时间问题,但是真正的测试数据一定能过滤出那些没有剪枝的算法。实际上参赛选手基本上都会使用常用的搜索算法,题目的区分度往往就是建立在诸如剪枝之类的优化上了。”引言 2017-3-27 8什么是搜索算法呢? 搜索算法是利用计算机的高性能来有目的地穷举一个问题的部分或所有的可能情况, 从而求出问题的解的一种方法。搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。 2017-3-27 9预热一下:二分查找预热一下:二分查找 2 3 4 5 6 8 12 20 32 45 65 74 86 95 100 head mid tail 2017-3-27 10查找示意图: A[1]~A[15] A[1]~A[7] A[9]~A[15] A[1]~A[3] A[5]~A[7] A[1]~A[1] A[3]~A[3] ……