秋令營上午搜索基礎(chǔ)

HuaiyinVocationalandTechnicalSchoolzcysky搜索基礎(chǔ)簡單介紹1.由于肯定有同學(xué)會把這個課看很多遍，因此ppt我會盡量寫的詳細。兼顧所有人的需求實在是困難，而且普及組考的本來就很簡單，所以我會講的基礎(chǔ)一點，至少要保證能聽懂。（嫌簡單去聽提高嘛）ppt背景的妹子是誰？立華奏(TachibanaKanade,FromAngelBeats!)什么是搜索搜索算法：深度優(yōu)先搜索（dfs）廣度優(yōu)先搜索（bfs）為啥要學(xué)搜索？可以騙分可以騙分可以騙分部分游戲題搜索就是正解（NOIP2015斗地主）在以“盡量多拿分”為目的的OI比賽中，搜索是非常重要的得分手段。從一個簡單的例子看dfs給你一個長度為3的環(huán)形數(shù)組，請你往里面填數(shù)字1--20，要求不能重復(fù)，而且相鄰兩個數(shù)的和為質(zhì)數(shù)。有多少方案呢？這題好簡單！我會for循環(huán)！陷入僵局？那我數(shù)組長度為5怎么辦？我寫5個for循環(huán)！………………那我數(shù)組長度為讀入的n，每次不固定，難道你要對每一個n寫一個for循環(huán)嗎？………………有沒有可以自動生成for循環(huán)的東西？數(shù)據(jù)結(jié)構(gòu)？我們發(fā)現(xiàn)，之前寫的每一層for循環(huán)，都長得非常像。那么我們讓程序自動生成這些相似的for循環(huán)行不行呢？這題for循環(huán)的特點：每一層結(jié)構(gòu)類似。在某一層中，我們要先計算下一層的答案，再返回回來枚舉別的可能性。有沒有與他對應(yīng)的數(shù)據(jù)結(jié)構(gòu)呢？似乎在哪里見過的樣子考慮每一層for循環(huán)數(shù)據(jù)的特點：先循環(huán)的層，最后更新答案……先進后出這不是棧嗎？好煩??！我能不能不自己寫棧？怎么寫呢？搜索模板的套路：先判斷是否達到目標狀態(tài)如果達到，判斷當前狀態(tài)是否合法是否計入答案。未達到，枚舉可能的狀態(tài)，記錄本輪選擇，進入下一層。返回后，消除影響。似乎很難寫？一點都不難！已經(jīng)沒有什么好害怕的了媽媽我會搜索了？來多少n我都不怕了？搜索的時間復(fù)雜度分析（畫圖）有沒有能夠應(yīng)用的題呢？洛谷P1238走迷宮記錄當前的坐標xy，用dx[]和dy[]數(shù)組存經(jīng)過路徑。直接用之前的模板就可以過啦~~有沒有可以應(yīng)用的題目呢~全排列的生成。雖然C++自帶有排列生成函數(shù)，但是實現(xiàn)全排列也是搜索的經(jīng)典題之一了。枚舉每一位的數(shù)字，這個可以看著代碼講。有特殊性質(zhì)怎么辦呢？P1135奇怪的電梯dfs第一次求出的不是最短的路徑誒！如何解決？沿用dfs的方法：記錄路徑長度，每次比較長度，保留最優(yōu)答案。缺點：需要遍歷所有情況。新的做法如果我們有一種第一次搜出的答案就是最短路徑的做法，就可以更高效的解決這個問題了。廣度優(yōu)先搜索。回顧深度優(yōu)先搜索的過程。怎么做？考慮性質(zhì)：先進去的點，拓展完之后先被放棄。對應(yīng)了先進先出的數(shù)據(jù)結(jié)構(gòu)……我會隊列！怎么寫？首先建立一個隊列，將初始狀態(tài)放入隊列。然后每次選擇隊頭，拓展，把新狀態(tài)計入隊列。如果隊列沒學(xué)會，去找lxl（nzhtl1477）showmethecodebfs與dfs比較dfs：深度搜索，每次搜完一棵子樹。易于保存方案，編碼容易，首選的搜索方法。缺點：無法解決優(yōu)先性質(zhì)的題，實現(xiàn)會依賴系統(tǒng)棧導(dǎo)致棧溢出。手寫棧模擬較為復(fù)雜。bfs與dfs比較bfs：具有良好的優(yōu)先性質(zhì)。缺點：很難統(tǒng)計具體方案。可拓展性：雙向bfs一些基礎(chǔ)的搜索題洛谷P1037產(chǎn)生數(shù)考慮運用dfs解決這個問題。首先遍歷每一位，按照規(guī)則生成出該位新的數(shù)進行搜索。高精度？不存在的。由于映射關(guān)系不存在自環(huán)，不需要判重。一些基礎(chǔ)的搜索題目洛谷P1019單詞接龍如何處理重疊？暴力預(yù)處理，然后直接搜索的時候帶進去即可。拓展：撕烤如下問題：1.如何更快的算匹配？哈希。后綴數(shù)組/后綴自動機基礎(chǔ)的搜索套路總結(jié)1.dfs找準每一輪枚舉的對象和范圍。枚舉，記錄答案以及已經(jīng)訪問過，防止重復(fù)枚舉。進入下一層?；厮荩绊??；A(chǔ)的搜索套路總結(jié)2.bfs將初始狀態(tài)放入隊列得到隊頭狀態(tài)，拓展他能拓展的所有狀態(tài)，扔進隊列。找到答案必為最優(yōu)先解。搜索的優(yōu)化我們發(fā)現(xiàn)之前我們的搜索會遍歷所有可能的狀態(tài)，然而正常人在做類似的事情的時候肯定不會這么干。所以我們用類似的人類智慧，減少一些狀態(tài)的枚舉。還記得之前的那棵搜索樹嗎？這種做法被形象地稱作“剪枝”。一道經(jīng)典題luoguP1731生日蛋糕問題實質(zhì)就是在規(guī)定的總體積N和層高內(nèi)，分成不同的小圓柱，并堆疊，同時要求堆疊的圓柱的半徑、高度逐漸遞減，求這些圓柱的最小的表面積?；A(chǔ)的判斷：是否做到了m層是否最終體積為0是否當前面積最小考慮優(yōu)化最優(yōu)化剪枝如果當前表面積+余下側(cè)面積>之前的最優(yōu)值，直接返回。正確性顯然。注意剪枝的計算會付出代價，但是付出的代價必須小于我的收益?？紤]優(yōu)化可行性剪枝如果當前剩下的做不到m層，肯定要跳出。同理，如果剩下的太多，哪怕我以最大代價做完m層都會用剩，也要跳出。以上信息都可以O(shè)(1)的求出，代價很小，但是作用很大。剪枝的小結(jié)可行性與最優(yōu)化：1.如果判斷下不能做到了，退出。2.如果已經(jīng)不可能再優(yōu)了，退出。記憶化（避免重復(fù)狀態(tài)）玄學(xué)剪枝剪枝的例題洛谷狗哥玩木棒這是個非常經(jīng)典的搜索應(yīng)用類的題。記憶化搜索啥是記憶化搜索呢？講義講的好清楚啊，我照著講義講講好了。記憶化搜索例題P3183[HAOI2016]食物鏈簡單的例題P1451求細胞數(shù)量flood-fill隨便搜索即可。本節(jié)小結(jié)搜索是非?；A(chǔ)的東西，并且用處非常廣泛。下午