搜索入门.ppt

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