搜索算法及其在ACM中的应用 admin 谢科 搜索算法分类 BFS 普通

1、搜索算法及其在ACM中的应用,admin 谢科,搜索算法分类,BFS 普通BFS 优先队列BFS 双向BFS A*算法 DFS 普通DFS 迭代加深算法 IDA* 搜索的剪枝和优化,一. BFS广度优先搜索,最重要的四点 状态空间是什么 状态如何存储 状态如何判重 怎么搜索 状态空间的优化 状态存储的优化 状态判重的优化 搜索方式的优化,BFS,广度优先搜索的思想很简单。 queue Q; Q.push( startState ); While ( ! Q.empty ) curState = Q.front(); if( curState = endState ) return true;

2、markcurState = true; extState = extend ( curState ); If( !markextState ) Q.push( extState ); ,POJ2243,给定一个8*8的格子地图，再给定初始点和终止点，要求输出从初始点到达终止点的最少步数。 注意到格子地图的大小为8*8,POJ3414,给两个桶，两个桶的体积分别为A和B，要求用这个两个桶装出C体积的水，如果可以的话就输出装法，不可以的话就输出impossibie. 我们发现A，B的最大值都不会超过100，并且是要求输出最少的步数和方法。,共同点,找到最少步数 搜索范围的限制,广度优先搜索,要求

3、用最少的步数，我们容易想到的就是广度优先搜索； 对于第一个题，地图大小为8*8，因此我们搜索过程中可以使用mark88这样一个数组来标记已经搜索过的节点； 而对于第二道题，两个桶的大小都不超过100，那么我们我们可以用一个二维数组mark 100 100 标记重复的状态来判重，并且保存起路径就可以了。,小技巧方向数组,广搜的时候，一般使用方向数组来辅助坐标的修改，例如： const int dx = -2, -2, -1, -1, 1, 1, 2, 2; const int dy = -1, 1, -2, 2, -2, 2, -1, 1;,小技巧保存路径的方法,一般用一个结构体来记录广搜时的状

4、态，如下所示： struct state int x, y; int d, op; int pre; ; 如果需要记录路径，我们在结构体中加入两个变量，op表示此次搜索的方向，而pre表示到达此状态的前一个状态在队列中的位置，初试状态的pre为-1。,小技巧保存路径的方法,则我们获取路径的方法为（记录在数组seq中）： void output(int k) sn = 0; while(Qk.pre != -1) seqsn+ = Qk.op; k = Qk.pre; 最后逆序打印seq即可。,1. 状态空间的优化,在确定使用广度优先之后 我们需要仔细的估算状态的数量，和规模，如果规模太大，超过

5、了承受范围，我们就需要试着去考虑缩小状态的规模。,Poj1324 Holedox Moving,贪吃蛇的游戏相信大家都玩过，这个题也是类似的，题目要求蛇头能达点（1，1）,Poj1324 Holedox Moving,条件n, m (1=n, m=20) 和 L (2=L=8) n, m 为地图的行数和列数，L为蛇的长度 同时地图上还有一些阻碍物。 蛇头不能碰到自己的身体，并且不能碰到阻碍物。,Poj1324 Holedox Moving,最好的算法，就是搜索，要求出最小的步数，并且可能有无解的情况，那么当然用广度优先搜索算法。 因为广度优先搜索需要判重，而判重就需要用到记录状态，但是这道题中

6、最大的难点就是状态的记录。 因为我们需要记录的是蛇头的位置，还有蛇身的情况。,Poj1324 Holedox Moving,平时一般迷宫问题，我们用广度优先搜索的时候，一般就是用一个数组去保存状态。那这个题可以吗？ 我们考虑最极端的情况，蛇的长度最大的时候有8段，我们如果要记录这8段的位置，位置的可能是 20 *，那么就可能会用到（）8的空间，这样做可能吗？或者说这样有必要吗？,Poj1324 Holedox Moving,分析下去，我们会发现，如果蛇头的位置确定，那么蛇身可以从蛇头按个方向一直走到蛇尾,Poj1324 Holedox Moving,这样状态数只为 20 * 20 * (4)7

7、 =6553600 一个的数组还是可以承受的。,2. 状态存储的优化,有些问题的状态规模很小，处理起来很简单，但有些问题的状态比较复杂，储存起来比较困难，这个时候我们就要考虑一下如何表示一个状态 。,状态存储的优化按位存储,对于那些包含多个对象的状态，并不是都需要用多个int型整数或者字符串来表示； 比如一头猪，每天的生活就是吃，睡，还有Nature Calling，因此我们可以简单地认为一头猪每天只有3种状态，我们可以用一个字节来表示一头猪，当然，更简单的，两个比特位就足以表示一头猪。,状态存储的优化按位存储,如果我们要表示4头猪的状态，我们只需要使用一个单字节变量即可，而不需要开一个4字节

8、的字符串。 意义在于，通过这样的手段，我们能够压缩状态的存储空间。 4头猪的实际状态空间为3*3*3*3，如果使用4个字节的字符串来表示4头猪，那么我们默认的存储空间应该为256*256*256*256，而如果用一个字节来表示，我们需要的存储空间仅为256，已经很接近实际使用空间了,状态存储的优化典型例子,POJ1753 给定一个4*4的黑白棋盘的初始状态，判断能否通过满足一些给定的翻转规则，使得所有棋面的颜色都一样，如果可以，输出最小步数。,状态存储的优化典型例子,那么，每个棋子只有两种状态，黑面朝上，或者白面朝上； 因此我们可以用一个bit位来表示一颗棋子，那么用16个bit位，即可表示整

9、个棋盘。 同时可以计算，最多有216次方的状态数； 则标记数组应该为，bool mark116,3. 状态判重的优化,状态判重的方式： 1. 数据规模小，标记数组（本质上也是最简单的Hash表）； 2. 数据规模打，带有冲突解决的Hash表，MapSTL,状态判重的优化,在考虑Hash 表来判重时因该首先考虑哪些没有冲突的Hash 方案，比如前面的倒水题，我们只需要开个100*100的bool标记数组就可以解决问题，所也不用考虑其他方案了。 但是对于有些问题使用没有冲突的Hash表超过了储存空间的上限，这时可以自己写Hash的冲突解决函数，也可以使用STL中的map 来代替Hash;,1) 标

10、记数组,标记数组，如果状态的规模比较小，或者在储存空间限制内，我们可以简单地使用标记数组，比如最初两道例题中的，bool mark 100100等。 技巧，如何初始化标记数组,小技巧如何初始化visit,使用情况：多组测试用例。 一般我们为了判重，仅仅开成bool型数组，我们可以开成char型数组，这样，初始化数组为全0。 对于当前测试用例cas，则对于状态i，marki cas表示未被扩展；而marki = cas则表示已被扩展。 如果测试用例比较多，则可以开成short int数组。,2) Hash表,Hash函数的选择 解决冲突的办法 MapSTL,2) Hash表,8数码问题， POJ

11、1077 3*3的方格图上，其中8个格子中有不同的数字，分别为18，一个格子为空，每次可以将空格子与其相邻格子互换，求一系列的操作，使得方格中的数字从左至右从上至下按顺序排列。,2) Hash表,此题的状态空间可以优化至存储空间能表示的范围内，但此刻我们尝试用解决冲突的办法来完成； 状态显然可以用一个整数来表示，比如我们的最终状态可以用123456789来表示（注意，这就是一种Hash函数），那么如果我们直接使用标记数组，那么数组大小需要为1010次方，显然不实际。,2) Hash表,到达最终状态有很多种方式，我们不需要将所有状态都扩展一次，我们只需要找到一组解，因此，我们可以开设一个大小为P

12、RIME=999983的数组，我们大胆假设在这个范围中，我们肯定能搜索到一组解。 问题出来了，由于状态空间是1010，我们必须把状态通过Hash函数映射到999983中去，但我们可能会遇到冲突，这时候就需要冲突解决函数。,解决冲突的简单办法,void get_hash(int k, int d) while(vk) k = (k + 1)%PRIME; hashk = d; vk = 1; return; bool find_hash(int k, int d) while(vk ,解决冲突的简单办法Map,STL提供了强大的类库，包括数据结构和算法。 我们可以使用其中的Map容器来判重； M

13、ap的本质是一颗平衡树； 具体实现,普通BFS相关题目推荐,POJ1324 POJ3322 POJ3414,3. BFS搜索方式的优化,1) 双向广搜 2) A*算法,1) 双向BFS,有些问题按照广度优先搜索法则扩展结点的规则，既适合顺序，也适合逆序，于是我们考虑在寻找目标结点或路径的搜索过程中，初始结点向目标结点和目标结点向初始结点同时进行扩展，直至在两个扩展方向上出现同一个子结点，搜索结束，这就是双向搜索过程。 出现的这个同一子结点，我们称为相交点，如果确实存在一条从初始结点到目标结点的最佳路径，那么按双向搜索进行搜索必然会在某层出现“相交”，即有相交点，初始结点一相交点一目标结点所形成

14、的一条路径即是所求路径。,POJ1915Knight Moves,给定一个棋盘，然后给定两个起始点和终点，输出按照马的走法，从起始点到达重点的最少步数； 我们可以使用普通BFS，从起始点开始搜索，扩展到终点结束；如果我们能从起点和终点同时开始搜索，那么扩展出来的搜索树也会更小，因此也能更快找到所需解。,双向BFS大体程序流程,now = 0; Q.push(st); RQ.push(ed); markst = true; Rmarked = true; while(!Q.empty() ,易错点，now变量的作用,双向广搜中，两边的扩展方式必须都是按层扩展，否则会出现和最优解擦肩而过的情况：

15、如图所示，设边权值全部为1，黑色边表示已经扩展的，蓝色边表示左边最后一次扩展的。由于左边的节点没有按层扩展（否则红线和蓝线在同一层扩展，已找到解），这时如果开始右边的搜索，有可能先搜到的是绿色线所表示的路径，这个解比最优解(红线)大1。,双向BFS推荐题目,POJ1915 POJ3523,2) A*算法,又称启发式搜索； 我们前面提到过一个状态的损耗值，我们设损耗函数g(n)表示状态n的损耗值。 我们引入一个启发函数h(n)； 同时定义估价函数f(n) = g(n) + h(n)作为我们扩展时的key值，即每次找f(n)最小的状态进行扩展。,启发式函数h(n),因此问题的关键在于启发式函数定义

16、，启发式函数可以定义为状态n到达终止状态的损耗值的下界。 比如我们定义h(n) = 0，这是完全正确的，因为我们前面所有的例子，不就是h(n) = 0的代表吗？ 由于h(n)是状态n到达终止状态的损耗值下界，那么f(n)一定是起始状态到达终止状态损耗值的下界，因此我们每次选择f(n)最小的状态进行扩展，能够保证最后能够得到的损耗值是最小的。,启发式函数h(n),设计更好的启发式函数，目的就是让我们以更快的速度向终止状态扩展。 启发式函数的设计需要具体情况具体分析。 例子，推箱子，八数码,八数码问题启发式函数的设计,大家思考一下,A*算法的实现,只需要把优先队列BFS中的损耗值换成f(n)即可。 每次扩展f(n)最小的状态，对于新扩展到的状态，要计算其估价函数的值。,A*算法的易错点,在A*搜索中，用fx, gx, hx分别表示状态x的总估价，已