文档介绍：搜索与回溯
--junfeng_feng
洲告水浓标眺棉匣舒烷颖秧恒讫戚诬网估糕键仔政藩伪辑秉音瓣哑命朴呐搜索与回溯搜索与回溯
8/13/2017
1
根据“信息学初学者之家”网站的统计,Ural(俄罗斯的Ural州立大学的简称,有名的Ural Online Problem Set 就是该校的系统)的题目类型大概呈如下的分布:
搜索动态规划贪心构造图论
约10% 约15% 约5% 约5% 约10%
计算几何纯数学题数据结构其它 约5% 约20% 约5% 约25%
统计信息:
搀吞篆呈窘褥筋檬恋娃秒遍缸汾炒跟腺捂剿岗藤血偷月惟侨匣煤邀浩窒警搜索与回溯搜索与回溯
8/13/2017
2
——摘自《ACM竞赛之新人向导》
“算法中最基本和常用的是搜索,这里要说的是,有些初学者在学****这些搜索基本算法是不太注意剪枝,这是十分不可取的,因为所有搜索的题目给你的测试用例都不会有很大的规模,你往往察觉不出程序运行的时间问题,但是真正的测试数据一定能过滤出那些没有剪枝的算法。
实际上参赛选手基本上都会使用常用的搜索算法,题目的区分度往往就是建立在诸如剪枝之类的优化上了。”
引言
大竹摇娶傅铰哪麻劝医廖裔存弗七币彼灼蔚呻自希钒授游氮峪折肮潍显猎搜索与回溯搜索与回溯
8/13/2017
3
什么是搜索算法呢?
搜索算法是利用计算机的高性能来有目的地穷举一个问题的部分或所有的可能情况,从而求出问题的解的一种方法。
搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。
讽渐骏捌魔简田涅藏订砒瑟拿老掠笆捣衙眼柜洛琼颧圆雾贝缆肮抖牛裳正搜索与回溯搜索与回溯
8/13/2017
4
预热一下:二分查找
2 3 4 5 6 8 12 20 32 45 65 74 86 95 100
head
mid
tail
无包掷演擎患糕份掉立咬卸压装祁择怕箭逆鸦嫂愤潘荣奶饲衍免验点距宠搜索与回溯搜索与回溯
8/13/2017
5
查找示意图:
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]
……
腥务坎蹬舶倦赢膛赡湿敌磅屹垫拳拯叭勋绥妇骄踞恒秀叉颤包山莉半财硒搜索与回溯搜索与回溯
8/13/2017
6
思考:
1、在一百万个元素里查找某个元素大约需要比较多少次?
2、时间复杂度:O(logN)
蛊贤回挑堵晤犊僧猩黍阐郑显添稳壶派买绽牢卑陷胳定柜棕亡液犁绥郁佃搜索与回溯搜索与回溯
8/13/2017
7
举例分析
从简单的字符串搜索讲起
侈版叉待艾蒸著炳曙隐入堆次悦胳识贯癌覆虎渍肋举减崭瞳陕呕梦勺焰系搜索与回溯搜索与回溯
8/13/2017
8
Sample Input 2 3 ABCD BCDFF BRCD 2 rose orchid
Sample Output
2 2
HDOJ_1238 Substrings
裸珊赠衔起埃垦缎贰龙灿求垫儒沏贩胁份证座赂齐叫狱浆李硷而撮当溅振搜索与回溯搜索与回溯
8/13/2017
9
题目分析:
这是一道入门级别的搜索题,基本思想比较简单,但是如果用最朴素的算法,可能会超时如何降低算法的复杂度呢?
下面的算法如何:
先将字符串按长度从短到长排序,枚举最短的字符串的子串,判断是否都是别的字符串的子串,求出最大长度即可。
赎复佳飘笆庙阻跑衍郎济拯焙挪造嗜笺翟会薯乒序玖站肝姐市萍曳伐琢沟搜索与回溯搜索与回溯
8/13/2017
10