《和搜索跳舞.ppt》由会员分享，可在线阅读，更多相关《和搜索跳舞.ppt（60页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、和搜索跳舞和搜索跳舞Dancing with SearchBy Barty嘛搜索o当清晨我们刚起床，急匆匆地寻找某一只袜子的时候，我们会怎么找？n我们可以翻箱倒柜，将所有内含物都整出来，然后一个个的判断它们是否为所需的袜子n我们可以闭上眼睛，随意抓起来一个东西，然后睁开眼睛看看它是不是袜子n我们可以先看柜子，再看柜子里的盒子A，再看盒子A里的盒子B，再看n我们还可以估计袜子有可能在哪些位置，按照可能性排序，先找最有可能的地方比如枕头下面何谓搜索o上面那个例子告诉我们：o当我们遇到一个没有数学模型能够与之对应的时候，我们就要去“搜索”！当然，搜索也是有很多的方法的。o因为最终结果是存在的，我们始
2、终相信：总能够搜索到结果！只是也许我们需要等一会才会算出结果怎么搜索o枚举法当我们事先知道结果或者某约束条件的范围的时候，如果范围不是很大，我们就用枚举法。o回溯法当我们不知道求解的过程中会走到哪里，但是目的明确，步与步之间都有一定的相似关系的时候，我们采用回溯法。枚举法o枚举方式直译枚举二分枚举o枚举对象枚举约束条件枚举结果值o枚举优化减少枚举范围降低枚举维度直译枚举o这种枚举方法思考量很小，但是通常时间效率很低，多用于数据规模较小、结果范围容易确定的题目。【例题】侦探推理侦探推理o明明同学最近迷上了侦探漫画柯南并沉醉于推理游戏之中，于是他召集了一群同学玩推理游戏。游戏的内容是这样的，明明的
3、同学们先商量好由其中的一个人充当罪犯（在明明不知情的情况下），明明的任务就是找出这个罪犯。接着，明明逐个询问每一个同学，被询问者可能会说：o证词中出现的其他话，都不列入逻辑推理的内容。明明所知道的是，他的同学中有N个人始终说假话，其余的人始终说真。现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一凶手只有一个！个！例题分析o这道题的结果的范围十分明显，而且范围很小，我们就可以在此时应用枚举法。o我们想出了两种枚举方式：枚举谁说假话枚举谁是凶手o显然，枚举凶手要简单得多：因为“凶手只有一个！”o当然，还要枚举今天是周几。o下面给出程序(枚举部分)：ofori:=1tom
4、doofort:=1to7doobeginofillchar(pd,sizeof(pd),0);oflag:=true;oforj:=1tomdoofork:=1tomdooiftdj,k0thenobeginoif(tdj,k=1)=(k=i)thenobeginoifpdj=0thenpdj:=1oelseifpdj=-1thenflag:=false;oendoelsebeginoifpdj=0thenpdj:=-1oelseif(pdj=1)thenflag:=false;oend;oend;oforj:=1tomdoifdtj0thenoifdtjtthenobeginoifpdj=
5、0thenpdj:=-1oelseif(pdj=1)thenflag:=false;oendoelsebeginoifpdj=0thenpdj:=1oelseif(pdj=-1)thenflag:=false;oend;oifflagthenobeginoa:=0;b:=0;oforj:=1tomdoifpdj=1theninc(a)oelseifpdj=-1theninc(b);oif(b=n)and(a=m-n)thenobeginowriteln(namei);ohalt;oend;oend;oend;owriteln(Impossible)二分枚举o二分枚举运用的是结果的单调性：即当i
6、满足时，对于j(1=j=j=i)也都满足o这种枚举方法往往用于求满足条件的最大或最小结果值。o这种枚举方法常常和回溯法综合使用，枚举结果值，回溯验证是否可行。(DFS-ID)【例题】电话网络o由于地震使得连接汶川县城电话线全部损坏，假如你是负责将电话线接到震中汶川县城的负责人，汶川县城周围分布着N(1N1000)根按1.N顺次编号的废弃的电话线杆，任意两根电话线杆间都没有电话线相连。一共P(1P10000)对电话线杆间可以拉电话线，其余的由于地震使得无法被连接。第I对电话线杆的两个端点分别为Ai,Bi，它们间的距离为Li（1Li1000000）。数据中保证每对（Ai,Bi）最多只出现1次。编号
7、为1的电话线杆已经接入了全国的电话网络，整个县城的电话线全部连到了编号为N的电话线杆上。也就是说，你的任务仅仅是找到一条将1号和N号电话线杆连接起来的路径，其余的电话线杆并不一定连入电话网络。电信公司决定支援灾区免费为汶川县城连接k(0kn)对由你制定的电话线杆。对于此外的那些电话线，需要为它们付费，总费用等于其中最长的电话线的长度（每根电话线仅连接一对电话线杆）。如果需要连接的电话线杆不超过k对，那么总支出为0.请你计算一下，将电话线引到震中汶川县城最少需要在电话线上花多少钱？o输入格式：输入文件的第一行包含三个用空格隔开的整数：N,P,K第二行到第P+1行：每行分别都为三个用空格隔开的整数
8、：Ai,Bi,Li输出格式：输出文件中仅包含一个整数，表示在这项工程上的最小支出。如果任务不可能完成，则输出-1；输入样例：571125314248323529347456输出样例：4例题分析o问题总结：n求MAX，使得1N的一条路径上满足：o边长大于或等于MAX的边的数量不超过Kn求满足条件的MAX的最小值例题分析o乍一看这题，会让我们无从下手o直接深搜？由于N=1000，预计会很容易超时o然而又没有对应的数学模型o因而，我们想到了枚举MAXo为什么呢？因为如果MAX满足，那么MAX+1显然也一定满足o故而我们可以运用二分枚举来解决这道题例题分析o那么，具体如何运用二分枚举？o对于这道题，可
9、以简单地将二分枚举的上下界限定：0最大边长o然后对于每一次判断MAX是否成立，可将图内所有边长改为0(边长=MAX)o再求1N最短路是否=k即可o问题解决！枚举的优化o优化有两种方式：限制枚举的范围、降低枚举的维度。o限制枚举的范围要充分利用题目中的条件，可以优化时间效率，但效果不明显。o降低维度往往是我们要重点采取的措施！枚举降维o何谓降维？n就是将循环的层数减少。o降维的方式n往往通过递推关系，由其他参量或限制因素求得某一参量的值，从而求得结果。o降维的效果是很显著的！【例题】吃西瓜吃西瓜o背景SubRaY有一天得到一块西瓜,是长方体形的.题目描述SubRaY发现这块西瓜长m厘米,宽n厘米
10、,高h厘米.他发现如果把这块西瓜平均地分成m*n*h块1立方厘米的小正方体,那么每一小块都会有一个营养值(可能为负,因为西瓜是有可能坏掉的,但是绝对值不超过200).现在SubRaY决定从这m*n*h立方厘米的西瓜中切出mm*nn*hh立方厘米的一块小西瓜(一定是立方体形,长宽高均为整数),然后吃掉它.他想知道他最多能获得多少营养值.(0=mm=m,0=nn=n,0=hh=h.mm,nn,hh的值由您来决定).换句话说,我们希望从一个m*n*h的三维矩阵中,找出一个三维子矩阵,这个子矩阵的权和最大.o数据范围对于30%的数据,h=1,1=m,n=10对于全部的数据,1=h=32,1=m,n=5
11、0,保证h=m,n输入格式首行三个数h,m,n(注意顺序),分别表示西瓜的高,长,宽.以下h部分,每部分是一个m*n的矩阵,第i部分第j行的第k个数表示西瓜第i层,第j行第k列的那块1立方厘米的小正方体的营养值.输出格式SubRaY所能得到的最大营养值oExampleInputo234o4128o05-484o3019o2149o1017o3128oExampleOutputo45例题分析o这道题看似简单：不就是求个和嘛！o不过如果用我们平常用的求和方法求最大值，复杂度是很“可观”的：O(h3*m3*n3)o这是显然要超时的o那么怎么优化呢？例题分析o首先我们回想到求一串数中连续数的最大和的方
12、法：队列优化o我们便可以枚举一个长方形，然后再纵向扩展求最大值。我们就需要预先求每个小长方形的数值和。o复杂度现在就降到了O(h*n3*m3)o显然依旧不满足要求例题分析o现在我们想：求子矩形的数值和的过程中是否做了重复工作？o显然是的。我们没有必要每次把(x1,y1)到(x2,y2)的值都加一遍。我们只需求sumx,y(从(1,1)到(x,y)的数值和)。每次求(x1,y1)到(x2,y2)的和的时候，即求sumx2,y2-sumx1-1,y2-sumx2,y1-1+sumx1-1,y1-1。例题分析o现在的时间复杂度是O(h*n2*m2)n基本上已经满足要求了o但是还可以优化：因为h的范围
13、要比n或m的范围小。o我们可以将长方体换个方向。这样，时间复杂度就变为O(h2*n*m2)可以满足时间限制了。例题分析o对于这道题，我们将两种枚举的优化方法都运用进去了。o最终使得时间复杂度由O(h3*m3*n3)降到O(h2*n*m2)，空间复杂度由n2*m2降到n*m，效果十分明显。枚举法的缺陷o枚举法是一种很容易理解，很容易实现，但效率普遍较低的一种算法。o并且，对于结果或过程不可预见的题目，它是无法解决的。o这就要另一种“全效”算法：回溯法登场了！回溯法o什么是回溯法？o举一个日常生活中的例子：o当我们走迷宫的时候，我们通常是这样走的：n向前后左右四个方向中的一个前进一步(这一步一定不
14、是刚刚走过的)n如果进入死胡同，我们就要往回走到路口，再选择一个方向走下去，直到走至终点。然后欢天喜地地庆祝我们的IQ原来是如此之高槑回溯的方法o回溯的代码实现，通常是这样滴：oProcSearch(v:int)ooif到达边界thenoo输出或储存结果；oexit;oofori=1to决策种类数oif满足可行性和最优性限制thenoSearch(Func(v);oo回溯法的优化o对于回溯法的基本问题的讨论我就不多讲了。o下面我主要讲讲回溯法的几种优化方法：o预处理o剪枝n可行性剪枝n最优性剪枝o启发式搜索预处理o预处理的范围是很广的o一般情况下有以下几种方式n预处理深度上界n预处理代价和的上
15、界n预处理决策代价值n预处理读入数据等等预处理深度上界o预处理深度上界的两种方式n贪心法构造上界n枚举上界o对于贪心法构造上界，实际上和最优性剪枝的性质是类似的(也包括预处理代价和的上界)，我们之后再谈。o对于枚举上界，实际上就是运用二分枚举上界之后用DFS验证是否可行。这种方法即是ID-DFS(迭代加深搜索)预处理决策代价值o这种方法实际上就是用到了一个搜索中的重要概念：搜索实际上就是对一个隐式图的完搜索实际上就是对一个隐式图的完全或不完全遍历全或不完全遍历。o预处理决策代价值，实际上就是预处理两点之间的边权值。由于在搜索中有可能多次用到某一个边权值，因而预处理会节省一些时间消耗。剪枝o剪枝
16、是搜索的一个重要组成部分。或者说，搜索一定要有剪枝。o剪枝可以分为两类：n可行性剪枝n最优性剪枝可行性剪枝o看到这个名称，估计都能猜个八九不离十了吧o没错。可行性剪枝就是将明显不符合逻辑、不符合要求、不符合的状态“咔嚓”剪掉。o怎么剪？就要看题目中的要求和隐含条件了最优性剪枝o当然，仅仅刨去“不能走”的分支是不够的。我们还要把“走了没前途”的枝条也“咔嚓”掉哇咔咔o这就和之前的限制深度、限制代价总和相关联了。实际上，一般也就是这两种方式。【例题】FenceRail(栅栏)o描述描述 Description农夫约翰打算建立一个栅栏将他的牧场给围起来，因此他需要一些特定规格的木材。于是农夫约翰到木
17、材店购买木材。可是木材店老板说他这里只剩下少部分大规格的木板了。不过约翰可以购买这些木板，然后切割成他所需要的规格。而且约翰有一把神奇的锯子，用它来锯木板，不会产生任何损失，也就是说长度为10的木板可以切成长度为8和2的两个木板。你的任务：给你约翰所需要的木板的规格，还有木材店老板能够给出的木材的规格，求约翰最多能够得到多少他所需要的木板。o输入格式输入格式 Input Formato第一行为整数m(m=50)表示木材店老板可以提供多少块木材给约翰。紧跟着m行为老板提供的每一块木板的长度。接下来一行(即第m+2行)为整数n(n=1000)，表示约翰需要多少木材。接下来n行表示他所需要的每一块木
18、板的长度。木材的规格小于32767。（对于店老板提供的和约翰需要的每块木板，你只能使用一次）。o输出格式输出格式 Output Formato只有一行，为约翰最多能够得到的符合条件的木板的个数。o时间限制时间限制 Time Limitationo每个测试点1s例题分析o这道题很容易理解，也很容易就上手做。但是往往做出来以后大部分数据都会超时o那么，我们就用前面总结的一些方法来改进时间效率，解决这道题。o特别注意一下“木材”和“木板”的含义不然下面的讲解会很头晕o*M个木材，N个木板。例题分析o预处理：n预处理读入数据：对数据进行排序，并将明显切不出来的木板和明显没用(过短)的木材扔掉。n预处理
19、深度限制：我们以切出的木板为深度，那么实际上我们就是在二分枚举答案！o注意对木板要从小到大排序，对木材要从大到小排序。o为什么？做做就知道了例题分析o怎么搜？以木板数为阶段，二分枚举最大深度；或者从可行的上界向下依次枚举深度o剪枝n如果当前剩余的可用木材（能切出最短木板）的长度总和比剩余的未切木板的总和小，则返回false例题分析o但是，当我们这般如此地将程序实现以后，发现超时！o我们自习研究数据就会发现，当两个木板(AB)的长度相同时，我们做了无用功：A从C切下，B从D切下；B从C切下，A从D切下。o这两种方法实际上是一样的这便产成了冗余运算。例题分析o怎么减少冗余？o由于我们是按顺序搜的木
20、板，因此我们只需记录上个木板是从last木材切下的，那么如果这个木板和上个木板的长度相同则从last木材开始判断，否则从第一个木材开始判断。o具体程序实现见后文数据结构oConstomaxn=50;omaxr=1023;oVaroboard:array0.maxnoflongint;os,rail:array0.maxroflongint;on,r,i,sum:longint;预处理oProcedureInit;oBeginofori:=1ton-1dooforj:=i+1tondooifboardirailjthenswap(raili,railj);owhileboardnboard1do
21、dec(r);osum:=0;s1:=rail1;ofori:=1tondosum:=sum+boardi;oforj:=2tordosj:=sj-1+railj;owhilesrsumdodec(r);oENd;搜索过程oFunctionokay(deep,ss,last:longint):boolean;oVarotmp,i:longint;oflag:boolean;oBeginoifss=raildeep)thenobeginoboardi:=boardi-raildeep;otmp:=ss;oifboardig(n)时，可以省略g(n)，而提高效率。【例题】八数码问题o问题简介：所谓
22、八数码问题是指这样一种游戏：将分别标有数字1，2，3，8的八块正方形数码牌任意地放在一块33的数码盘上。放牌时要求不能重叠。于是，在33的数码盘上出现了一个空格。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，将任意摆放的数码盘逐步摆成某种特殊的排列。如下图表示了一个具体的八数码问题求解。例题分析o针对这道题，我们往往采用的Hash+BFS算法。事实上，这种方法的确有效。o但是我们也可以通过使用启发函数来大大降低时间消耗。例题分析o我们的启发函数可以这样设：设当前状态为x，目标状态为y，则启发函数值即为x与y的不同的数码的个数。o由于我们采用的是BFS，就不用考虑之前的深度的问题，因
23、为我们对一个点的第一次的深度值即为它的最优值(这样才可以用Hash)o当然如果采用的是DFS，我们就得再综合考虑深度的问题了。不建议采用DFS！数据结构oProgramA_Star(input,output);oconstoP:array1.8oflongint=(1,2,6,24,120,720,5040,40320);ostep:array1.4oflongint=(-3,3,1,-1);ogoal=123804765;oTypeodata=recordot:longint;ox:longint;oend;onum=array1.9oflongint;oVarouse:array0.362
24、880ofboolean;ores:array0.362880oflongint;ox1,x2,st,i,j,v,t,l,r,lx,tmpx:longint;oxx:array1.4oflongint;oqueue:array1.362880ofdata;otmp:num;oflag1,flag2:boolean;ostr:string;启发函数distoFunctiondist(x:longint):longint;oVaros,g:longint;oBeginos:=0;g:=goal;owhile(x+g)0doobeginos:=s+ord(xmod10)(gmod10);ox:=xd
25、iv10;g:=gdiv10;oend;odist:=s;oEnd;主过程oBeginoreadln(str);ofori:=1to9doost:=st*10+ord(stri)-48;oqueue1.x:=st;oqueue1.t:=0;ouseod(st):=true;oresod(st):=0;ol:=1;r:=1;orepeatowithqueueldoobeginov:=getzero(x);oget(tmp,x);ofillchar(xx,sizeof(xx),0);lx:=0;主过程ofori:=1to4doobeginocaseiofo1:ifv=7thencontinue;o
26、3:ifvmod3=0thencontinue;o4:ifvmod3=1thencontinue;oend;oswap(tmpv+stepi,tmpv);otmpx:=getn(tmp);oifnotuseod(tmpx)thenobeginoinc(lx);xxlx:=tmpx;oend;oswap(tmpv,tmpv+stepi);oend;ofori:=1tolx-1dooforj:=i+1tolxdooifdist(xxi)dist(xxj)thenswap(xxi,xxj);主过程ofori:=1tolxdoobeginoinc(r);oqueuer.x:=xxi;oqueuer.t
27、:=t+1;ouseod(xxi):=true;oresod(xxi):=t+1;oend;oend;oinc(l);ountiluseod(goal);owriteln(resod(goal);oEnd.结语o搜索很简单：知道搜索规则，很容易就编出程序o搜索很复杂：为了实现1s的时限，往往需要许多种剪枝和优化的方法o搜索很实用：大部分问题实际上都是可以用搜索做滴，特别是当我们需要获得一道很复杂问题的部份分的时候现在o尽情地考验一下电脑的栈容量吧o尽情地获得牛题的30分吧o尽情地给那棵分叉太多的树剪剪枝吧o尽情地体会搜索的无聊与快乐吧o尽情地DancingwithSearch吧！TheEnd.版权所有，传播者请勿擅自更改。ByBarty