算法合集之《信息学竞赛中搜索问题的常见优化技巧》._信息学竞赛算法 - CSDN文库

信息学竞赛

需积分: 10 185 浏览量更新于2023-03-16 评论 1 收藏 978KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

2006 年全国信息学冬令营讲座

信息学竞赛中搜索问题的常见优化技巧

重庆一中黄晓愉

【摘要】结合例题分析归纳了信息学竞赛中解决搜索问题所常用的思考方法与解题方法，从深度

优先搜索和广度优先搜索两个方面探讨了提高程序效率的适用技巧。

【关键词】１信息学；２搜索顺序；３搜索对象；４ Hash 表 5 剪枝。

在信息学竞赛中解决搜索问题通常采用两种方法进行，即：深度优先搜索和广

度优先搜索。

一、深度优先搜索的优化技巧

我们在做题的时候，经常遇到这类题目——给出约束条件，求一种满足约束条

件的方案，这类问题我们叫它“约束满足”问题。对于约束满足问题，我们通常可以从

搜索的顺序和搜索的对象入手，进而提高程序的效率。

搜索的顺序及对象：

　　在解决约束满足问题的时候，题目给出的约束条件越强，对于搜索中的剪枝就

越有利。之所以深度优先搜索的效率在很大程度上优于穷举，就是因为它在搜索过

程中很好的利用了题目中的约束条件进行剪枝，达到提高程序效率的目的。

显然，在同样的一棵搜索树中，越在接近根接点的位置利用约束条件剪枝效果

就越好。如何在搜索中最大化的利用题目的约束条件为我们提供剪枝的依据，是提

高深度优先搜索效率的一个很重要的地方。而不同的搜索顺序和搜索对象就直接影

响到我们对于题目约束条件的运用。

下面，我们就从搜索的顺序和搜索的对象两方面来探讨一下不同的方法对程序

效率的影响。

（1）搜索顺序的选择：

我们先来看一道比较简单的题目： (zju1937)

已知一个数列 a0,a1......am 其中

a0 = 1

am = n

a0 < a1 < a2 < ... < am-1 < am

对于每个 k(1<=k<=m),ak=ai+aj (0 <= i, j <= k-1)，这里 i 与 j 可以相等。

现给定 n 的值，要求 m 的最小值（并不要求输出）,及这个数列的值(可能存在

多个数列,只输出任一个满足条件的就可以了)。

分析　由于 a

k

=a

i

+a

j

(0<=i,j<k),所以我们在搜索的过程中可以采用由小到大搜索

数列的每一项的搜索顺序进行试算。在一般搜索的时候我们习惯于从小到大依次搜

索每个数的取值，但是在这到题目中按照这样的顺序搜索编程运算其结果（效率）

十分不理想：

1

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余6页未读，立即下载

评论0

zhaicong123

粉丝: 0
资源: 2

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈