day3搜索优化方法-曹利国-noip培训

搜索优化方法长沙市一中曹利国什么是搜索？搜索是对一个问题不断地寻找可行方案，然后找到最优的可行方案。搜索称为“通用解题法”，但是大局部情况下搜索所需的时间复杂度很高。搜索一般分为：深度优先搜索〔DFS〕和广度优先搜索〔BFS〕搜索关键字状态状态转移优先搜索遍历枚举深度优先搜索广度优先搜索剪枝状态状态转移状态：是对问题在某一时刻的进展情况的数学描述状态转移：是问题从一种状态转移到另一种状态的操作。搜索过程：通过状态转移不断地寻找目标状态或最优状态。深度优先遍历深度优先搜索遍历：遍历类似树的先根遍历，它是一个递归过程，可称述为：首先访问一个顶点Vi〔开始为初始点〕，并将其标记为已访问过，然后从Vi的一个未被访问可到达的邻接点出发进行深度优先搜索遍历，当Vi所有可到达的邻接点均被访问过时，那么退回上一个顶点Vk，从Vk的另一个未被访问过的邻接点出发进行深度优先搜索遍历。深度优先搜索深度优先搜索：按照深度优先搜索遍历所有的状态。实现方式可以采用递归或者栈来实现深度优先搜索递归实现的框架：VoidDFS(longstate,longdepth){for(longi=1;i<=count(state);i++)newstate=make(state,i);if(answer)printans;elseif(depth<maxdepth)DFS(newstate,depth+1)}深度优先搜索深度优先搜索可以看成按深度优先顺序遍历一颗树：一般深度优先搜索要用到回溯。回溯算法适用问题：求解搜索问题一般的深度优先搜索问题都要用到回溯算法，每次不能遍历下去时，回溯到前一个点，继续遍历。例题1走迷宫问题〔高级本〕有一个m*n格的迷宫(表示有m行、n列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这m*n个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，那么输出相应信息(用-1表示无路)。例题1分析我们不难想到可以采用深度优先搜索。我们用深度优先搜索扩展一个点时，向4个方向按照深度优先搜索进行扩展，但是注意一些到过的点不能再次经过。当到达目标点时不扩展下去，并且计数器加一，输出答案，回溯。当前这个点不能继续扩展下去时，回溯到上一节点，扩展下去。深度优先搜索的优化尽可能减少生成的节点数定制回溯边界条件，剪掉不可能得到最优解的子树运用记忆化的方法，使得一些遍历过的子树不要重复遍历

减少所遍历的状态总数例题2：定货单〔ceoi试题〕某商店经理已将所有的货物按它们的标号的字母顺序进行了分类。所有的标号首字母相同的货物被存储在同一仓库中，该仓库也用该字母进行标记。在某天中，经理接到并登记了许多定货单，每张定货单仅需一种货物你道了该天经理所需处理的所有定货单，但你不知道它们的登记顺序。计算出所有可能的访问仓库的方法，来为经理解决该天所有的定货要求。输入文件ORDERS.IN中仅有一行，包含所有所需货物的标号〔一个随机的顺序〕。每一种货物是用它标号的首字母来表示的，只使用英文小写字母。定货单的数目不超过200输出：输出文件ORDERS.OUT要包含经理访问仓库的所有可能顺序。例如Order.inorder.outbbjdbbdjbbjdbdbjbdjb bjbdbjdbdbbjdbjbdjbbjbbdjbdbjdbb分析因为题目要求我们输出所有可能的登记顺序，而数据的范围也不大，不难看出它是一个搜索题目。由于方案数可能会比较大，如果要保存下所有的方案也是没有必要的，因此我们宜采用深搜而放弃广搜。一般来讲，要确定某个顺序第I位上的字母，我们是从“a“到“z”循环，依次查找，看哪个字母还可以再选，当可选字母的比较少，且可选字母中每一个字母又可以选较屡次时，每一重循环就有很多扫描是多余的。我们可以对这种情况作如下优化：在输入完毕后，先统计出各种字母的总个数，并且将可选的字母按字典顺序依次放入到一个字符串数组中〔每个字母最多放一次〕，搜索的时候，我们将从“a”到“z”的循环改为从头到尾扫描字符串数组，由于该字符串数组中的各字母都是可选的，所以我们每扫到一个字母，就将它插入到当前方案的序列中，并将它的可选次数减1如果一个字母已经不能再选〔可选次数为0〕，那么暂时将它从字符串数组中删去，等到当前过程递归调用完毕后再将其插入该字符串数组。这样一来，就可以保证每一次循环扫描到的字母都是可选的，搜索中几乎没有了多余的运算搜索剪枝在很多情况下，我们已经找到了一组比较好的解。但是计算机仍然会义无返顾地去搜索比它更“劣”的其他解，搜索到后也只能回溯。为了防止出现这种情况，我们需要灵活地去定制回溯搜索的边界。剪枝1、正确性：剪去的“枝条”不包含最优答案2、准确性：在保证第一条原那么的情况下，尽可能的剪去更多不包含最优答案的枝条3、高效性：通过剪枝要能够更快的接近到达最优解常用剪枝可行性剪枝最优性剪枝例题3：计算机网络连接〔gdoi〕要将n(n<=30)台计算机连成网络，连接方法：去除首尾两台计算机与一台计算机相连以外，其他计算机只与两台计算机相连。连接的长度那么为计算机连接的电缆的长度。求：一种连接方式，使需要电缆的长度最短分析〔优化一〕假设目前搜索到了一组解，电缆总长度为kx，那么，如果说以后搜索到的连接方法〔不一定是最终连接方法〕的连接长度>=kx，那么这个方案的总长度一定不小于kx，那么，就不必要搜索下去了，直接换下一个结点继续搜索。优化二路径A1-A2-…An与路径An-An-1-…A1这两条路径是一个“正反”的关系，本质上是相同的，于是我们可以规定起点始的下标总是小于终点的下标优化三假设路径的A-B-C-D的长度<A-C-B-D的长度，那么包含A-C-B-D路径的路径的长度一定不是最短。回溯边界在深度优先搜索的过程当中，往往有很多走不通的“死路”。假设我们把这些“死路”排除在外，不是可以节省很多的时间吗？打一个比方，前面有一个路径，别人已经提示：“这是死路，肯定不通”，而你的程序仍然很“执着”地要继续朝这个方向走，走到头来才发现，别人的提示是正确的。这样，浪费了很多的时间。针对这种情况，我们可以把“死路”给标记一下不走，就可以得到更高的搜索效率。例题：N皇后问题采用一般的回溯，就是每一行的每个格子放与不放都搜索一下，实际上，在放置了(1,1)这个皇后，再把皇后放置在(2,1)就是毫无意义的：前面一个皇后一定能攻击到它。为了防止这种情况，我们这样做：走了一个棋子以后，把它的“势力范围”给圈出来，并且告诉以后的皇后：这里不能放置。例题4：Betsy‘sTour〔USACO〕一个正方形的镇区分为N2个小方块〔1<=N<=7〕。农场位于方格的左上角，集市位于右下角。贝茜穿过小镇，从左上角走到左下角，刚好经过每个方格一次。写一个程序，对于给出的N值，计算贝茜从农场走到集市有多少种唯一的路径例题4：Betsy‘sTour〔USACO〕这一题是一道经典题目，我们开始想到用搜索来解决：我们搜索一条在N*N的矩阵中从点〔1，1〕到点〔1，N〕的路径，然后判断这个路径是不是遍历完所有的点。但是当N比较小时，答案可以很快的出来，可是当N比较大时，求出答案的时间会很大。例题4：Betsy‘sTour〔USACO〕我们可以想到用可行性剪枝来优化。剪枝一：对于某一个没有访问过的点〔不包括终点〕，至少有两个点〔没有访问的点或贝茜所在的点〕在他附近。因为一个没有访问过的点要被访问到，一定要一进一出，所以必须要在他附近有两个点，才能满足点被全部访问的要求。例题4：Betsy‘sTour〔USACO〕剪枝二：

我们继续分析，当这个地图被分为了两个或多个连通块时，能不能全部访问？答案很显然，不能！我们就可以再加一个优化，判断当前状态表示的地图是不是只有一个连通块。这样减少了很多不符合题意的状态。例题3：Betsy‘sTour〔USACO〕对于上面的剪枝，每一次行动都要对所有的格子进行判断。其实我们知道每一次行动后只会对其附近的格子有影响，那么我们不妨只判断附近格子在操作之后是不是符合题目要求。对于第一个剪枝我们很容易的判断完，但对于第二个剪枝，怎么判断呢？例题3：Betsy‘sTour〔USACO〕例题4：Betsy‘sTour〔USACO〕从上面的那个图中可以知道，当出现了上图的三种情况后，必定是出现了两个以上的连通块，不是最后的结果通过这一个优化，我们又进一步的减少了时间复杂度，解决了这一个问题。提示：这一题可以考虑用状态压缩的动态规划来做。例题5：最少乘法次数由x开始，通过最少的乘法次数得出x^n，其中n为输入数据。例题5：最少乘法次数这题是一道很经典的题目，开始我们会想到动态规划来求解，但是用动态规划求解时会出现后效性，所以只能想用别的方法。我们考虑用搜索，设第一层a[1]=1，那么搜索到第i层时a[i]的值在a[i-1]+1到n的值里面选择可以到达的值。当a[i]=n时，答案为i-1。但是这样搜索可能会搜到很多状态，使得时间复杂度很大，怎么办？例题5：最少乘法次数我们不妨考虑用最优化剪枝，现在乘的次数不比当前答案优时，我们不用搜索下去，因为从这个状态搜索下去的答案肯定不比最后的优。这个判断虽然很好，但是剪枝得不够彻底，我们继续想，如果当前的a[i]用最少的乘法到n，这个答案不比当前答案优时，那就没有必要搜索下去，我们就可以预处理从p(=a[i])乘到n，至少要乘多少次。这样我们能够很好的解决这问题。例题5：最少乘法次数但是当p>=n/2时，p至少要乘以1次就可以到达n，这样对于这种情况，前面的剪枝的效果很很低。我们不难发现，如果p>=n/2时，其实相乘的那些数都小于n/2，而那些乘的数之前也计算出来了，就可以考虑用动态规划来求最优解，这样对于p无论在那个值时，都有很好的剪枝来优化。例题6：彩票问题：彩票上的数字：1,2,…,M彩民的选择：A1,A2,…,An，其中Ai属于1,2,…,M每人只能买一张彩票，每人彩票选择都不同抽出两个自然数X和Y。如果1/A1+2/A2+…+1/An=X/Y，那么中奖〔获取纪念品〕。输入：N，M，X，Y输出：所需准备的纪念品数量1≤X,Y≤100，1≤N≤10，1≤M≤50。输入数据保证输出结果不超过105。深度优先搜索的优化从上面两题我们了解到可行性剪枝和最优性剪枝的运用和技巧。其实除了上面的一些剪枝外，还有其他的剪枝技巧。分析：对于每个数，有选和不选两种可能性，显然可以建立如下模型：

x1/1+x2/2+x3/3+…+xm/m=X/Y

其中，xi=0或者1(1<=i<=m)x1+x2+x3+…+xm=n逐个搜索xiO(2m)x1/1+x2/2+x3/3+…+xm/m=X/Y同时乘以m!*Y通分。令Ti=m!*Y/i(1<=i<=m),T0=m!*X那么：T1x1+T2x2+T3x3+…+Tmxm=T0这就变成了一个01背包问题。每个包裹的体积是Ti，箱子体积T0从M个中选N个，填满箱子。

求方案数。如何优化？？T1x1+T2x2+T3x3+…+Tmxm=T0如何剪枝？f[i,T]表示为了满足T1x1+T2x2+…+Tmxm=T，最少要让多少个xi取1。f[i,T]=min{f[i-1,T],f[i-1,T-Ti]+1}按照xm,xm-1,xm-2,…,x1的顺序搜索。假设xp~xm都已经取定，令S=Tpxp+Tp+1xp+1+…+Tmxm，L=xp+xp+1+…+xm，如果f[p-1,T-S]+L>N，那么就可以回溯，不必继续搜索了。T~O(m!)。太大了！f数组开不下，时间上也不允许。动态规划的思想，空间矛盾太大。抓住矛盾：解决空间问题！T太大了，可不可以想方法把它变小呢？同余T1x1+T2x2+T3x3+…+Tmxm=T0f[i,T]表示为了满足T1x1+T2x2+…+Tmxm=T，至少要让多少个xi取1。f[i,T]=min{f[i-1,T],f[i-1,T-Ti]+1}T1x1+T2x2+T3x3+…+Tmxm=T0f[i,T]表示为了满足(T1x1+T2x2+…+TmXm)modP=T，至少要让多少个xi取1。f[i,T]=min{f[i-1,T],f[i-1,(T-Ti)modP]+1}0<=T<P按照xm,xm-1,xm-2,…,x1的顺序搜索。假设xp~xm都已经取定，令S=Tpxp+Tp+1xp+1+…+Tmxm，L=xp+xp+1+…+xm，如果f[p-1,(T-S)modP]+L>N，那么就可以回溯，不必继续搜索了。剪枝效果有所削弱但是空间复杂度降到了O(mP)，这里P可以任取。广度优先遍历广度优先搜索遍历：类似树的按层遍历，其过程为：首先访问初始点Vi，并将其标记为已访问过，接着访问Vi的所有未被访问过可到达的邻接点Vi1、Vi2……Vit，并均标记为已访问过，然后再按照Vi1、Vi2……Vit的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依此类推，直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。广度优先搜索队列实现的框架：VoidBFS(longinitialstate){que.in(initialstate);While(!(que.empty())){state=que.out();for(longi=1;i<=count(state);i++){newstate=make(state,i);if(answer(newstate))printans;elseque.in(newstate);}}}广度优先搜索对于状态数很多时，广度优先搜索可以采用循环队列或动态链表来处理。一般的广度优先搜索题目会用到hash表来优化判重。例题7：黑白棋游戏(高级本)黑白棋游戏的棋盘由4×4方格阵列构成。棋盘的每一方格中放有1枚棋子，共有8枚白棋子和8枚黑棋子。这16枚棋子的每一种放置方案都构成一个游戏状态。在棋盘上拥有1条公共边的2个方格称为相邻方格。一个方格最多可有4个相邻方格。在玩黑白棋游戏时，每一步可将任何2个相邻方格中棋子互换位置。对于给定的初始游戏状态和目标游戏状态，编程计算从初始游戏状态变化到目标游戏状态的最短着棋序列。例题5：黑白棋游戏(高级本)这题我们可以想到用深度优先搜索来做，但是如果下一步出现了以前的状态怎么办？直接判断时间复杂度的可能会有点大，这题的最优解法是用广度优先搜索来做我们就可以有初始状态按照广度优先搜索遍历来扩展每一个点，这样到达目标状态的步数一定是最优的〔步数的增加时单调的〕。但问题是如果出现了重复的情况我们就必须要判重，但是朴素的判重是可以到达状态数级别的，其实我们可以考虑用hash表来判重。例题5：黑白棋游戏(高级本)Hash表：思路是根据关键码值进行直接访问。也就是说把一个关键码值映射到表中的一个位置来访问记录的过程。在Hash表中，一般插入，查找的时间复杂度可以在O〔1〕的时间复杂度内搞定。对于这一题我们可以用二进制值表示其hash值，最多2^16次方，所以我们开个2^16次方的表记录这个状态出现没有，这样可以在O〔1〕的时间复杂度内解决判重问题例题7：黑白棋游戏(高级本)进一步考虑：从初始状态到目标状态，必定会产生很多无用的状态，那还有什么优化可以减少这时间复杂度？我们可以考虑把初始状态和目标状态一起扩展，这样如果初始状态的某个被扩展的点与目标状态所扩展的点相同时，那这两个点不用扩展下去，而两个扩展的步数和也就是答案。例题5：黑白棋游戏(高级本)上面的想法是双向广度优先搜索：就像上图一样，少扩展了很多不必要的状态广度优先搜索的优化从上面一题可以看到我们用到了两个优化：Hash表优化；双向广搜优化；注：一般的广度优先搜索用这两个优化就足以解决。例题8：pku1729在一个N*N(N<=30)的地图上，有A和B两个人，地图上的一些地方为空地，一些地方有障碍不能通过。在每一个时刻A和B必须向四个方向移动(‘N’,’E’,’W’,’S’)，并且AB两人彼此特别讨厌对方，他们希望在移动的时候尽可能的离对方远，现在知道两个人分别的起点和终点。求出一条使AB到达终点的路径，并且在途中AB间最近的距离最远，在此根底上使AB尽快到达终点。例题8分析题目是要你使首先是要AB都到达终点，然后是要路径中AB离得尽可能的远，同时AB要尽快到达。我们很容易想到用广度优先搜索来解决问题，也很容易想到用hash表来表示，为hash[Xa,Ya,Xb,Yb,t]记录当A在〔Xa，Ya〕，B在〔Xb，Yb〕且时间经过t时AB的最近距离是多少，或者hash[Xa,Ya,Xb,Yb,d]记录当A在〔Xa，Ya〕，B在〔Xb，Yb〕且最近距离为d时AB所有的最少时间是多少例题8：pku1729但是这样表示的状态很大，有可能到达N^6级别，已经超过了所能承受的空间限制。继续分析，AB两个人的距离最多只会相差N^4=810000种可能，我们不妨采用二分最近距离的方法来求解。这是二分次数最多只需要log2810000<20次即可例题8：pku1729我们重新定义hash值，假设当前二分到最近距离为x，那么hash[Xa,Ya,Xb,Yb]记录A在〔Xa，Ya〕，B在〔Xb，Yb〕时，且最近距离大于x时的最少时间。我们成功的把状态量降低为(N^4)，已经很好的解决这空间问题，而时间复杂度为O(N^4*20)，很好的解决了这个问题。总结：我们通过二分的方法使空间和时间复杂度都降低了很多。深度优先搜索和广度优先搜索深度优先搜索广度优先搜索遍历方式深度优先搜索遍历广度优先搜索遍历所用数据结构栈队列一般优化最优性剪枝可行性剪枝Hash判重双向搜索讨论：什么时候用深度优先搜索好？什么时候用广度优先搜索好？A*算法介绍A*算法前，先介绍下估价函数和贪心搜索估价函数：在解决问题的时候常常会估计状态离目标状态到底有多接近，进而对多种方案进行选择。放在搜索中来，可以有一个状态的估价函数来估计它到目标状态的距离。定义h(s)表示当前状态s到目标状态的估价。贪心搜索：像广度优先搜索一样用一个优先队列按其h(s)来储存待扩展，但是由于h(s)不准确，所以不能保证是最优解。A*算法和贪心算法很类似，它不是按h值来计算，而是按另外一个函数值f使得f是由启始状态到目标状态的估价。设g(s)为目标状态到达现在状态s的代价，那么f(s)=g(s)+h(s)。因为对于任意两个状态s1,s2满足h(s1)<=h(s2)+w(s1,s2);W(s1,s2)s1转移到s2的代价。那么对于状态s1,s2,且s2是s1