PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

谨卫
5 years ago
Views:

1 搜索算法及其在 ACM 中的应用北京邮电大学 ACM 集训队

2 搜索算法分类 BFS DFS 普通 BFS 优先队列 BFS 双向 BFS A* 算法普通 DFS 迭代加深算法 IDA* 搜索的剪枝和优化

3 一. BFS 广度优先搜索最重要的四点状态空间是什么状态如何存储状态如何判重怎么搜索状态空间的优化状态存储的优化状态判重的优化搜索方式的优化

4 BFS 广度优先搜索的思想很简单 queue Q; Q.push( startstate ); While (! Q.empty ) { curstate = Q.front(); if( curstate == endstate ) return true; mark[curstate] = true; extstate = extend ( curstate ); If(!mark[extState] ) { Q.push( extstate ); } }

5 POJ2243 给定一个 8*8 的格子地图, 再给定初始点和终止点, 要求输出从初始点到达终止点的最少步数注意到格子地图的大小为 8*8

6 POJ3414 给两个桶, 两个桶的体积分别为 A 和 B, 要求用这个两个桶装出 C 体积的水, 如果可以的话就输出装法, 不可以的话就输出 impossibie. 我们发现 A, B 的最大值都不会超过 100, 并且是要求输出最少的步数和方法

7 共同点找到最少步数搜索范围的限制

8 广度优先搜索要求用最少的步数, 我们容易想到的就是广度优先搜索 ; 对于第一个题, 地图大小为 8*8, 因此我们搜索过程中可以使用 mark[8][8] 这样一个数组来标记已经搜索过的节点 ; 而对于第二道题, 两个桶的大小都不超过 100, 那么我们我们可以用一个二维数组 mark [ 100 ] [ 100 ] 标记重复的状态来判重, 并且保存起路径就可以了

9 小技巧方向数组广搜的时候, 一般使用方向数组来辅助坐标的修改, 例如 : const int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2}; const int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};

10 小技巧保存路径的方法一般用一个结构体来记录广搜时的状态, 如下所示 : struct state{ int x, y; int d, op; int pre; }; 如果需要记录路径, 我们在结构体中加入两个变量, op 表示此次搜索的方向, 而 pre 表示到达此状态的前一个状态在队列中的位置, 初试状态的 pre 为 -1

11 小技巧保存路径的方法则我们获取路径的方法为 ( 记录在数组 seq 中 ): void output(int k){ sn = 0; while(q[k].pre!= -1){ seq[sn++] = Q[k].op; k = Q[k].pre; } } 最后逆序打印 seq 即可

12 1. 状态空间的优化在确定使用广度优先之后我们需要仔细的估算状态的数量, 和规模, 如果规模太大, 超过了承受范围, 我们就需要试着去考虑缩小状态的规模

13 Poj1324 Holedox Moving 贪吃蛇的游戏相信大家都玩过, 这个题也是类似的, 题目要求蛇头能达点 ( 1, 1 )

14 Poj1324 Holedox Moving 条件 n, m (1<=n, m<=20) 和 L (2<=L<=8) n, m 为地图的行数和列数, L 为蛇的长度同时地图上还有一些阻碍物蛇头不能碰到自己的身体, 并且不能碰到阻碍物

15 Poj1324 Holedox Moving 最好的算法, 就是搜索, 要求出最小的步数, 并且可能有无解的情况, 那么当然用广度优先搜索算法因为广度优先搜索需要判重, 而判重就需要用到记录状态, 但是这道题中最大的难点就是状态的记录因为我们需要记录的是蛇头的位置, 还有蛇身的情况

16 Poj1324 Holedox Moving 平时一般迷宫问题, 我们用广度优先搜索的时候, 一般就是用一个数组去保存状态那这个题可以吗??? 我们考虑最极端的情况, 蛇的长度最大的时候有 8 段, 我们如果要记录这 8 段的位置, 位置的可能是 20 * 20=4 00, 那么就可能会用到 (400) ^ 8 的空间, 这样做可能吗? 或者说这样有必要吗?

17 Poj1324 Holedox Moving 分析下去, 我们会发现, 如果蛇头的位置确定, 那么蛇身可以从蛇头按 4 个方向一直走到蛇尾

18 Poj1324 Holedox Moving 这样状态数只为 20 * 20 * (4)^7 = 一个的数组还是可以承受的

19 2. 状态存储的优化有些问题的状态规模很小, 处理起来很简单, 但有些问题的状态比较复杂, 储存起来比较困难, 这个时候我们就要考虑一下如何表示一个状态

20 状态存储的优化按位存储对于那些包含多个对象的状态, 并不是都需要用多个 int 型整数或者字符串来表示 ; 比如一头猪, 每天的生活就是吃, 睡, 还有 Nature Calling, 因此我们可以简单地认为一头猪每天只有 3 种状态, 我们可以用一个字节来表示一头猪, 当然, 更简单的, 两个比特位就足以表示一头猪

21 状态存储的优化按位存储如果我们要表示 4 头猪的状态, 我们只需要使用一个单字节变量即可, 而不需要开一个 4 字节的字符串意义在于, 通过这样的手段, 我们能够压缩状态的存储空间 4 头猪的实际状态空间为 3*3*3*3, 如果使用 4 个字节的字符串来表示 4 头猪, 那么我们默认的存储空间应该为 256*256*256*256, 而如果用一个字节来表示, 我们需要的存储空间仅为 256, 已经很接近实际使用空间了子

22 状态存储的优化典型例子 POJ1753 给定一个 4*4 的黑白棋盘的初始状态, 判断能否通过满足一些给定的翻转规则, 使得所有棋面的颜色都一样, 如果可以, 输出最小步数

23 状态存储的优化典型例子那么, 每个棋子只有两种状态, 黑面朝上, 或者白面朝上 ; 因此我们可以用一个 bit 位来表示一颗棋子, 那么用 16 个 bit 位, 即可表示整个棋盘同时可以计算, 最多有 2^16 次方的状态数 ; 则标记数组应该为, bool mark[1<<16]

24 3. 状态判重的优化状态判重的方式 : 1. 数据规模小, 标记数组 ( 本质上也是最简单的 Hash 表 ); 2. 数据规模打, 带有冲突解决的 Hash 表, Map@STL

25 状态判重的优化在考虑 Hash 表来判重时因该首先考虑哪些没有冲突的 Hash 方案, 比如前面的倒水题, 我们只需要开个 100*100 的 bool 标记数组就可以解决问题, 所也不用考虑其他方案了但是对于有些问题使用没有冲突的 Hash 表超过了储存空间的上限, 这时可以自己写 Hash 的冲突解决函数, 也可以使用 STL 中的 map 来代替 Hash;

26 1) 标记数组标记数组, 如果状态的规模比较小, 或者在储存空间限制内, 我们可以简单地使用标记数组, 比如最初两道例题中的, bool mark [100][100] 等技巧, 如何初始化标记数组 ( 灵感来源于 yicou)

27 小技巧如何初始化 visit 使用情况 : 多组测试用例一般我们为了判重, 仅仅开成 bool 型数组, 我们可以开成 char 型数组, 这样, 初始化数组为全 0 对于当前测试用例 cas, 则对于状态 i, mark[i] < cas 表示未被扩展 ; 而 mark[i] == cas 则表示已被扩展如果测试用例比较多, 则可以开成 short int 数组

28 2) Hash 表 Hash 函数的选择解决冲突的办法

29 2) Hash 表 8 数码问题, POJ1077 3*3 的方格图上, 其中 8 个格子中有不同的数字, 分别为 1~8, 一个格子为空, 每次可以将空格子与其相邻格子互换, 求一系列的操作, 使得方格中的数字从左至右从上至下按顺序排列

30 2) Hash 表此题的状态空间可以优化至存储空间能表示的范围内, 但此刻我们尝试用解决冲突的办法来完成 ; 状态显然可以用一个整数来表示, 比如我们的最终状态可以用来表示 ( 注意, 这就是一种 Hash 函数 ), 那么如果我们直接使用标记数组, 那么数组大小需要为 10^10 次方, 显然不实际

31 2) Hash 表到达最终状态有很多种方式, 我们不需要将所有状态都扩展一次, 我们只需要找到一组解, 因此, 我们可以开设一个大小为 PRIME= 的数组, 我们大胆假设在这个范围中, 我们肯定能搜索到一组解问题出来了, 由于状态空间是 10^10, 我们必须把状态通过 Hash 函数映射到中去, 但我们可能会遇到冲突, 这时候就需要冲突解决函数

32 解决冲突的简单办法 void get_hash(int k, int d){ while(v[k]) k = (k + 1)%PRIME; hash[k] = d; v[k] = 1; return; } bool find_hash(int k, int d){ while(v[k] && hash[k]!= d) k = (k + 1)%PRIME; if(!v[k] hash[k]!= d) return false; else return true; }

33 解决冲突的简单办法 Map STL 提供了强大的类库, 包括数据结构和算法我们可以使用其中的 Map 容器来判重 ; Map 的本质是一颗平衡树 ; 具体实现

34 普通 BFS 相关题目推荐 POJ1324 POJ3322 POJ3414

35 3. BFS 搜索方式的优化 1) 基于优先队列的 BFS 2) A* 算法 3) 双向广搜

36 1) 基于优先队列的搜索对于前面所提到的问题, 我们都是希望得到最小步数, 而广度优先搜索刚好就是逐层搜索的算法, 因此, 只要我们搜索到了目标, 那么得到的肯定是最小步数本质上来看, 每次都应该选择当前未扩展状态中损耗最小的状态进行扩展, 对于前述问题, 损耗即指步数那对于一般性问题呢?

37 POJ3635 题中, 需要找出从初始点到达终止点最少需要的花费根据我们前面的结论, 我们这里的损耗即是花费, 即, 我们每次要扩展花费最少的状态, 那最后如果到达了终止状态, 所得到的花费, 自然也是所有到达终止状态路径中最少的

38 POJ3635 那么如何每次获得当前未扩展状态中最小的状态呢? 能否想到一种数据结构?

39 POJ3635 当然可以, 那就是使用堆基于堆实现的队列, 我们称之为优先队列其实前述的普通 BFS, 我们也可以将它们看成是以当前步数为 key 值的优先队列, 不是吗? 而如果我们以深度作为 Key 值, 那就是普通的 DFS 了本题如何扩展状态, 同学们可以自己思考一下

40 基于优先队列的 BFS priority_queue Q; while(!q.empty()){ curstate = Q.top(); Q.pop(); while(mark[curstate] &&!Q.empty()){ curstate = Q.top(); Q.pop(); } if(curstate == endstate) return true; mark[curstate] = true; extstate = extend(curstate); if(!mark[extstate]) Q.push(extState); } return false;

41 优先队列 BFS 的易错点 mark[curstate] = true; extstate = extend(curstate); if(!mark[extstate]) Q.push(extState); 当需要标记一个状态已经搜索过时, 需要在扩展此状态时进行标记, 而不是在初次寻找到这个状态时标记, 请问为什么?

42 相关题目推荐 POJ3635 POJ2908

43 2) A* 算法又称启发式搜索 ; 我们前面提到过一个状态的损耗值, 我们设损耗函数 g(n) 表示状态 n 的损耗值我们引入一个启发函数 h(n) ; 同时定义估价函数 f(n) = g(n) + h(n) 作为我们扩展时的 key 值, 即每次找 f(n) 最小的状态进行扩展

44 启发式函数 h(n) 因此问题的关键在于启发式函数定义, 启发式函数可以定义为状态 n 到达终止状态的损耗值的下界比如我们定义 h(n) = 0, 这是完全正确的, 因为我们前面所有的例子, 不就是 h(n) = 0 的代表吗? 由于 h(n) 是状态 n 到达终止状态的损耗值下界, 那么 f(n) 一定是起始状态到达终止状态损耗值的下界, 因此我们每次选择 f(n) 最小的状态进行扩展, 能够保证最后能够得到的损耗值是最小的

45 启发式函数 h(n) 设计更好的启发式函数, 目的就是让我们以更快的速度向终止状态扩展启发式函数的设计需要具体情况具体分析例子, 推箱子, 八数码

46 Poj1475:Pushing Boxes

47 推箱子的启发函数我们想要找到一个状态到达最终状态的损耗值的一个下界如何才能得到这个下界? 如果不考虑箱子的存在, 你能想到吗?

48 推箱子的启发函数显然, 如果不考虑箱子的存在, 一个下界就是, 当前状态里最终状态的最短距离 ( 注意, 在这里不是曼哈顿距离, 因为还要考虑石墙的存在 ) 那么, 显然的, 任何一个状态到 target 的最短距离就可以作为这个状态的启发式函数, 并且对于只有一个箱子的情况而言, 这还是一个很不错的启发式函数我们可以通过预处理, BFS 一遍, 得到每个状态的启发式值

49 八数码问题启发式函数的设计大家思考一下

50 A* 算法的实现只需要把优先队列 BFS 中的损耗值换成 f(n) 即可每次扩展 f(n) 最小的状态, 对于新扩展到的状态, 要计算其估价函数的值

51 A* 算法的易错点在 A* 搜索中, 用 f[x], g[x], h[x] 分别表示状态 x 的总估价, 已经完成的深度, 剩余估价且 f[x] = g[x] + h[x]; 以前一直将比较函数写成 return f[x] > f[y];

52 A* 算法的易错点当 f[x] == f[y] 时, 错误就产生了 ( 除非对于 f[x] == f[y] 是 g[x] == g[y] 的充分条件 ) 原因是, 如果 f[x] == f[y], g[x] < g[y] 现假设 x, y 都可以通过代价相同代价 d 到达状态 z 而 x, y 的优先级相同, 如果先搜 g[y], g[z] = g[y] + d 就不是最小值, 因为有 g[x] < g[y] 正确的比较应该这样写 : if (f[x] == f[y]) return g[x] > g[y]; return f[x] > f[y];

53 相关题目推荐 POJ1077 POJ1475

54 3) 双向 BFS 有些问题按照广度优先搜索法则扩展结点的规则, 既适合顺序, 也适合逆序, 于是我们考虑在寻找目标结点或路径的搜索过程中, 初始结点向目标结点和目标结点向初始结点同时进行扩展, 直至在两个扩展方向上出现同一个子结点, 搜索结束, 这就是双向搜索过程出现的这个同一子结点, 我们称为相交点, 如果确实存在一条从初始结点到目标结点的最佳路径, 那么按双向搜索进行搜索必然会在某层出现相交, 即有相交点, 初始结点一相交点一目标结点所形成的一条路径即是所求路径

55 POJ1915 Knight Moves 给定一个棋盘, 然后给定两个起始点和终点, 输出按照马的走法, 从起始点到达重点的最少步数 ; 我们可以使用普通 BFS, 从起始点开始搜索, 扩展到终点结束 ; 如果我们能从起点和终点同时开始搜索, 那么扩展出来的搜索树也会更小, 因此也能更快找到所需解

56 双向 BFS 大体程序流程 now = 0; Q.push(st); RQ.push(ed); mark[st] = true; Rmark[ed] = true; while(!q.empty() &&!RQ.empty()){ while(q.front().step == now){ nextstate = extend(q.front); if(mark[nextstate]) continuel if(rmark[nextstate]) return true; } while(rq.front().step == now){ nextstate = extend(rq.front); if(rmark[nextstate]) continuel if(mark[nextstate]) return true; } now++; }

57 易错点, now 变量的作用双向广搜中, 两边的扩展方式必须都是按层扩展, 否则会出现和最优解擦肩而过的情况 : 如图所示, 设边权值全部为 1, 黑色边表示已经扩展的, 蓝色边表示左边最后一次扩展的由于左边的节点没有按层扩展 ( 否则红线和蓝线在同一层扩展, 已找到解 ), 这时如果开始右边的搜索, 有可能先搜到的是绿色线所表示的路径, 这个解比最优解 ( 红线 ) 大 1

58 双向 BFS 推荐题目 POJ1915 POJ3523

C++ 程序设计告别 OJ1 - 参考答案 MASTER 2019 年 5 月 3 日 1

C++ 程序设计告别 OJ1 - 参考答案 MASTER 2019 年 5 月 3 日 1 C++ 程序设计告别 OJ1 - 参考答案 MASTER 2019 年月 3 日 1 1 INPUTOUTPUT 1 InputOutput 题目描述用 cin 输入你的姓名 ( 没有空格 ) 和年龄 ( 整数 ), 并用 cout 输出输入输出符合以下范例输入 master 999 输出 I am master, 999 years old. 注意 "," 后面有一个空格,"." 结束,