第五讲 搜索和动态规划ppt课件.ppt

《第五讲 搜索和动态规划ppt课件.ppt》由会员分享，可在线阅读，更多相关《第五讲 搜索和动态规划ppt课件.ppt（54页珍藏版）》请在三一办公上搜索。

1、搜索与动态规划基础,深度优先搜索,深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次.递归，回溯，暴力。就像走迷宫，走遍任何一条路径，碰到死路。走不了了，就回头找到最近的分叉路，走另一条。以此类推，直到找到出口。所以相当暴力，基本上比赛不会出太赤裸裸的暴力搜索。用暴力搜索的要小心的估算复杂度，不轻易写。,递归,#includeusing namespace std;int f(int x)if(xx)coutf(x)endl;return 0;,树,搜索到有的点，当树层数稍微

2、多时，指数级增长复杂度.,#,!,(,(,#,),*,$,),!,(,*,#,(,条件剪枝！,递归:回溯方法,例：皇后问题,3.回溯方法,(),(),3.回溯方法,(),(),(1,1),Q,3.回溯方法,(),(),(1,1),(1,1)(2,3),Q,Q,3.回溯方法,(),(),(1,1),(1,1)(2,3),Q,3.回溯方法,(),(),(1,1),(1,1)(2,3),(1,1)(2,4),Q,Q,3.回溯方法,(),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,Q,Q,3.回溯方法,(),(),(1,1),(1,1)(2,3),

3、(1,1)(2,4),(1,1)(2,4)(3.2),Q,Q,3.回溯方法,(),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,3.回溯方法,(),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),3.回溯方法,(),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(1,2),3.回溯方法,(),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(1,2),(1,2)(2,4),3.回溯方法,(),(),(1,

4、1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(1,2),(1,2)(2,4),(1,2)(2,4)(3,1),3.回溯方法,(),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(1,2),(1,2)(2,4),(1,2)(2,4)(3,1),(1,2)(2,4)(3,1)(4,3),3.回溯方法,递归的思想：,当前状态,目标状态g,Hdu 2510 符号三角形http:/,符号三角形的 第1行有n个由“+”和”-“组成的符号，以后每行符号比上行少1个，2个同号下面是”+“，2个异 号下面是”-“。计算有多少个

5、不同的符号三角形，使其所含”+“和”-“的个数相同。n=7时的1个符号三角形如下:+-+-+-+-+-+-+-+,怎么做,递归：dfs(int row,int val,int plus,int min);建立一个数组，暴力填写+和-，最后判断是否合法。合法就num+。这个思路很容易想到，想到后马上看数据范围，n=24，貌似不大。暴力写写，挂了。打表吧。还是不行，跑不出结果怎么打表，囧剪枝！计算出一共会有多少个+，这样一旦+或者-的数量超过这个数，就可以回溯了。,n=24,#include using namespace std;int a=0,0,0,4,6,0,0,12,40,0,0,171

6、,410,0,0,1896,5160,0,0,32757,59984,0,0,431095,822229;int main()int n;while(cinn,n)coutnanendl;return 0;,Pku 1088 滑雪,http:/x,int y)如果dpxy=-1 进行计算，不然返回dpxy计算时,dpxy=max(dfs(x-1,y),dfs(x+1,y),dfs(x,y-1),dfs(x,y+1)+1;(如果周围比它小的话),推荐题目：,Foj：140817341543,广度优先搜索bfsbreadth-first search,如果*想碰到，需要多少步。DFS写写看吧。Bf

7、s用队列。,Struct nodeInt x;Int y;Int num;Bool flag100100;,Hdu 3220 Alices Cube,上海赛区的题目，清华10+分钟过的题目，全场100+多队，几乎所有的队伍都过的题目，但是做出来的速度却相差很多。40分钟内写出来，并一次ac的。Hdu 3220，会的可以去写写。Bfs+位压缩。,http:/,题目大意：,给定一个几何体，每个点都有一个值，0或者1，每次可以把线段相邻的两个点的值互换，问需要几步，可以让1-8号节点是0，而9到16号为1,做法,首先，肯定要很认真的看清哪些点是相邻的，为了提高ac率，要检查两三遍。比赛场上有人没用位

8、压缩的，肯定超时了，后来跑了很久后，终于打表过。浪费很多时间。对于16个点，int 有32位，我们可以令每一位对应好节点号，比如3 就是0.011这样每次送入队列的只是一个数字，这个数字就能用16个点的信息，如果用结构体，里面再定义bool flag【16】，就会超时。,做法,未压缩的目标状态：256-1=255初始态：自己用二进制转十进制法转得到x；struct node int num;int zt;用到stl 开始时s.num=0;s.zt=x;,做法(伪代码),Q.push(s);While(!q.empty()Tmp=q.front();Q.pop();该变一步，得到tmp2 tmp

9、2.num=tmp1.num+1,q.push(tmp2)；If(tmp2.zt=目标状态)打印num；break;,广度优先搜索,Bfs 用在地图搜索的非常多。如何提高效率。以题目而定。常用：优先队列优化。就是（堆）例子：,Bfs 简介,Bfs 用队列的思想，先进先出。Hdu 1242 Rescuehttp:/,做法两种,1：记忆化bfs，用一张二维表，存到达每个点所要的最短步数，初始化为inf(无穷大);每次用bfs到达的步数如果小于该点的原值，更新，并入队。直到队列为空；2：优先队列，每次选取步数最少的点出来，第一次到达目标点的步数就是最小步数。,Bfs 用到的stl。,#include

10、Struct nodeint x,int y,int num;queueq2;priority_queueq1;可以自动选取优先级最高的点出来扩展。比如上题中的消耗体力最少的点出来扩展。提高效率。,Priority_queue,其实就是数据结构将会学到的“堆”，能在log级的复杂度内找到最小的值，并调整堆。自己写堆效率较高，代码量大。且复杂容易出错。一般情况下stl的这个函数效率也足够高了。很方便。结构体小于号重载后，每次选取步数最小的点出来。,Bfs题目：,Fzu 1205Poj 1724Hdu 2267,A*算法,动态规划,不得不说的例子：数字三角形,动态规划与递归,动态规划思想：求c(n

11、,m);递归写法：int c(int n,int m)if(m=0)return 1;if(m=1)return n;if(n=m)return 1;return c(n-1,m-1)+c(n-1,m);,动态规划写法,for(i=0;in;i+)for(j=0;j=i;j+)if(j=0|i=j)Cij=1;elseCij=Ci-1j+Ci-1j-1;,区别,动态规划往往效率很高。而递归写法，由于层层递归，速度很慢。当n，m=（30，15）的时候，得出结果就需要好几秒了，如果n，m=（100，50）发现时间上等的超出我们的耐性了。而动态规划只是100*50的数组处理，马上就有结果。动态规划，

12、要想好动态规划的方程，几乎每场比赛都有1题。,Fzu 1004,For(i=n;i=1;i-)For(j=1;j=I;j+)dpij+=max(dpi+1j,dpi+1j+1);输出dp00,不得不说的另一个例子：背包问题,Hdu 2602 Bone Collector http:/,0-1 背包,题目模型：N个物体：两个属性：重量和价值如上：5个物体，背包容量10个重量5个物体的价值：1 2 3 4 5重量 5 4 3 2 1如何选取其中的物体，使价值和最大，当然重量又不能超过背包的最大允许量。,动态规划,每次加入一个物体的考虑，只有取与不取的情况，保留最大值。弄懂思想代码很短。初次接触则不

13、好懂n个物体，m的背包容量for(i=0;i=wi;j-)dpj=max(dpj,dpj-wi+vi);,无穷背包,只要从小往大dp就行了for(i=0;in;i+)for(j=0；j=m;j+)dpj=max(dpj,dpj-wi+vi);,USACO2.2 Subset Sums,题目如下：对于从1到N的连续整集合合，能划分成两个子集合，且保证每个集合的数字和是相等的。举个例子，如果N=3，对于1，2，3能划分成两个子集合，他们每个的所有数字和是相等的：3and 1,2 这是唯一一种分发（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）如果N=7，有四种方法能划分集合1，2，

14、3，4，5，6，7，每一种分发的子集合各数字和是相等的:1,6,7 and 2,3,4,5 注 1+6+7=2+3+4+5 2,5,7 and 1,3,4,6 3,4,7 and 1,2,5,6 1,2,4,7 and 3,5,6 给出N，你的程序应该输出划分方案总数，如果不存在这样的划分方案，则输出0。程序不能预存结果直接输出。,解法：,int s=n*(n+1)/2;if(s%2)cout=i;j-)dpj+=dpj-i;cout(dyns/2)endl;,图论和动态规划,Fzu 1747 Impossible Mission http:/,求哈密顿通路,1,2,3,4 4 1 4 1 2 1 3 2 3,4,位运算，比如3，位表示0011，为已经走过1号点和2号点的情况。定义二维数组dpab,表示到a点，此时共走过b的状态的走的种数。假设已知dp300101,Dp200111,dp401101,dp510101都要加上dp300101;,fzu动态规划,Foj 1342Foj 1667Foj 1416,结束,谢谢,