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

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

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

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

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

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

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