第五讲---搜索和动态规划

搜索与动态规划《基础》深度优先搜索深度优先搜索属于图算法的一种,英文缩写为DFS即DepthFirstSearch.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次.递归，回溯，暴力。就像走迷宫，走遍任何一条路径，碰到死路。走不了了，就回头找到最近的分叉路，走另一条。以此类推，直到找到出口。所以相当暴力，基本上比赛不会出太赤裸裸的暴力搜索。用暴力搜索的要小心的估算复杂度，不轻易写。递归#includeiostreamusingnamespacestd;intf(intx){if(x=1)return1;elsereturnf(x-1);}intmain(){intx;while(cinx)coutf(x)endl;return0;}树搜索到有@的点，当树层数稍微多时，指数级增长复杂度.#!((#)*$)!@(*#(条件剪枝！递归:回溯方法例：皇后问题QQQQ3.回溯方法()()3.回溯方法()()((1,1))Q3.回溯方法()()((1,1))((1,1)(2,3))QQ3.回溯方法()()((1,1))((1,1)(2,3))Q3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))QQ3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))QQQ3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))QQ3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q3.回溯方法()()((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))Q3.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))QQ3.回溯方法()()((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))QQQ3.回溯方法()()((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))QQQQ3.回溯方法递归的思想：当前状态目标状态gHdu2510符号三角形=2510符号三角形的第1行有n个由“+”和”-“组成的符号，以后每行符号比上行少1个，2个同号下面是”+“，2个异号下面是”-“。计算有多少个不同的符号三角形，使其所含”+“和”-“的个数相同。n=7时的1个符号三角形如下:++-+-+++----+-+++--++--+---+怎么做递归：dfs(introw,intval,intplus,intmin);建立一个数组，暴力填写+和-，最后判断是否合法。合法就num++。这个思路很容易想到，想到后马上看数据范围，n=24，貌似不大。暴力写写，挂了。打表吧。还是不行，跑不出结果怎么打表，囧剪枝！！计算出一共会有多少个+，这样一旦+或者-的数量超过这个数，就可以回溯了。n=24#includeiostreamusingnamespacestd;inta[]={0,0,0,4,6,0,0,12,40,0,0,171,410,0,0,1896,5160,0,0,32757,59984,0,0,431095,822229};intmain(){intn;while(cinn,n)coutna[n]endl;return0;}Pku1088滑雪=1088记忆化搜索,对于dfs(intx,inty)如果dp[x][y]==-1进行计算，不然返回dp[x][y]计算时,dp[x][y]=max(dfs(x-1,y),dfs(x+1,y),dfs(x,y-1),dfs(x,y+1))+1;(如果周围比它小的话)推荐题目：Foj：140817341543广度优先搜索bfsbreadth-firstsearch@14513211671615124*2820113917191018如果*想碰到@，需要多少步。DFS写写看吧。Bfs用队列。Structnode{Intx;Inty;Intnum;}Boolflag[100][100];Hdu3220Alice’sCube上海赛区的题目，清华10+分钟过的题目，全场100+多队，几乎所有的队伍都过的题目，但是做出来的速度却相差很多。40分钟内写出来，并一次ac的。Hdu3220，会的可以去写写。Bfs+位压缩。=3220题目大意：给定一个几何体，每个点都有一个值，0或者1，每次可以把线段相邻的两个点的值互换，问需要几步，可以让1-8号节点是0，而9到16号为1做法首先，肯定要很认真的看清哪些点是相邻的，为了提高ac率，要检查两三遍。比赛场上有人没用位压缩的，肯定超时了，后来跑了很久后，终于打表过。浪费很多时间。对于16个点，int有32位，我们可以令每一位对应好节点号，比如3就是0..011这样每次送入队列的只是一个数字，这个数字就能用16个点的信息，如果用结构体，里面再定义boolflag【16】，就会超时。做法未压缩的目标状态：256-1=255初始态：自己用二进制转十进制法转得到x；structnode{intnum;intzt;};用到stlqueue开始时s.num=0;s.zt=x;做法(伪代码)Q.push(s);While(!q.empty()){Tmp=q.front();Q.pop();该变一步，得到tmp2tmp2.num=tmp1.num+1,q.push(tmp2)；If(tmp2.zt=目标状态){打印num；break;}}广度优先搜索Bfs用在地图搜索的非常多。如何提高效率。以题目而定。常用：优先队列优化。就是（堆）例子：草地-2平地-1草地-2草地-2雪地-3平地-1平地-1雪地-3雪地-3雪地-3草地-2平地-1Bfs简介Bfs用队列的思想，先进先出。Hdu1242Rescue=1242做法两种1：记忆化bfs，用一张二维表，存到达每个点所要的最短步数，初始化为inf(无穷大);每次用bfs到达的步数如果小于该点的原值，更新，并入队。直到队列为空；2：优先队列，每次选取步数最少的点出来，第一次到达目标点的步数就是最小步数。Bfs用到的stl。#includequeueStructnode{intx,inty,intnum;}queuenodeq2;priority_queuenodeq1;可以自动选取优先级最高的点出来扩展。比如上题中的消耗体力最少的点出来扩展。提高效率。Priority_queue其实就是《数据结构》将会学到的“堆”，能在log级的复杂度内找到最小的值，并调整堆。自己写堆效率较高，代码量大。且复杂容易出错。一般情况下stl的这个函数效率也足够高了。很方便。结构体小于号重载后，每次选取步数最小的点出来。Bfs题目：Fzu1205Poj1724Hdu2267A*算法动态规划不得不说的例子：数字三角形动态规划与递归动态规划思想：求c(n,m);递归写法：intc(intn,intm){if(m==0)return1;if(m==1)returnn;if(n==m)return1;returnc(n-1,m-1)+c(n-1,m);}动态规划写法for(i=0;in;i++){for(j=0;j=i;j++){if(j==0||i==j)C[i][j]=1;elseC[i][j]=C[i-1][j]+C[i-1][j-1];}}区别动态规划往往效率很高。而递归写法，由于层层递归，速度很慢。当n，m=（30，15）的时候，得出结果就需要好几秒了，如果n，m=（100，50）发现时间上等的超出我们的耐性了。而动态规划只是100*50的数组处理，马上就有结果。动态规划，要想好动态规划的方程，几乎每场比赛都有1题。Fzu1004For(i=n;i=1;i--)For(j=1;j=I;j++)dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]);输出dp[0][0]不得不说的另一个例子：背包问题Hdu2602BoneCollector=26020-1背包题目模型：N个物体：两个属性：重量和价值如上：5个物体，背包容量10个重量5个物体的价值：12345重量54321如何选取其中的物体，使价值和最大，当然重量又不能超过背包的最大允许量。动态规划每次加入一个物体的考虑，只有取与不取的情况，保留最大值。弄懂思想代码很短。初次接触则不好懂n个物体，m的背包容量for(i=0;in;i++)for(j=m;j=w[i];j--)dp[j]=max(dp[j],dp[j-w[i]]+v[i]);无穷背包只要从小往大dp就行了for(i=0;in;i++)for(j=0；j=m;j++)dp[j]=max(dp[j],dp[j-w[i]]+v[i]);USACO2.2SubsetSums题目如下：对于从1到N的连续整集合合，能划分成两个子集合，且保证每个集合的数字和是相等的。举个例子，如果N=3，对于{1，2，3}能划分成两个子集合，他们每个的所有数字和是相等的：{3}and{1,2}这是唯一一种分发（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）如果N=7，有四种方法能划分集合{1，2，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。程序不能预存结果直接输出。解法：ints=n*(n+1)/2;if(s%2)cout0endl;for(i=1;i=n;i++)for(j=s;j=i;j--)dp[j]+=dp[j-i];cout(dyn[s]/2)endl;图论和动态规划Fzu1747ImpossibleMission=1747求哈密顿通路12344141213234位运算，比如3，位表示0011，为已经走过1号点和2号点的情况。定义二维数组dp[a][b],表示到a点，此时共走过b的状态的走的种数。假设已知dp[3][00101],Dp[2][00111],dp[4][01101],dp[5][10101]都要加上dp[3][00101];fzu动态规划Foj1