(HDUACM2010版_11)搜索入门

统计信息：根据“信息学初学者之家”网站的统计， Ural(俄罗斯的Ural州立大学的简称，有名的Ural Online Problem Set 就是该校的系统)的题目类型大概呈如下的分布：搜索动态规划贪心构造约10% 约15% 约5% 约5% 计算几何纯数学题数据结构约5% 约20% 约5%2014-4-27

图论约10% 其它约25%4

杭电 ACM

引言“算法中最基本和常用的是搜索，这里要说的是，有些初学者在学习这些搜索基本算法是不太注意剪枝，这是十分不可取的，因为所有搜索的题目给你的测试用例都不会有很大的规模，你往往察觉不出程序运行的时间问题，但是真正的测试数据一定能过滤出那些没有剪枝的算法。实际上参赛选手基本上都会使用常用的搜索算法，题目的区分度往往就是建立在诸如剪枝之类的优化上了。 ”

——摘自《ACM竞赛之新人向导》2014-4-27 5

杭电 ACM

什么是搜索算法呢？搜索算法是利用计算机的高性能来有目的地穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。

搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。

2014-4-27

杭电 ACM

本讲主要内容

二分搜索三分搜索 DFS BFS(略)

2014-4-27

杭电 ACM

第一部分：二分查找

假设给出若干个(可以很多)有序的整数，请查找某个元素是否存在，比如——请查找以上数列中是否存在某个整数(比如25), 若有，请输出其位置，否则请输出NO~2014-4-27 8

2 3 4 5 6 8 12 20 32 45 65 74 86 95 100

杭电 ACM

第一部分：二分查找2 3 4 5 6 8 12 20 32 45 65 74 86 95 100

head

mid

tail

再次提醒：二分查找的前提—— 数据的单调性2014-4-27 9

杭电 ACM

思考：

1、在一百万个元素里查找某个元素大约需要比较多少次？

2、时间复杂度：O(logN)

2014-4-27

杭电 ACM

二分查找-例题1

HDOJ-2199

给出方程： 8*x4 + 7*x3 + 2*x2 + 3*x + 6 = Y 其中，实数Y满足 (fabs(Y) <= 1e10) 请输出x在区间[0,100]的解，结果精确到小数点后4位。2014-4-27 11

杭电 ACM

题目分析

常规暴力枚举？当测试数据足够多->效率低下指定区间内的单调性(如何证明?) 推荐方法：二分求解

2014-4-27

杭电 ACM

二分查找-参考代码1

//HDOJ-2199 #include <iostream> #include <cmath> using namespace std; double Y; double l, r, m; double f( double x ) { return 8*pow(x, 4.0) + 7*pow(x, 3.0) + 2*pow(x, 2.0) + 3*x + 6;} int main() { int t; scanf("%d", &t ); while( t-- ) { scanf("%lf", &Y ); if( f

(0) <= Y && Y <= f(100) ) { l = 0; r = 100; while( r - l > 1e-6 ) { m = (l + r) / 2; double ans = f(m); if( ans > Y ) { r = m - 1e-7; }else l = m + 1e-7; } printf("%.4lf\n", (l + r) / 2 ); }else printf("No solution!\n"); } }

2014-4-27

杭电 ACM

二分查找-例题2

HDOJ-2899

给出函数： F(x) = 6*x7 + 8*x6 + 7*x3 + 5*x2 - y*x 其中，实数y满足 (0<y < 1e10) 请输出x在区间[0,100]时函数F(x)的最小值，结果精确到小数点后4位。2014-4-27 14

杭电 ACM

题目分析

指定区间内是否满足单调性? 显然不满足->不能直接二分满足凸性？如何证明？极值点的特点？是否可以二分？15

2014-4-27

杭电 ACM

二分查找-参考代码2

//HDOJ-2899 #include <stdio.h> #include <math.h> const double eps = 1e-8; double y; double cal(double x){ return 42.0*pow(x,6.0)+48.0*pow(x,5.0)+21.0*pow(x,2.0)+10.0*x; } double ans(double x){ return 6.0*pow(x,7.0)+8.0*pow(x,6.0)+7.0*pow(x,3.0)+5.0*pow(x,2.0)-y*x; } int main(){ int T; double f,l,mid; scanf("%d",&T); while(T--){ scanf("%lf",&y); if(cal(100.0)-y<=0.0){ printf("%.4lf\n",ans(100.0)); continue; } f=0.0,l=100.0; while(l-f>eps){ mid=(f+l)/2.0; if(cal(mid)-y<0.0){ f=mid; }else{ l=mid; } } printf("%.4lf\n",ans(mid)); } return 0;

2014-4-27

杭电 ACM

新问题

如果函数满足凸性特点，但是——求导不方便！该如何处理？

2014-4-27

杭电 ACM

三分查找(Ternary Search)

2014-4-27

杭电 ACM

三分查找(Ternary Search)

2014-4-27

杭电 ACM