九宫-深度搜索

今日，你了吗？AC2023/11/211第一讲一招制敌之搜寻题2023/11/212 依据“信息学初学者之家”网站的统计，Ural〔俄罗斯的Ural州立大学的简称，那里设立了一个UralOnlineProblemSet，并且支持OnlineJudge。〕的题目类型或许呈如下的分布：

搜寻动态规划贪心构造图论 约10%约15%约5%约5%约10% 计算几何纯数学问题数据构造其它

约5%约20%约5%约25%统计信息：2023/11/213搜寻题特点分析:题意简洁理解算法相对固定编程有路可循竞赛必备学问2023/11/214——摘自《ACM竞赛之新人向导

》 “算法中最根本和常用的是搜寻，主要是回溯和分支限界法的使用。这里要说的是，有些初学者在学习这些搜寻根本算法是不太留意剪枝，这是特别不行取的，由于全部搜寻的题目给你的测试用例都不会有很大的规模，你往往觉察不出程序运行的时间问题，但是真正的测试数据肯定能过滤出那些没有剪枝的算法。实际上参赛选手根本上都会使用常用的搜寻算法，题目的区分度往往就是建立在诸如剪枝之类的优化上了。”引言2023/11/215什么是搜寻算法呢？ 搜寻算法是利用计算机的高性能来有目的地穷举一个问题的局部或全部的可能状况，从而求出问题的解的一种方法。

搜寻过程实际上是依据初始条件和扩展规章构造一棵解答树并查找符合目标状态的节点的过程。

2023/11/216举例分析从简洁的字符串搜寻讲起2023/11/217HDOJ_1238SubstringsYouaregivenanumberofcase-sensitivestringsofalphabeticcharacters,findthelargeststringX,suchthateitherX,oritsinversecanbefoundasasubstringofanyofthegivenstrings.

InputThefirstlineoftheinputfilecontainsasingleintegert(1<=t<=10),thenumberoftestcases,followedbytheinputdataforeachtestcase.Thefirstlineofeachtestcasecontainsasingleintegern(1<=n<=100),thenumberofgivenstrings,followedbynlines,eachrepresentingonestringofminimumlength1andmaximumlength100.Thereisnoextrawhitespacebeforeandafterastring.

OutputThereshouldbeonelinepertestcasecontainingthelengthofthelargeststringfound.

2023/11/218SampleInput

2

3

ABCD

BCDFF

BRCD

2

rose

orchidSampleOutput

2

2

2023/11/219题目分析：这是一道入门级别的搜寻题，根本思想比较简洁，但是假设用最朴实的算法，可能会超时如何降低算法的简单度呢？下面的算法如何：先将字符串按长度从短到长排序，枚举最短的字符串的子串，推断是否都是别的字符串的子串，求出最大长度即可。2023/11/2110说明： 此题除了可以练习根本搜寻算法，也是练习字符串处理的好题目，题中用到的相关学问点有：求反串求子串字符串查找求字符串长度猛烈推举！！2023/11/2111再来一道数值型搜寻题2023/11/2112HDOJ_1239

CallingExtraterrestrialIntelligenceAgainProblemDescriptionAmessagefromhumanstoextraterrestrialintelligencewassentthroughtheAreciboradiotelescopeinPuertoRicoontheafternoonofSaturdayNovember16,1974.Themessageconsistedof1679bitsandwasmeanttobetranslatedtoarectangularpicturewith23*73pixels.Sinceboth23and73areprimenumbers,23*73istheuniquepossiblesizeofthetranslatedrectangularpictureeachedgeofwhichislongerthan1pixel.Ofcourse,therewasnoguaranteethatthereceiverswouldtrytotranslatethemessagetoarectangularpicture.Eveniftheywould,theymightputthepixelsintotherectangleincorrectly.ThesendersoftheArecibomessagewereoptimistic.

Weareplanningasimilarproject.Yourtaskintheprojectistofindthemostsuitablewidthandheightofthetranslatedrectangularpicture.Theterm“mostsuitable“isdefinedasfollows.Anintegermgreaterthan4isgiven.Apositivefractiona/blessthanorequalto1isalsogiven.Theareaofthepictureshouldnotbegreaterthanm.Bothofthewidthandtheheightofthetranslatedpictureshouldbeprimenumbers.Theratioofthewidthtotheheightshouldnotbelessthana/bnorgreaterthan1.Youshouldmaximizetheareaofthepictureundertheseconstraints.

Inotherwords,youwillreceiveanintegermandafractiona/b.Itholdsthatm>4and0<a/b<1.Youshouldfindthepairofprimenumbersp,qsuchthatpq<=manda/b<=p/q<=1,andfurthermore,theproductpqtakesthemaximumvalueamongsuchpairsoftwoprimenumbers.Youshouldreportpandqasthe“mostsuitable“widthandheightofthetranslatedpicture.

2023/11/2113InputTheinputisasequenceofatmost2023tripletsofpositiveintegers,delimitedbyaspacecharacterinbetween.Eachlinecontainsasingletriplet.Thesequenceisfollowedbyatripletofzeros,000,whichindicatedtheendoftheinputandshouldnotbetreatedasdatatobeprocessed.

Theintegersofeachinputtripletaretheintegerm,thenumeratora,andthedenominatorbdescribedabove,inthisorder.Youmayassume4<m<=100000and1<=a<=b<=1000.

OutputTheoutputisasequenceofpairsofpositiveintegers.Thei-thoutputpaircorrespondstothei-thinputtriplet.Theintegersofeachoutputpairarethewidthpandtheheightqdescribedabove,inthisorder.

Eachoutputlinecontainsasinglepair.Aspacecharacterisputbetweentheintegersasadelimiter.Noothercharactersshouldappearintheoutput.

2023/11/2114SampleInput

512

99999999999

1680516

197011

2023411

000SampleOutput

22

313313

2373

4343

3753

2023/11/2115猎取有用信息a.给定整数m,a,b(4<m<=100000and 1<=a<=b<=1000)b.需要找到两个数(不妨设为p,q)满足以下条件：p,q均为质数；p*q<=m;a/b<=p/q<=1;c.输出全部满足以上条件的p,q中乘积最大的一对p,q(最大的p和最小的q,应当是相邻的两个质数)2023/11/2116算法分析1.典型的搜寻从全部可能的p,q中查找满足条件的一对2.p,q的要求p,q均为质数,且p<=q<=100000;3.按上述思想流程应为a.从1—100000中搜出质数b.两层循环，试遍全部的组合(p,q可能相等〕c.每种组合去推断是否符合条件，如是，将p*q与当前最大值比较，推断，保存2023/11/2117面临的问题：超时！从1—100000的质数运算约为1e+8,而这只是预备工作。因此，如不加以分析简化此题无法在规定时间内出解2023/11/2118深入分析考虑大于10000的某个质数，不妨设为Q，另一个质数为P，则：假设P<10，P/Q<0.001假设P>10，P*Q>100000而考虑到a,b的取值范围(1<=a<=b<=1000)可知min(a/b)=0.001同时，要求：p*q<=m<=10000所以无论如何质数都不能超过10000。〔事实上，不会超过9091〕然而，这是最小的范围吗？p,q的范围其实可在2—50000(why?)2023/11/2119搜寻时的技巧：搜寻挨次很重要。应当从大往小搜 〔num:质数的个数〕 for(i=num-1;i>=0;i--) for(j=i;j<=num-1;j++)……

留意剪枝：If(a[j]>m||a[j]*a[i]>m||((double)a[i]/a[j])<s) ……2023/11/2120真正的搜寻题迷宫搜寻2023/11/2121预备学问——树的遍历树的遍历主要有如下四种方法：1.先根/序遍历2.中根/序遍历3.后根/序遍历4.层次遍历分别有什么特点呢？2023/11/2122〔1〕先根遍历对树的访问次序是:1.先访问根结点2.再访问左子树3.最终访问右子树4.对于左右子树的访问也要满足以上规章例如如下：2023/11/2123以上二叉树的先根遍历序列是：？？21357461、2、4、5、3、6、72023/11/2124〔2〕中根遍历对树的访问次序是:1.先访问左子树2.再访问根结点3.最终访问右子树4.对于左右子树的访问也要满足以上规章例如如下：2023/11/2125以上二叉树的中根遍历序列是：？？21357464、2、5、1、6、3、72023/11/2126〔3〕后根遍历对树的访问次序是:1.先访问左子树2.再访问右子树3.最终访问根结点4.对于左右子树的访问也要满足以上规章例如如下：2023/11/2127以上二叉树的后根遍历序列是：？？21357464、5、2、6、7、3、12023/11/2128〔4〕层次遍历对树的访问次序是:1.先访问根结点2.再访问根结点的子节点〔即其次层节点〕3.再访问第三层节点4.……例如如下：2023/11/2129以上二叉树的层次遍历序列是：？？21357461、2、3、4、5、6、72023/11/2130几个根本概念：初始状态：略目标状态：略状态空间：由于求解问题的过程中分枝有很多〔主要是求解过程中求解条件的不确定性、不完备性造成的〕，使得求解的路径很多，这就构成了一个图，我们说这个图就是状态空间。状态空间搜寻：就是将问题求解过程表现为从初始状态到目标状态查找这个路径的过程。通俗点说，就是在解一个问题时，找到一条解题的过程，可以从求解的开头到问题的结果。2023/11/2131初始状态：目标状态：2831647512384765例九宫重排问题2023/11/213228316475283147652831647583214765283147652318476528316475283147652318476523184765283714652023/11/2133231847651238476512384765123784652023/11/2134三、广度优先搜寻 根本思想：从初始状态S开头，利用规章，生成全部可能的状态。构成树的下一层节点，检查是否消失目标状态G，假设未消失，就对该层全部状态节点，分别挨次利用规章。生成再下一层的全部状态节点，对这一层的全部状态节点检查是否消失G，假设未消失，连续按上面思想生成再下一层的全部状态节点，这样一层一层往下开放。直到消失目标状态为止。2023/11/2135BFS算法： 〔1〕把起始节点S线放到OPEN表中〔2〕假设OPEN是空表，则失败退出，否则连续。〔3〕在OPEN表中取最前面的节点node移到CLOSED表中。〔4〕扩展node节点。假设没有后继〔即叶节点〕，则转向〔2〕循环。〔5〕把node的全部后继节点放在OPEN表的末端。各后继结点指针指向node节点。〔6〕假设后继节点中某一个是目标节点，则找到一个解，成功退出。否则转向〔2〕循环。2023/11/2136搜寻过程如下：OPLWVUTRQABCDGEFS广度优先搜寻示意图2023/11/2137例1、示意图节点的搜寻SL，O，PQ，R，TU，V，WA，B，C

SLOPQR广度优先搜寻过程中的OPEN表和CLOSED表OPENCLOSED2023/11/2138四、深度优先搜寻 根本思想：从初始状态S开头，利用规章生成搜寻树下一层任一个结点，检查是否消失目标状态G，假设未消失，以此状态利用规章生成再下一层任一个结点，再检查是否为目标节点G，假设未消失，连续以上操作过程，始终进展到叶节点〔即不能再生成新状态节点〕，当它仍不是目标状态G时，回溯到上一层结果，取另一可能扩展搜寻的分支。生成新状态节点。假设仍不是目标状态，就按该分支始终扩展到叶节点，假设仍不是目标，承受一样的回溯方法回退到上层节点，扩展可能的分支生成新状态，…，始终进展下去，直到找到目标状态G为止。2023/11/2139搜寻过程如下：HALIFBCDEJGKS深度优先搜寻示意图2023/11/2140DFS算法 〔1〕把起始节点S线放到OPEN表中。〔2〕假设OPEN是空表，则失败退出，否则连续。〔3〕从OPEN表中取最前面的节点node移到CLOSED表中。〔4〕假设node节点是叶结点〔假设没有后继节点〕，则转向〔2〕。〔5〕扩展node的后继节点，产生全部后继节点，并把他们放在OPEN表的前面。各后继结点指针指向node节点。〔6〕假设后继节点中某一个是目标节点，则找到一个解，成功退出。否则转向〔2〕循环。2023/11/2141例、节点搜寻示意图SA，H，R，F，C，DE

SABCDEOPENCLOSED2023/11/2142小结： 广度和深度优先搜寻有一个很大的缺陷,就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的状况下是很适宜的算法，可是当状态空间特别大，且不猜测的状况下就不行取了。他的效率实在太低，甚至不行完成。

所以，在这里再次强调“剪枝”！2023/11/2143HDOJ_1010TempteroftheBoneProblemDescriptionThedoggiefoundaboneinanancientmaze,whichfascinatedhimalot.However,whenhepickeditup,themazebegantoshake,andthedoggiecouldfeelthegroundsinking.Herealizedthatthebonewasatrap,andhetrieddesperatelytogetoutofthismaze.

ThemazewasarectanglewithsizesNbyM.Therewasadoorinthemaze.Atthebeginning,thedoorwasclosedanditwouldopenattheT-thsecondforashortperiodoftime(lessthan1second).ThereforethedoggiehadtoarriveatthedooronexactlytheT-thsecond.Ineverysecond,hecouldmoveoneblocktooneoftheupper,lower,leftandrightneighboringblocks.Onceheenteredablock,thegroundofthisblockwouldstarttosinkanddisappearinthenextsecond.Hecouldnotstayatoneblockformorethanonesecond,norcouldhemoveintoavisitedblock.Canthepoordoggiesurvive?Pleasehelphim.

2023/11/2144InputTheinputconsistsofmultipletestcases.ThefirstlineofeachtestcasecontainsthreeintegersN,M,andT(1<N,M<7;0<T<50),whichdenotethesizesofthemazeandthetimeatwhichthedoorwillopen,respectively.ThenextNlinesgivethemazelayout,witheachlinecontainingMcharacters.Acharacterisoneofthefollowing:

”X”:ablockofwall,whichthedoggiecannotenter;

”S”:thestartpointofthedoggie;

”D”:theD