九宮-深度搜索

今日，你了嗎？AC2023/2/71第一講一招制敵之搜尋題2023/2/72 依據(jù)“信息學(xué)初學(xué)者之家”網(wǎng)站的統(tǒng)計，Ural（俄羅斯的Ural州立高校的簡稱，那里設(shè)立了一個UralOnlineProblemSet，并且支持OnlineJudge。）的題目類型或許呈如下的分布：

搜尋動態(tài)規(guī)劃貪心構(gòu)造圖論 約10%約15%約5%約5%約10% 計算幾何純數(shù)學(xué)問題數(shù)據(jù)結(jié)構(gòu)其它

約5%約20%約5%約25%統(tǒng)計信息：2023/2/73搜尋題特點分析:題意簡潔理解算法相對固定編程有路可循競賽必備學(xué)問2023/2/74——摘自《ACM競賽之新人向?qū)?/p>

》 “算法中最基本和常用的是搜尋，主要是回溯和分支限界法的運用。這里要說的是，有些初學(xué)者在學(xué)習(xí)這些搜尋基本算法是不太留意剪枝，這是特殊不行取的，因為全部搜尋的題目給你的測試用例都不會有很大的規(guī)模，你往往察覺不出程序運行的時間問題，但是真正的測試數(shù)據(jù)確定能過濾出那些沒有剪枝的算法。事實上參賽選手基本上都會運用常用的搜尋算法，題目的區(qū)分度往往就是建立在諸如剪枝之類的優(yōu)化上了?！币?023/2/75什么是搜尋算法呢？ 搜尋算法是利用計算機的高性能來有目的地窮舉一個問題的部分或全部的可能狀況，從而求出問題的解的一種方法。

搜尋過程事實上是依據(jù)初始條件和擴展規(guī)則構(gòu)造一棵解答樹并找尋符合目標(biāo)狀態(tài)的節(jié)點的過程。

2023/2/76舉例分析從簡潔的字符串搜尋講起2023/2/77HDOJ_1238SubstringsYouaregivenanumberofcase-sensitivestringsofalphabeticcharacters,findthelargeststringX,suchthateitherX,oritsinversecanbefoundasasubstringofanyofthegivenstrings.

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

OutputThereshouldbeonelinepertestcasecontainingthelengthofthelargeststringfound.

2023/2/78SampleInput

2

3

ABCD

BCDFF

BRCD

2

rose

orchidSampleOutput

2

2

2023/2/79題目分析：這是一道入門級別的搜尋題，基本思想比較簡潔，但是假如用最樸實的算法，可能會超時如何降低算法的困難度呢？下面的算法如何：先將字符串按長度從短到長排序，枚舉最短的字符串的子串，推斷是否都是別的字符串的子串，求出最大長度即可。2023/2/710說明： 本題除了可以練習(xí)基本搜尋算法，也是練習(xí)字符串處理的好題目，題中用到的相關(guān)學(xué)問點有：求反串求子串字符串查找求字符串長度猛烈舉薦??！2023/2/711再來一道數(shù)值型搜尋題2023/2/712HDOJ_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/2/713InputTheinputisasequenceofatmost2000tripletsofpositiveintegers,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/2/714SampleInput

512

99999999999

1680516

197011

2002411

000SampleOutput

22

313313

2373

4343

3753

2023/2/715獲得有用信息a.給定整數(shù)m,a,b(4<m<=100000and 1<=a<=b<=1000)b.須要找到兩個數(shù)(不妨設(shè)為p,q)滿足以下條件：p,q均為質(zhì)數(shù)；p*q<=m;a/b<=p/q<=1;c.輸出全部滿足以上條件的p,q中乘積最大的一對p,q(最大的p和最小的q,應(yīng)當(dāng)是相鄰的兩個質(zhì)數(shù))2023/2/716算法分析1.典型的搜尋從全部可能的p,q中找尋滿足條件的一對2.p,q的要求p,q均為質(zhì)數(shù),且p<=q<=100000;3.按上述思想流程應(yīng)為a.從1—100000中搜出質(zhì)數(shù)b.兩層循環(huán)，試遍全部的組合(p,q可能相等）c.每種組合去推斷是否符合條件，如是，將p*q與當(dāng)前最大值比較，推斷，保存2023/2/717面臨的問題：超時！從1—100000的質(zhì)數(shù)運算約為1e+8,而這只是準(zhǔn)備工作。因此，如不加以分析簡化此題無法在規(guī)定時間內(nèi)出解2023/2/718深化分析考慮大于10000的某個質(zhì)數(shù)，不妨設(shè)為Q，另一個質(zhì)數(shù)為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所以無論如何質(zhì)數(shù)都不能超過10000。（事實上，不會超過9091）然而，這是最小的范圍嗎？p,q的范圍其實可在2—50000(why?)2023/2/719搜尋時的技巧：搜尋依次很重要。應(yīng)當(dāng)從大往小搜 （num:質(zhì)數(shù)的個數(shù)） 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/2/720真正的搜尋題迷宮搜尋2023/2/721預(yù)備學(xué)問——樹的遍歷樹的遍歷主要有如下四種方法：1.先根/序遍歷2.中根/序遍歷3.后根/序遍歷4.層次遍歷分別有什么特點呢？2023/2/722（1）先根遍歷對樹的訪問次序是:1.先訪問根結(jié)點2.再訪問左子樹3.最終訪問右子樹4.對于左右子樹的訪問也要滿足以上規(guī)則示例如下：2023/2/723以上二叉樹的先根遍歷序列是：？？21357461、2、4、5、3、6、72023/2/724（2）中根遍歷對樹的訪問次序是:1.先訪問左子樹2.再訪問根結(jié)點3.最終訪問右子樹4.對于左右子樹的訪問也要滿足以上規(guī)則示例如下：2023/2/725以上二叉樹的中根遍歷序列是：？？21357464、2、5、1、6、3、72023/2/726（3）后根遍歷對樹的訪問次序是:1.先訪問左子樹2.再訪問右子樹3.最終訪問根結(jié)點4.對于左右子樹的訪問也要滿足以上規(guī)則示例如下：2023/2/727以上二叉樹的后根遍歷序列是：？？21357464、5、2、6、7、3、12023/2/728（4）層次遍歷對樹的訪問次序是:1.先訪問根結(jié)點2.再訪問根結(jié)點的子節(jié)點（即其次層節(jié)點）3.再訪問第三層節(jié)點4.……示例如下：2023/2/729以上二叉樹的層次遍歷序列是：？？21357461、2、3、4、5、6、72023/2/730幾個基本概念：初始狀態(tài)：略目標(biāo)狀態(tài)：略狀態(tài)空間：由于求解問題的過程中分枝有很多（主要是求解過程中求解條件的不確定性、不完備性造成的），使得求解的路徑很多，這就構(gòu)成了一個圖，我們說這個圖就是狀態(tài)空間。狀態(tài)空間搜尋：就是將問題求解過程表現(xiàn)為從初始狀態(tài)到目標(biāo)狀態(tài)找尋這個路徑的過程。通俗點說，就是在解一個問題時，找到一條解題的過程，可以從求解的起先到問題的結(jié)果。2023/2/731初始狀態(tài)：目標(biāo)狀態(tài)：2831647512384765例九宮重排問題2023/2/73228316475283147652831647583214765283147652318476528316475283147652318476523184765283714652023/2/733231847651238476512384765123784652023/2/734三、廣度優(yōu)先搜尋 基本思想：從初始狀態(tài)S起先，利用規(guī)則，生成全部可能的狀態(tài)。構(gòu)成樹的下一層節(jié)點，檢查是否出現(xiàn)目標(biāo)狀態(tài)G，若未出現(xiàn)，就對該層全部狀態(tài)節(jié)點，分別依次利用規(guī)則。生成再下一層的全部狀態(tài)節(jié)點，對這一層的全部狀態(tài)節(jié)點檢查是否出現(xiàn)G，若未出現(xiàn)，接著按上面思想生成再下一層的全部狀態(tài)節(jié)點，這樣一層一層往下綻開。直到出現(xiàn)目標(biāo)狀態(tài)為止。2023/2/735BFS算法： （1）把起始節(jié)點S線放到OPEN表中（2）假如OPEN是空表，則失敗退出，否則接著。（3）在OPEN表中取最前面的節(jié)點node移到CLOSED表中。（4）擴展node節(jié)點。若沒有后繼（即葉節(jié)點），則轉(zhuǎn)向（2）循環(huán)。（5）把node的全部后繼節(jié)點放在OPEN表的末端。各后繼結(jié)點指針指向node節(jié)點。（6）若后繼節(jié)點中某一個是目標(biāo)節(jié)點，則找到一個解，成功退出。否則轉(zhuǎn)向（2）循環(huán)。2023/2/736搜尋過程如下：OPLWVUTRQABCDGEFS廣度優(yōu)先搜尋示意圖2023/2/737例1、示意圖節(jié)點的搜尋SL，O，PQ，R，TU，V，WA，B，C

SLOPQR廣度優(yōu)先搜尋過程中的OPEN表和CLOSED表OPENCLOSED2023/2/738四、深度優(yōu)先搜尋 基本思想：從初始狀態(tài)S起先，利用規(guī)則生成搜尋樹下一層任一個結(jié)點，檢查是否出現(xiàn)目標(biāo)狀態(tài)G，若未出現(xiàn)，以此狀態(tài)利用規(guī)則生成再下一層任一個結(jié)點，再檢查是否為目標(biāo)節(jié)點G，若未出現(xiàn)，接著以上操作過程，始終進行到葉節(jié)點（即不能再生成新狀態(tài)節(jié)點），當(dāng)它仍不是目標(biāo)狀態(tài)G時，回溯到上一層結(jié)果，取另一可能擴展搜尋的分支。生成新狀態(tài)節(jié)點。若仍不是目標(biāo)狀態(tài)，就按該分支始終擴展到葉節(jié)點，若仍不是目標(biāo)，接受相同的回溯方法回退到上層節(jié)點，擴展可能的分支生成新狀態(tài)，…，始終進行下去，直到找到目標(biāo)狀態(tài)G為止。2023/2/739搜尋過程如下：HALIFBCDEJGKS深度優(yōu)先搜尋示意圖2023/2/740DFS算法 （1）把起始節(jié)點S線放到OPEN表中。（2）假如OPEN是空表，則失敗退出，否則接著。（3）從OPEN表中取最前面的節(jié)點node移到CLOSED表中。（4）若node節(jié)點是葉結(jié)點（若沒有后繼節(jié)點），則轉(zhuǎn)向（2）。（5）擴展node的后繼節(jié)點，產(chǎn)生全部后繼節(jié)點，并把他們放在OPEN表的前面。各后繼結(jié)點指針指向node節(jié)點。（6）若后繼節(jié)點中某一個是目標(biāo)節(jié)點，則找到一個解，成功退出。否則轉(zhuǎn)向（2）循環(huán)。2023/2/741例、節(jié)點搜尋示意圖SA，H，R，F(xiàn)，C，DE

SABCDEOPENCLOSED2023/2/742小結(jié)： 廣度和深度優(yōu)先搜尋有一個很大的缺陷,就是他們都是在一個給定的狀態(tài)空間中窮舉。這在狀態(tài)空間不大的狀況下是很合適的算法，可是當(dāng)狀態(tài)空間特殊大，且不預(yù)料的狀況下就不行取了。他的效率實在太低，甚至不行完成。

所以，在這里再次強調(diào)“剪枝”！2023/2/743HDOJ_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/2/744InputTheinputconsistsofmultipletestcases.ThefirstlineofeachtestcasecontainsthreeintegersN,M,andT(1<N,M<7;0<T<50),whichdenotethesizesofthemazeandthetimeatwhichthedoorwillopen,respectively.ThenextNlinesgivethemazelayout,witheachlinecontainingMcharacters.Acharacterisoneofthefollowing:

'X':ablockofwall,whichthedoggiecannotenter;

'S':thestartpointofthedoggie;

'D'