九宫-深度搜索.ppt

《九宫-深度搜索.ppt》由会员分享，可在线阅读，更多相关《九宫-深度搜索.ppt（54页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、今天，今天，你 了吗？AC2023/3/71第一讲第一讲一招制敌之搜索题2023/3/72根据“信息学初学者之家”网站的统计，Ural（俄罗斯的Ural州立大学的简称，那里设立了一个UralOnlineProblemSet，并且支持OnlineJudge。）的题目类型大概呈如下的分布：搜索动态规划贪心构造图论约10%约15%约5%约5%约10%计算几何纯数学问题数据结构其它约5%约20%约5%约25%统计信息：统计信息：2023/3/73搜索题特点分析搜索题特点分析:l题意容易理解题意容易理解l算法相对固定算法相对固定l编程有路可循编程有路可循l竞赛必备知识竞赛必备知识2023/3/74摘自摘

2、自ACMACM竞赛之新人向导竞赛之新人向导“算法中最基本和常用最基本和常用的是搜索，主要是回溯和分支限界法的使用。这里要说的是，有些初学者在学习这些搜索基本算法是不太注意剪枝，这是十分不可取的，因为所有搜索的题目给你的测试用例都不会有很大的规模，你往往察觉不出程序运行的时间问题，但是真正的测试数据一定能过滤出那些没有剪枝的算法。实际上参赛选手基本上都会使用常用的搜索算法，题目的区分度往往就是建立在诸如剪枝之类的优化上了。”引言引言2023/3/75什么是搜索算法呢？搜索算法是利用计算机的高性能来有目的地穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。搜索过程实际上是根据初始条件

3、和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。2023/3/76举例分析举例分析从简单的字符串搜索讲起2023/3/77HDOJ_1238 SubstringslYou are given a number of case-sensitive strings of alphabetic characters,find the largest string X,such that either X,or its inverse can be found as a substring of any of the given strings.InputlThe first line of

4、the input file contains a single integer t(1=t=10),the number of test cases,followed by the input data for each test case.The first line of each test case contains a single integer n(1=n 4and0a/b1.Youshouldfindthepairofprimenumbersp,qsuchthatpq=manda/b=p/q=1,andfurthermore,theproductpqtakesthemaximu

5、mvalueamongsuchpairsoftwoprimenumbers.Youshouldreportpandqasthemostsuitablewidthandheightofthetranslatedpicture.2023/3/713lInputlTheinputisasequenceofatmost2000tripletsofpositiveintegers,delimitedbyaspacecharacterinbetween.Eachlinecontainsasingletriplet.Thesequenceisfollowedbyatripletofzeros,000,whi

6、chindicatedtheendoftheinputandshouldnotbetreatedasdatatobeprocessed.Theintegersofeachinputtripletaretheintegerm,thenumeratora,andthedenominatorbdescribedabove,inthisorder.Youmayassume4m=100000and1=a=b=1000.llOutputlTheoutputisasequenceofpairsofpositiveintegers.Thei-thoutputpaircorrespondstothei-thin

7、puttriplet.Theintegersofeachoutputpairarethewidthpandtheheightqdescribedabove,inthisorder.Eachoutputlinecontainsasinglepair.Aspacecharacterisputbetweentheintegersasadelimiter.Noothercharactersshouldappearintheoutput.2023/3/714lSample Input5129999999999916805161970112002411000lSample Output2231331323

8、73434337532023/3/715获取有用信息获取有用信息a.给定整数m,a,b(4m=100000and1=a=b=1000)b.需要找到两个数(不妨设为p,q)满足以下条件：lp,q均为质数；lp*q=m;la/b=p/q=1;c.输出所有满足以上条件的p,q中乘积最大的一对p,q(最大的p和最小的q,应该是相邻的两个质数)2023/3/716算法分析算法分析1.典型的搜索从所有可能的p,q中寻找满足条件的一对2.p,q的要求p,q均为质数,且p=q=100000;3.按上述思想流程应为a.从1100000中搜出质数b.两层循环，试遍所有的组合(p,q可能相等）c.每种组合去判断是否

9、符合条件，如是，将p*q与当前最大值比较，判断，保存2023/3/717面临的问题：面临的问题：超时！从1100000的质数运算约为1e+8,而这只是准备工作。因此，如不加以分析简化此题无法在规定时间内出解2023/3/718深入分析深入分析考虑大于10000的某个质数，不妨设为Q，另一个质数为P，则：l如果P10，P/Q10，P*Q100000而考虑到a,b的取值范围(1=a=b=1000)可知min(a/b)=0.001同时，要求：p*q=m=0;i-)for(j=i;jm|aj*aim|(double)ai/aj)s)2023/3/720真正的搜索题真正的搜索题迷宫搜索迷宫搜索2023/

10、3/721预备知识预备知识树的遍历树的遍历树的遍历主要有如下四种方法：1.先根/序遍历2.中根/序遍历3.后根/序遍历4.层次遍历分别有什么特点呢？分别有什么特点呢？2023/3/722（1）先根遍历对树的访问次序是:1.先访问根结点2.再访问左子树3.最后访问右子树4.对于左右子树的访问也要满足以上规则示例如下：示例如下：2023/3/723以上二叉树的先根遍历序列是：？21357461、2、4、5、3、6、72023/3/724（2）中根遍历对树的访问次序是:1.先访问左子树2.再访问根结点3.最后访问右子树4.对于左右子树的访问也要满足以上规则示例如下：示例如下：2023/3/725以上

11、二叉树的中根遍历序列是：？21357464、2、5、1、6、3、72023/3/726（3）后根遍历对树的访问次序是:1.先访问左子树2.再访问右子树3.最后访问根结点4.对于左右子树的访问也要满足以上规则示例如下：示例如下：2023/3/727以上二叉树的后根遍历序列是：？21357464、5、2、6、7、3、12023/3/728（4）层次遍历对树的访问次序是:1.先访问根结点2.再访问根结点的子节点（即第二层节点）3.再访问第三层节点4.示例如下：示例如下：2023/3/729以上二叉树的层次遍历序列是：？21357461、2、3、4、5、6、72023/3/730几个基本概念：几个基本

12、概念：l初始状态：略l目标状态：略l状态空间：由于求解问题的过程中分枝有很多（主要是求解过程中求解条件的不确定性、不完备性造成的），使得求解的路径很多，这就构成了一个图，我们说这个图就是状态空间。l状态空间搜索：就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，就是在解一个问题时，找到一条解题的过程，可以从求解的开始到问题的结果。2023/3/731初始状态：目标状态：2831647512384765例例 九宫重排问题九宫重排问题2023/3/7322831647528314765283164758321476528314765231847652831647528314

13、7652318476523184765283714652023/3/733231847651238476512384765123784652023/3/734三、广度优先搜索三、广度优先搜索基本思想基本思想：从初始状态S开始，利用规则，生成所有可能的状态。构成树的下一层节点，检查是否出现目标状态G，若未出现，就对该层所有状态节点，分别顺序利用规则。生成再下一层的所有状态节点，对这一层的所有状态节点检查是否出现G，若未出现，继续按上面思想生成再下一层的所有状态节点，这样一层一层往下展开。直到出现目标状态为止。2023/3/735BFS算法：算法：（1）把起始节点S线放到OPEN表中（2）如果OP

14、EN是空表，则失败退出，否则继续。（3）在OPEN表中取最前面的节点node移到CLOSED表中。（4）扩展node节点。若没有后继（即叶节点），则转向（2）循环。（5）把node的所有后继节点放在OPEN表的末端。各后继结点指针指向node节点。（6）若后继节点中某一个是目标节点，则找到一个解，成功退出。否则转向（2）循环。2023/3/736搜索过程如下：OPLWVUTRQABCDGEFS广度优先搜索示意图2023/3/737例1、示意图节点的搜索SL，O，PQ，R，TU，V，WA，B，C S L O PQ R 广度优先搜索过程中的OPEN表和CLOSED表OPENCLOSED2023/3

15、/738四、深度优先搜索基本思想：从初始状态S开始，利用规则生成搜索树下一层任一个结点，检查是否出现目标状态G，若未出现，以此状态利用规则生成再下一层任一任一个个结点，再检查是否为目标节点G，若未出现，继续以上操作过程，一直进行到叶节点（即不能再生成新状态节点），当它仍不是目标状态G时，回溯到上一层结果，取另一可能扩展搜索的分支。生成新状态节点。若仍不是目标状态，就按该分支一直扩展到叶节点，若仍不是目标，采用相同的回溯办法回退到上层节点，扩展可能的分支生成新状态，一直进行下去，直到找到目标状态G为止。2023/3/739搜索过程如下：HALIFBCDEJGKS深度优先搜索示意图2023/3/7

16、40DFS算法（1）把起始节点S线放到OPEN表中。（2）如果OPEN是空表，则失败退出，否则继续。（3）从OPEN表中取最前面的节点node移到CLOSED表中。（4）若node节点是叶结点（若没有后继节点），则转向（2）。（5）扩展node的后继节点，产生全部后继节点，并把他们放在OPEN表的前面。各后继结点指针指向node节点。（6）若后继节点中某一个是目标节点，则找到一个解，成功退出。否则转向（2）循环。2023/3/741例、节点搜索示意图SA，H，R，F，C，D E S A BC D EOPENCLOSED2023/3/742小结：小结：广度和深度优先搜索有一个很大的缺陷,就是他们

17、都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。所以，在这里再次强调“剪枝剪枝”！2023/3/743HDOJ_1010 Tempter of the BonelProblem DescriptionlThedoggiefoundaboneinanancientmaze,whichfascinatedhimalot.However,whenhepickeditup,themazebegantoshake,andthedoggiecouldfeelthegroundsinking.Herea

18、lizedthatthebonewasatrap,andhetrieddesperatelytogetoutofthismaze.ThemazewasarectanglewithsizesNbyM.Therewasadoorinthemaze.Atthebeginning,thedoorwasclosedanditwouldopenattheT-thsecondforashortperiodoftime(lessthan1second).ThereforethedoggiehadtoarriveatthedooronexactlytheT-thsecond.Ineverysecond,heco

19、uldmoveoneblocktooneoftheupper,lower,leftandrightneighboringblocks.Onceheenteredablock,thegroundofthisblockwouldstarttosinkanddisappearinthenextsecond.Hecouldnotstayatoneblockformorethanonesecond,norcouldhemoveintoavisitedblock.Canthepoordoggiesurvive?Pleasehelphim.2023/3/744lInputlTheinputconsistso

20、fmultipletestcases.ThefirstlineofeachtestcasecontainsthreeintegersN,M,andT(1N,M7;0T1或或1-0 必然是奇数步必然是奇数步 l 0-0 走走1-1 必然是偶数步必然是偶数步 所以当遇到从0走向0但是要求时间是奇数的，或者，从1走向0但是要求时间是偶数的都可以直接判断不可达！结论：结论：2023/3/749这个题目没问题了吧？这个题目没问题了吧？2023/3/750思考：思考：l求某给定时间以内能否找到出口l找到出口的最短时间l条件变为可以停留2023/3/751附录：推荐搜索题：附录：推荐搜索题：l1010TempteroftheBonel1015Safecrackerl1072Nightmarel1238Substringsl1239CallingExtraterrestrialIntelligenceAgainl1240Asteroids!l1241OilDepositsl1242Rescuel1372KnightMovesl1401Solitaire2023/3/752课后一定要练习！课后一定要练习！2023/3/753ACM,天天见！天天见！2023/3/754