搜索入门.ppt

根据“信息学初学者之家”网站的统计,Ural(俄罗斯的Ural州立大学的简称,有名的Ural Online Problem Set 就是该校的系统)的题目类型大概呈如下的分布:
搜索动态规划贪心构造图论
约10% 约15% 约5% 约5% 约10%
计算几何纯数学题数据结构其它约5% 约20% 约5% 约25%
统计信息:
11/30/2018
1
——摘自《ACM竞赛之新人向导》
“算法中最基本和常用的是搜索,这里要说的是,有些初学者在学****这些搜索基本算法是不太注意剪枝,这是十分不可取的,因为所有搜索的题目给你的测试用例都不会有很大的规模,你往往察觉不出程序运行的时间问题,但是真正的测试数据一定能过滤出那些没有剪枝的算法。
实际上参赛选手基本上都会使用常用的搜索算法,题目的区分度往往就是建立在诸如剪枝之类的优化上了。”
引言
11/30/2018
2
什么是搜索算法呢?
搜索算法是利用计算机的高性能来有目的地穷举一个问题的部分或所有的可能情况,从而求出问题的解的一种方法。

搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。
11/30/2018
3
预热一下:二分查找
2 3 4 5 6 8 12 20 32 45 65 74 86 95 100
head
mid
tail
11/30/2018
4
查找示意图:
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]
……
11/30/2018
5
思考:
1、在一百万个元素里查找某个元素大约需要比较多少次?
2、时间复杂度:O(logN)
11/30/2018
6
举例分析
从简单的字符串搜索讲起
11/30/2018
7
Sample Input23ABCDBCDFFBRCD2roseorchid
Sample Output
22
HDOJ_1238 Substrings
11/30/2018
8
题目分析:
这是一道入门级别的搜索题,基本思想比较简单,但是如果用最朴素的算法,可能会超时如何降低算法的复杂度呢?
下面的算法如何:
先将字符串按长度从短到长排序,枚举最短的字符串的子串,判断是否都是别的字符串的子串,求出最大长度即可。
11/30/2018
9
说明:
本题除了可以练****基本搜索算法,也是练****字符串处理的好题目,题中用到的相关知识点有:
求反串
求子串
字符串查找
求字符串长度
强烈推荐!!
11/30/2018
10