浅谈搜索入门.doc

《浅谈搜索入门.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、浅谈搜索入门WQ@YCOI零前言搜索是01beginners的必修课，也是在齐类比赛中十分通用的技巧。己近三年辽宁省的NOIP成绩为例，我们假设一名选手掌握了基本的搜索和模拟算法，那么TA的成绩将如下所示(均达到辽宁省省线)：2010：100+30+30+50=2102009：100+50+30+40=2202008：100+100+30+10：=240下面就简单谈谈各种常见的搜索并另附了-些可供练习的好题。一深度优先搜索深度优先搜索常'用于求可行解、解的总数或者非深度最优的垠优解。它可以轻松地用递归实现，当然可能也有人热衷于非递归形式。递归框架如下：proceduredfs(dep)beg

2、inif得到可行解thenbeginendelseif到达最底层thenexitelsefori:=to可向下扩展结点个数dobegin更新结点信息dfs(dep+1);回溯节点信息end;end;二广度优先搜索广度优先搜索常用于求深度最优的最优解。它一•般用队列来实现(如果为了节省空间可以选择収模的方式使用循环队列，如最短路的SPFA算法)。英框架如下：procedurebfs;beginwhile(head<=tail)dobeginfori:=1to可向下扩展结点个数dobegininc(tail);记录新结点end;inc(head);end;end;三判重问题搜索过程中常常遇到搜索

3、冋同一种情况的吋候，就像你可以乘坐154从育才北校去南校，也可以打车过去，总之到那之后你该干嘛干嘛！如果搜索到这样一种情况，你即便再往下搜也只是重复了昨天的故事，全是无用功。这时,你就需要想办法判断你是是否冋到了过去。我们通常开一个布尔数组來判重。主程序中：fillchar(vis,sizeof(vis)r0);搜素过程中：ifnotvis［这个结点］thenbeginvis［这个结点］:=true;扩展这个结点end忽略这个结点四迭代加深搜索我很喜欢这个迭代加深，我认为它平衡了深搜和广搜的优缺点。它既像BFS那样高效又像DFS那样容易实现。迭代加深尤其适用于记录结点信息比较麻烦的求最深度优

4、解的题目。它得到的第一个可行解必然最优。其框架如下：主程•序中：dep_limit:=1;while未得到最优解dobegindfs_id(l);inc(dep_limit);end;搜素过程中：proceduredfs_id(dep)beginif得到最优解thenbeginendelseif至4达最底层or(dep>dep_limit)thenexitelsefori:=lto可向下扩展结点个数dobegin更新结点信息dfs(dep+);回溯结点信息end;end;可能有人有疑问：你不刚说完无用功的事儿么！这么來冋重新搜索不是一堆无用功么！在这里我解释一下：如果你把搜索过程想象成在一棵

5、树上的遍历，那么如果一棵树比另一棵树多一层那么你要搜索的数据量就是翻了-•帝。五搜索的优化在做搜索题目时，我会反问自C这么儿个问题，也是通常的优化思路。在做最后提到的那些题时可以体会到这些问题。1.以什么作为搜索对象？2.可否进行对解的预处理（动规、随机化……）？3.釆用什么搜索顺序？4.能否忽略明显得不到合理解的结点？（可行性剪枝）5.能否忽略明显得不到最优解的结点？（最优化剪枝）六抓住比赛的BUG比赛和考试不同于联系和学习，我们不得不承认功利至上，所以耍掌握比赛的技巧。首先，我來谈谈打农。它常常用于函数类询问，比如：n皇后解的总数、NOIP2008的火柴棒等式……实际操作就是在比赛时跑出

6、所有输入対应的解后，建立常量数纽。其次是卡时技巧。方法是初始化计数器为0,在每次访问结点是计数器加1即可，当达到（吋限*9*10^9）时，输出当前最优解、当前解总数或者无解时的特判。最后说一下算法设计效率。我们期望的是得分效率高。记住，2个60分算法优于1个100分算法！也就是说，满分算法不一定是完满算法！七推荐题目名称考察点来源提交生日蛋糕强力剪枝NOI1999POJ1190木棒问题强力剪枝+搜索顺序ACM中欧POJ1011奶牛加密术强力剪枝+搜索顺序USACOUSACO4.1.4质数方阵强力剪枝10194USACO4.3.2靶心数独搜索顺序NOIP2009RQNOJ521Betsy的旅行

7、强力剪枝USACOUSACO5.4.4拼球问题细心搜索CEOI1998POJ1725BLOXORZ细心搜索POJO加如5月赛POJ3322八数码问题康托判重10196USACO3.2.5汽车问题搜索顺序10194POJ1167骑士聚会强力剪枝+预处理10198USACO3.3.313皇后对称判重经典问题USACO1.5.4N皇后可行解启发式修补经典问题POJ3239十五数码问题启发函数经典问题POJ1077