day3搜索優(yōu)化方法-曹利國-noip培訓(xùn)

搜索優(yōu)化方法長沙市一中曹利國什么是搜索？搜索是對一個問題不斷地尋找可行方案，然后找到最優(yōu)的可行方案。搜索稱為“通用解題法”，但是大局部情況下搜索所需的時間復(fù)雜度很高。搜索一般分為：深度優(yōu)先搜索〔DFS〕和廣度優(yōu)先搜索〔BFS〕搜索關(guān)鍵字狀態(tài)狀態(tài)轉(zhuǎn)移優(yōu)先搜索遍歷枚舉深度優(yōu)先搜索廣度優(yōu)先搜索剪枝狀態(tài)狀態(tài)轉(zhuǎn)移狀態(tài)：是對問題在某一時刻的進展情況的數(shù)學(xué)描述狀態(tài)轉(zhuǎn)移：是問題從一種狀態(tài)轉(zhuǎn)移到另一種狀態(tài)的操作。搜索過程：通過狀態(tài)轉(zhuǎn)移不斷地尋找目標狀態(tài)或最優(yōu)狀態(tài)。深度優(yōu)先遍歷深度優(yōu)先搜索遍歷：遍歷類似樹的先根遍歷，它是一個遞歸過程，可稱述為：首先訪問一個頂點Vi〔開始為初始點〕，并將其標記為已訪問過，然后從Vi的一個未被訪問可到達的鄰接點出發(fā)進行深度優(yōu)先搜索遍歷，當(dāng)Vi所有可到達的鄰接點均被訪問過時，那么退回上一個頂點Vk，從Vk的另一個未被訪問過的鄰接點出發(fā)進行深度優(yōu)先搜索遍歷。深度優(yōu)先搜索深度優(yōu)先搜索：按照深度優(yōu)先搜索遍歷所有的狀態(tài)。實現(xiàn)方式可以采用遞歸或者棧來實現(xiàn)深度優(yōu)先搜索遞歸實現(xiàn)的框架：VoidDFS(longstate,longdepth){for(longi=1;i<=count(state);i++)newstate=make(state,i);if(answer)printans;elseif(depth<maxdepth)DFS(newstate,depth+1)}深度優(yōu)先搜索深度優(yōu)先搜索可以看成按深度優(yōu)先順序遍歷一顆樹：一般深度優(yōu)先搜索要用到回溯?；厮菟惴ㄟm用問題：求解搜索問題一般的深度優(yōu)先搜索問題都要用到回溯算法，每次不能遍歷下去時，回溯到前一個點，繼續(xù)遍歷。例題1走迷宮問題〔高級本〕有一個m*n格的迷宮(表示有m行、n列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件讀入這m*n個數(shù)據(jù)和起始點、結(jié)束點(起始點和結(jié)束點都是用兩個數(shù)據(jù)來描述的，分別表示這個點的行號和列號)?，F(xiàn)在要你編程找出所有可行的道路，要求所走的路中沒有重復(fù)的點，走時只能是上下左右四個方向。如果一條路都不可行，那么輸出相應(yīng)信息(用-1表示無路)。例題1分析我們不難想到可以采用深度優(yōu)先搜索。我們用深度優(yōu)先搜索擴展一個點時，向4個方向按照深度優(yōu)先搜索進行擴展，但是注意一些到過的點不能再次經(jīng)過。當(dāng)?shù)竭_目標點時不擴展下去，并且計數(shù)器加一，輸出答案，回溯。當(dāng)前這個點不能繼續(xù)擴展下去時，回溯到上一節(jié)點，擴展下去。深度優(yōu)先搜索的優(yōu)化盡可能減少生成的節(jié)點數(shù)定制回溯邊界條件，剪掉不可能得到最優(yōu)解的子樹運用記憶化的方法，使得一些遍歷過的子樹不要重復(fù)遍歷

減少所遍歷的狀態(tài)總數(shù)例題2：定貨單〔ceoi試題〕某商店經(jīng)理已將所有的貨物按它們的標號的字母順序進行了分類。所有的標號首字母相同的貨物被存儲在同一倉庫中，該倉庫也用該字母進行標記。在某天中，經(jīng)理接到并登記了許多定貨單，每張定貨單僅需一種貨物你道了該天經(jīng)理所需處理的所有定貨單，但你不知道它們的登記順序。計算出所有可能的訪問倉庫的方法，來為經(jīng)理解決該天所有的定貨要求。輸入文件ORDERS.IN中僅有一行，包含所有所需貨物的標號〔一個隨機的順序〕。每一種貨物是用它標號的首字母來表示的，只使用英文小寫字母。定貨單的數(shù)目不超過200輸出：輸出文件ORDERS.OUT要包含經(jīng)理訪問倉庫的所有可能順序。例如Order.inorder.outbbjdbbdjbbjdbdbjbdjb bjbdbjdbdbbjdbjbdjbbjbbdjbdbjdbb分析因為題目要求我們輸出所有可能的登記順序，而數(shù)據(jù)的范圍也不大，不難看出它是一個搜索題目。由于方案數(shù)可能會比較大，如果要保存下所有的方案也是沒有必要的，因此我們宜采用深搜而放棄廣搜。一般來講，要確定某個順序第I位上的字母，我們是從“a“到“z”循環(huán)，依次查找，看哪個字母還可以再選，當(dāng)可選字母的比較少，且可選字母中每一個字母又可以選較屢次時，每一重循環(huán)就有很多掃描是多余的。我們可以對這種情況作如下優(yōu)化：在輸入完畢后，先統(tǒng)計出各種字母的總個數(shù)，并且將可選的字母按字典順序依次放入到一個字符串?dāng)?shù)組中〔每個字母最多放一次〕，搜索的時候，我們將從“a”到“z”的循環(huán)改為從頭到尾掃描字符串?dāng)?shù)組，由于該字符串?dāng)?shù)組中的各字母都是可選的，所以我們每掃到一個字母，就將它插入到當(dāng)前方案的序列中，并將它的可選次數(shù)減1如果一個字母已經(jīng)不能再選〔可選次數(shù)為0〕，那么暫時將它從字符串?dāng)?shù)組中刪去，等到當(dāng)前過程遞歸調(diào)用完畢后再將其插入該字符串?dāng)?shù)組。這樣一來，就可以保證每一次循環(huán)掃描到的字母都是可選的，搜索中幾乎沒有了多余的運算搜索剪枝在很多情況下，我們已經(jīng)找到了一組比較好的解。但是計算機仍然會義無返顧地去搜索比它更“劣”的其他解，搜索到后也只能回溯。為了防止出現(xiàn)這種情況，我們需要靈活地去定制回溯搜索的邊界。剪枝1、正確性：剪去的“枝條”不包含最優(yōu)答案2、準確性：在保證第一條原那么的情況下，盡可能的剪去更多不包含最優(yōu)答案的枝條3、高效性：通過剪枝要能夠更快的接近到達最優(yōu)解常用剪枝可行性剪枝最優(yōu)性剪枝例題3：計算機網(wǎng)絡(luò)連接〔gdoi〕要將n(n<=30)臺計算機連成網(wǎng)絡(luò)，連接方法：去除首尾兩臺計算機與一臺計算機相連以外，其他計算機只與兩臺計算機相連。連接的長度那么為計算機連接的電纜的長度。求：一種連接方式，使需要電纜的長度最短分析〔優(yōu)化一〕假設(shè)目前搜索到了一組解，電纜總長度為kx，那么，如果說以后搜索到的連接方法〔不一定是最終連接方法〕的連接長度>=kx，那么這個方案的總長度一定不小于kx，那么，就不必要搜索下去了，直接換下一個結(jié)點繼續(xù)搜索。優(yōu)化二路徑A1-A2-…An與路徑An-An-1-…A1這兩條路徑是一個“正反”的關(guān)系，本質(zhì)上是相同的，于是我們可以規(guī)定起點始的下標總是小于終點的下標優(yōu)化三假設(shè)路徑的A-B-C-D的長度<A-C-B-D的長度，那么包含A-C-B-D路徑的路徑的長度一定不是最短?；厮葸吔缭谏疃葍?yōu)先搜索的過程當(dāng)中，往往有很多走不通的“死路”。假設(shè)我們把這些“死路”排除在外，不是可以節(jié)省很多的時間嗎？打一個比方，前面有一個路徑，別人已經(jīng)提示：“這是死路，肯定不通”，而你的程序仍然很“執(zhí)著”地要繼續(xù)朝這個方向走，走到頭來才發(fā)現(xiàn)，別人的提示是正確的。這樣，浪費了很多的時間。針對這種情況，我們可以把“死路”給標記一下不走，就可以得到更高的搜索效率。例題：N皇后問題采用一般的回溯，就是每一行的每個格子放與不放都搜索一下，實際上，在放置了(1,1)這個皇后，再把皇后放置在(2,1)就是毫無意義的：前面一個皇后一定能攻擊到它。為了防止這種情況，我們這樣做：走了一個棋子以后，把它的“勢力范圍”給圈出來，并且告訴以后的皇后：這里不能放置。例題4：Betsy‘sTour〔USACO〕一個正方形的鎮(zhèn)區(qū)分為N2個小方塊〔1<=N<=7〕。農(nóng)場位于方格的左上角，集市位于右下角。貝茜穿過小鎮(zhèn)，從左上角走到左下角，剛好經(jīng)過每個方格一次。寫一個程序，對于給出的N值，計算貝茜從農(nóng)場走到集市有多少種唯一的路徑例題4：Betsy‘sTour〔USACO〕這一題是一道經(jīng)典題目，我們開始想到用搜索來解決：我們搜索一條在N*N的矩陣中從點〔1，1〕到點〔1，N〕的路徑，然后判斷這個路徑是不是遍歷完所有的點。但是當(dāng)N比較小時，答案可以很快的出來，可是當(dāng)N比較大時，求出答案的時間會很大。例題4：Betsy‘sTour〔USACO〕我們可以想到用可行性剪枝來優(yōu)化。剪枝一：對于某一個沒有訪問過的點〔不包括終點〕，至少有兩個點〔沒有訪問的點或貝茜所在的點〕在他附近。因為一個沒有訪問過的點要被訪問到，一定要一進一出，所以必須要在他附近有兩個點，才能滿足點被全部訪問的要求。例題4：Betsy‘sTour〔USACO〕剪枝二：

我們繼續(xù)分析，當(dāng)這個地圖被分為了兩個或多個連通塊時，能不能全部訪問？答案很顯然，不能！我們就可以再加一個優(yōu)化，判斷當(dāng)前狀態(tài)表示的地圖是不是只有一個連通塊。這樣減少了很多不符合題意的狀態(tài)。例題3：Betsy‘sTour〔USACO〕對于上面的剪枝，每一次行動都要對所有的格子進行判斷。其實我們知道每一次行動后只會對其附近的格子有影響，那么我們不妨只判斷附近格子在操作之后是不是符合題目要求。對于第一個剪枝我們很容易的判斷完，但對于第二個剪枝，怎么判斷呢？例題3：Betsy‘sTour〔USACO〕例題4：Betsy‘sTour〔USACO〕從上面的那個圖中可以知道，當(dāng)出現(xiàn)了上圖的三種情況后，必定是出現(xiàn)了兩個以上的連通塊，不是最后的結(jié)果通過這一個優(yōu)化，我們又進一步的減少了時間復(fù)雜度，解決了這一個問題。提示：這一題可以考慮用狀態(tài)壓縮的動態(tài)規(guī)劃來做。例題5：最少乘法次數(shù)由x開始，通過最少的乘法次數(shù)得出x^n，其中n為輸入數(shù)據(jù)。例題5：最少乘法次數(shù)這題是一道很經(jīng)典的題目，開始我們會想到動態(tài)規(guī)劃來求解，但是用動態(tài)規(guī)劃求解時會出現(xiàn)后效性，所以只能想用別的方法。我們考慮用搜索，設(shè)第一層a[1]=1，那么搜索到第i層時a[i]的值在a[i-1]+1到n的值里面選擇可以到達的值。當(dāng)a[i]=n時，答案為i-1。但是這樣搜索可能會搜到很多狀態(tài)，使得時間復(fù)雜度很大，怎么辦？例題5：最少乘法次數(shù)我們不妨考慮用最優(yōu)化剪枝，現(xiàn)在乘的次數(shù)不比當(dāng)前答案優(yōu)時，我們不用搜索下去，因為從這個狀態(tài)搜索下去的答案肯定不比最后的優(yōu)。這個判斷雖然很好，但是剪枝得不夠徹底，我們繼續(xù)想，如果當(dāng)前的a[i]用最少的乘法到n，這個答案不比當(dāng)前答案優(yōu)時，那就沒有必要搜索下去，我們就可以預(yù)處理從p(=a[i])乘到n，至少要乘多少次。這樣我們能夠很好的解決這問題。例題5：最少乘法次數(shù)但是當(dāng)p>=n/2時，p至少要乘以1次就可以到達n，這樣對于這種情況，前面的剪枝的效果很很低。我們不難發(fā)現(xiàn)，如果p>=n/2時，其實相乘的那些數(shù)都小于n/2，而那些乘的數(shù)之前也計算出來了，就可以考慮用動態(tài)規(guī)劃來求最優(yōu)解，這樣對于p無論在那個值時，都有很好的剪枝來優(yōu)化。例題6：彩票問題：彩票上的數(shù)字：1,2,…,M彩民的選擇：A1,A2,…,An，其中Ai屬于1,2,…,M每人只能買一張彩票，每人彩票選擇都不同抽出兩個自然數(shù)X和Y。如果1/A1+2/A2+…+1/An=X/Y，那么中獎〔獲取紀念品〕。輸入：N，M，X，Y輸出：所需準備的紀念品數(shù)量1≤X,Y≤100，1≤N≤10，1≤M≤50。輸入數(shù)據(jù)保證輸出結(jié)果不超過105。深度優(yōu)先搜索的優(yōu)化從上面兩題我們了解到可行性剪枝和最優(yōu)性剪枝的運用和技巧。其實除了上面的一些剪枝外，還有其他的剪枝技巧。分析：對于每個數(shù)，有選和不選兩種可能性，顯然可以建立如下模型：

x1/1+x2/2+x3/3+…+xm/m=X/Y

其中，xi=0或者1(1<=i<=m)x1+x2+x3+…+xm=n逐個搜索xiO(2m)x1/1+x2/2+x3/3+…+xm/m=X/Y同時乘以m!*Y通分。令Ti=m!*Y/i(1<=i<=m),T0=m!*X那么：T1x1+T2x2+T3x3+…+Tmxm=T0這就變成了一個01背包問題。每個包裹的體積是Ti，箱子體積T0從M個中選N個，填滿箱子。

求方案數(shù)。如何優(yōu)化？？T1x1+T2x2+T3x3+…+Tmxm=T0如何剪枝？f[i,T]表示為了滿足T1x1+T2x2+…+Tmxm=T，最少要讓多少個xi取1。f[i,T]=min{f[i-1,T],f[i-1,T-Ti]+1}按照xm,xm-1,xm-2,…,x1的順序搜索。假設(shè)xp~xm都已經(jīng)取定，令S=Tpxp+Tp+1xp+1+…+Tmxm，L=xp+xp+1+…+xm，如果f[p-1,T-S]+L>N，那么就可以回溯，不必繼續(xù)搜索了。T~O(m!)。太大了！f數(shù)組開不下，時間上也不允許。動態(tài)規(guī)劃的思想，空間矛盾太大。抓住矛盾：解決空間問題！T太大了，可不可以想方法把它變小呢？同余T1x1+T2x2+T3x3+…+Tmxm=T0f[i,T]表示為了滿足T1x1+T2x2+…+Tmxm=T，至少要讓多少個xi取1。f[i,T]=min{f[i-1,T],f[i-1,T-Ti]+1}T1x1+T2x2+T3x3+…+Tmxm=T0f[i,T]表示為了滿足(T1x1+T2x2+…+TmXm)modP=T，至少要讓多少個xi取1。f[i,T]=min{f[i-1,T],f[i-1,(T-Ti)modP]+1}0<=T<P按照xm,xm-1,xm-2,…,x1的順序搜索。假設(shè)xp~xm都已經(jīng)取定，令S=Tpxp+Tp+1xp+1+…+Tmxm，L=xp+xp+1+…+xm，如果f[p-1,(T-S)modP]+L>N，那么就可以回溯，不必繼續(xù)搜索了。剪枝效果有所削弱但是空間復(fù)雜度降到了O(mP)，這里P可以任取。廣度優(yōu)先遍歷廣度優(yōu)先搜索遍歷：類似樹的按層遍歷，其過程為：首先訪問初始點Vi，并將其標記為已訪問過，接著訪問Vi的所有未被訪問過可到達的鄰接點Vi1、Vi2……Vit，并均標記為已訪問過，然后再按照Vi1、Vi2……Vit的次序，訪問每一個頂點的所有未被訪問過的鄰接點，并均標記為已訪問過，依此類推，直到圖中所有和初始點Vi有路徑相通的頂點都被訪問過為止。廣度優(yōu)先搜索隊列實現(xiàn)的框架：VoidBFS(longinitialstate){que.in(initialstate);While(!(que.empty())){state=que.out();for(longi=1;i<=count(state);i++){newstate=make(state,i);if(answer(newstate))printans;elseque.in(newstate);}}}廣度優(yōu)先搜索對于狀態(tài)數(shù)很多時，廣度優(yōu)先搜索可以采用循環(huán)隊列或動態(tài)鏈表來處理。一般的廣度優(yōu)先搜索題目會用到hash表來優(yōu)化判重。例題7：黑白棋游戲(高級本)黑白棋游戲的棋盤由4×4方格陣列構(gòu)成。棋盤的每一方格中放有1枚棋子，共有8枚白棋子和8枚黑棋子。這16枚棋子的每一種放置方案都構(gòu)成一個游戲狀態(tài)。在棋盤上擁有1條公共邊的2個方格稱為相鄰方格。一個方格最多可有4個相鄰方格。在玩黑白棋游戲時，每一步可將任何2個相鄰方格中棋子互換位置。對于給定的初始游戲狀態(tài)和目標游戲狀態(tài)，編程計算從初始游戲狀態(tài)變化到目標游戲狀態(tài)的最短著棋序列。例題5：黑白棋游戲(高級本)這題我們可以想到用深度優(yōu)先搜索來做，但是如果下一步出現(xiàn)了以前的狀態(tài)怎么辦？直接判斷時間復(fù)雜度的可能會有點大，這題的最優(yōu)解法是用廣度優(yōu)先搜索來做我們就可以有初始狀態(tài)按照廣度優(yōu)先搜索遍歷來擴展每一個點，這樣到達目標狀態(tài)的步數(shù)一定是最優(yōu)的〔步數(shù)的增加時單調(diào)的〕。但問題是如果出現(xiàn)了重復(fù)的情況我們就必須要判重，但是樸素的判重是可以到達狀態(tài)數(shù)級別的，其實我們可以考慮用hash表來判重。例題5：黑白棋游戲(高級本)Hash表：思路是根據(jù)關(guān)鍵碼值進行直接訪問。也就是說把一個關(guān)鍵碼值映射到表中的一個位置來訪問記錄的過程。在Hash表中，一般插入，查找的時間復(fù)雜度可以在O〔1〕的時間復(fù)雜度內(nèi)搞定。對于這一題我們可以用二進制值表示其hash值，最多2^16次方，所以我們開個2^16次方的表記錄這個狀態(tài)出現(xiàn)沒有，這樣可以在O〔1〕的時間復(fù)雜度內(nèi)解決判重問題例題7：黑白棋游戲(高級本)進一步考慮：從初始狀態(tài)到目標狀態(tài)，必定會產(chǎn)生很多無用的狀態(tài)，那還有什么優(yōu)化可以減少這時間復(fù)雜度？我們可以考慮把初始狀態(tài)和目標狀態(tài)一起擴展，這樣如果初始狀態(tài)的某個被擴展的點與目標狀態(tài)所擴展的點相同時，那這兩個點不用擴展下去，而兩個擴展的步數(shù)和也就是答案。例題5：黑白棋游戲(高級本)上面的想法是雙向廣度優(yōu)先搜索：就像上圖一樣，少擴展了很多不必要的狀態(tài)廣度優(yōu)先搜索的優(yōu)化從上面一題可以看到我們用到了兩個優(yōu)化：Hash表優(yōu)化；雙向廣搜優(yōu)化；注：一般的廣度優(yōu)先搜索用這兩個優(yōu)化就足以解決。例題8：pku1729在一個N*N(N<=30)的地圖上，有A和B兩個人，地圖上的一些地方為空地，一些地方有障礙不能通過。在每一個時刻A和B必須向四個方向移動(‘N’,’E’,’W’,’S’)，并且AB兩人彼此特別討厭對方，他們希望在移動的時候盡可能的離對方遠，現(xiàn)在知道兩個人分別的起點和終點。求出一條使AB到達終點的路徑，并且在途中AB間最近的距離最遠，在此根底上使AB盡快到達終點。例題8分析題目是要你使首先是要AB都到達終點，然后是要路徑中AB離得盡可能的遠，同時AB要盡快到達。我們很容易想到用廣度優(yōu)先搜索來解決問題，也很容易想到用hash表來表示，為hash[Xa,Ya,Xb,Yb,t]記錄當(dāng)A在〔Xa，Ya〕，B在〔Xb，Yb〕且時間經(jīng)過t時AB的最近距離是多少，或者hash[Xa,Ya,Xb,Yb,d]記錄當(dāng)A在〔Xa，Ya〕，B在〔Xb，Yb〕且最近距離為d時AB所有的最少時間是多少例題8：pku1729但是這樣表示的狀態(tài)很大，有可能到達N^6級別，已經(jīng)超過了所能承受的空間限制。繼續(xù)分析，AB兩個人的距離最多只會相差N^4=810000種可能，我們不妨采用二分最近距離的方法來求解。這是二分次數(shù)最多只需要log2810000<20次即可例題8：pku1729我們重新定義hash值，假設(shè)當(dāng)前二分到最近距離為x，那么hash[Xa,Ya,Xb,Yb]記錄A在〔Xa，Ya〕，B在〔Xb，Yb〕時，且最近距離大于x時的最少時間。我們成功的把狀態(tài)量降低為(N^4)，已經(jīng)很好的解決這空間問題，而時間復(fù)雜度為O(N^4*20)，很好的解決了這個問題?？偨Y(jié)：我們通過二分的方法使空間和時間復(fù)雜度都降低了很多。深度優(yōu)先搜索和廣度優(yōu)先搜索深度優(yōu)先搜索廣度優(yōu)先搜索遍歷方式深度優(yōu)先搜索遍歷廣度優(yōu)先搜索遍歷所用數(shù)據(jù)結(jié)構(gòu)棧隊列一般優(yōu)化最優(yōu)性剪枝可行性剪枝Hash判重雙向搜索討論：什么時候用深度優(yōu)先搜索好？什么時候用廣度優(yōu)先搜索好？A*算法介紹A*算法前，先介紹下估價函數(shù)和貪心搜索估價函數(shù)：在解決問題的時候常常會估計狀態(tài)離目標狀態(tài)到底有多接近，進而對多種方案進行選擇。放在搜索中來，可以有一個狀態(tài)的估價函數(shù)來估計它到目標狀態(tài)的距離。定義h(s)表示當(dāng)前狀態(tài)s到目標狀態(tài)的估價。貪心搜索：像廣度優(yōu)先搜索一樣用一個優(yōu)先隊列按其h(s)來儲存待擴展，但是由于h(s)不準確，所以不能保證是最優(yōu)解。A*算法和貪心算法很類似，它不是按h值來計算，而是按另外一個函數(shù)值f使得f是由啟始狀態(tài)到目標狀態(tài)的估價。設(shè)g(s)為目標狀態(tài)到達現(xiàn)在狀態(tài)s的代價，那么f(s)=g(s)+h(s)。因為對于任意兩個狀態(tài)s1,s2滿足h(s1)<=h(s2)+w(s1,s2);W(s1,s2)s1轉(zhuǎn)移到s2的代價。那么對于狀態(tài)s1,s2,且s2是s1