Download presentation
Presentation is loading. Please wait.
1
搜索算法入门 广度优先搜索 深度优先搜索 简单的搜索剪枝 wfzyl2007
2
搜索算法应用范围 广度优先搜索 深度优先搜索 不同的搜索方式和剪枝技巧的运用，会对程序效率产生巨大影响。
解决最优解问题，例如迷宫问题。 深度优先搜索 解决可行解问题，例如8皇后问题。 不同的搜索方式和剪枝技巧的运用，会对程序效率产生巨大影响。 搜索的过程，实际上是遍历一个解答树的过程。图中每个节点是一个搜索状态，有向边对应状态转移。凡是能转化为这一模型的问题都可以用搜索算法解决，只是时间效率存在问题。
3
广度优先搜索 按照广度优先的顺序遍历状态空间。 算法框架如下: //BreadthFirstSearch
InitialQueue( Queue ); Queue.push( startState ); While ( ! Queue.empty ) { currentState = Queue.front(); if( currentState == endState ) return result; tempState = extend ( currentState ); If( tempState is legal ) { Queue.push( tempState ); }
4
Boj 1017 Description 最近流行一个叫做Herbert的游戏，下面我们来看它的简化版：游戏地图是一个24*24的网格来表示。机器人Herbert的体积刚好占一个格子，每次机器人可以往上、下左、右四个方向移动。每个格子可能是以下几种情况中的一种：1：空格子，用‘*’表示，机器人可以随意经过。2：格子放有障碍物。用‘#’表示，机器人不能进入这个格子。3: 格子放有按钮。按钮分为两种，一种是白色的，用‘w’表示，机器人经过后将会得到加分。另外一种是黑色的，用‘b’表示。机器人经过后机器人将会毁坏。机器人的初始位置用‘s’表示。希望你能做一个程序判断当前的地图是否能得到所有的加分。 Input 第一行输入正整数T，表明有T组数据（0 < T < 20)。每一组数据是一个24*24的矩阵。 Output 如果能够得到所有的加分，则输出"YES"。否则输出"NO"。
5
这是一个最简单的迷宫问题。分析得出，’b’格子与’#’格子是等价的。我们只需要在读入时统计出所有’w’格子的数量N，再从起点’s’格子进行广度优先搜索，遍历得到所有可以到达的’w’格子数量m。
如果N==m，则‘YES’；否则‘NO’。 这是一个运用广搜最简单的例子，但我们发现处理时并不是那么简单。
6
广度优先搜索技巧 运用方向数组来辅助修改坐标 如何保存路径 上例中，我们要由一个状态向其上、下、左、右四个方向扩展。可以定义方向数组：
const int dx={ 0, 1, 0, -1}; const int dy={ -1, 0, 1, 0}; 如何保存路径 一般用一个结构体来记录广搜时的状态，如下所示： struct state{ int x, y, d; //int op, pre; }; 如果需要记录路径，我们在结构体中加入两个变量，op表示此次搜索的方向，而pre表示到达此状态的前一个状态在队列中的位置，初始状态的pre为-1。
7
对广搜进行优化 优化状态空间 优化存储空间 优化判重方式 优化搜索方式
如何最优地表示一个状态 优化存储空间 压缩存储技术 优化判重方式 Hash、Map的运用 优化搜索方式 正向搜索 or 反向搜索？ 优先队列广搜、A*、双向广搜 今天只是一个入门讲解，只在这里简单一提如何优化状态空间，有兴趣的同学可以去查找相关资料。
8
Poj1324 Holedox Moving 贪吃蛇的游戏相信大家都玩过，这个题也是类似的，题目要求蛇头能达点（1，1）。
9
条件n, m (1<=n, m<=20) 和 L (2<=L<=8)
同时地图上还有一些阻碍物。 蛇头不能碰到自己的身体，并且不能碰到阻碍物。
10
最好的算法，就是搜索，要求出最小的步数，并且可能有无解的情况，那么当然用广度优先搜索算法。
因为广度优先搜索需要判重，而判重就需要用到记录状态，但是这道题中最大的难点就是状态的记录。 因为我们需要记录的是蛇头的位置，还有蛇身的情况。
11
平时一般迷宫问题，我们用广度优先搜索的时候，一般就是用一个数组去保存状态。那这个题可以吗？
我们考虑最极端的情况，蛇的长度最大的时候有8段，我们如果要记录这8段的位置，位置的可能20*20=400，那么就可能会用到 400^8的空间，这样做可能吗？或者说这样有必要吗？
12
分析下去，我们会发现，如果蛇头的位置确定，那么蛇身可以从蛇头按４个方向一直走到蛇尾。
这样状态数只为 20 * 20 * (4)^7 = 一个的数组还是可以承受的。
13
推荐习题 普通BFS 优先队列BFS 启发式搜索 双向BFS BOJ1079、POJ1324、POJ3322、POJ3414
14
深度优先搜索 按照深度优先的顺序遍历状态空间。 算法框架如下： void search( curState ) {
if( curState == endState ) { save the result; return success; } if( curState is illegal ) { return fail; for( tmpState = extend( curState ) ) { search( tmpState );
15
Boj 1039 Description Input Output
遥远的Vitamin部落有着传奇的文化，他们已经知道，将一个数a相加若干次（或者0次，虽然他们并不知道0的存在）后，可以得到另外一个b，则他们称数a是数b的Vitamin因子。Vitamin族人认为：一个太少，三个太多，两个正好。因为他们认为“两个”是天神对他们的恩赐。所以在他们的祭祀天神的活动中，有一种舞蹈叫做“两个 舞”。这个舞蹈由N个漂亮的姑娘来表演，每个姑娘的头巾上会有一个数字（1到9），姑娘依次从幕后跳出来，每个时刻，已经出场的姑娘头巾上数字可以按出场 顺序用Vitamin记数法可以组成一个数，这个数只能有两个Vitamin因子。例如：有两个姑娘跳舞的时候，可以给第一姑娘编号为2，第二姑娘编为3。先是第一个姑娘出场，她的号码2有两个Vitamin因子。接着第二个姑娘上场了，她和第一个姑娘组成了数字23，也只有两个Vitamin因子。 Input 多组测试数据。每组数据只有一个整数N（1<= N <= 7），且占一行。数据以0结束（该0不用求解）。 表示有N个姑娘跳舞。 Output 每组输入对应的输出应在一个块内，即每组测试数据的输出后多输出一个空行，仅一个！从第一个姑娘开始，将每个姑娘的编号按Vitamin记数法可以得到一个数，将每组数据的输出按照从小到大输出。
16
这是一道简单的深度优先搜索和判素数的题目。
题目要求找出所有满足前m位（m=1…N）均为素数的N位数。 状态是当前找到前m位符合要求的数，处于搜索树的m深度处。用深度优先搜索，优先扩展m+1深度处的状态，直到扩展到N深度或者无解回溯。
17
简单的剪枝技巧 极端法剪枝 调整法剪枝 数学方法 在博弈问题中多采用的Alpha-Beta剪枝
通过前面的搜索已经得到一个较优值S’。发现当前状态扩展出来的值已经不可能比S’更好，故放弃当前状态的扩展。 调整法剪枝 通过对子树的比较剪掉重复子树和明显不是最有“前途”的子树。 数学方法 通过数学方法计算出扩展的上界或下界，适用范围有限。 在博弈问题中多采用的Alpha-Beta剪枝 这里只简单一提，有兴趣同学可以去查相关资料。
18
谢谢 Poj1324贪吃蛇问题更详细解答可以参考： 更多深入了解可以去看lrj黑书和算法导论。 我的联系方式 论坛ID：wfzyl2007
Similar presentations
