3、“死路”排除在外，不是可以節(jié)省很多的時(shí)間嗎？打一個(gè)比方，前面有一個(gè)路徑，別人已經(jīng)提示：“這是死路，肯定不通”，而你的程序仍然很“執(zhí)著”地要繼續(xù)朝這個(gè)方向走，走到頭來(lái)才發(fā)現(xiàn)，別人的提示是正確的。這樣，浪費(fèi)了很多的時(shí)間。針對(duì)這種情況，我們可以把“死路”給標(biāo)記一下不走，就可以得到更高的搜索效率。*例題皇后問(wèn)題分析取n=4為例采用一般的回溯，就是每一行的每個(gè)格子放與不放都搜索一下：然后回溯一次，換下一個(gè)點(diǎn)繼續(xù)搜索。這個(gè)算法的效率，是實(shí)際上，在放置了(1,1)這個(gè)皇后，再把皇后放置在(2,1)就是毫無(wú)意義的：前面一個(gè)皇后一定能攻擊到它。為了避免這種情況，我們這樣做：走了一個(gè)
4、棋子以后，把它的“勢(shì)力范圍”給圈出來(lái)，并且告訴以后的皇后：這里不能放置。舉簡(jiǎn)單的例子：放置皇后(1,1)，由于打“.”的格子在放了(1,1)這顆子之后，被標(biāo)注為了“不能走”，所以這些點(diǎn)我們就不去理會(huì)了。這樣就節(jié)省了很多時(shí)間，大大提高了搜索的效率。而對(duì)于很多回溯的題目，我們都可以采用分枝定界法，把搜索樹(shù)中不必要的枝剪去，大大提高了搜索的效率。[記憶化]對(duì)于一些有最優(yōu)子結(jié)構(gòu)的問(wèn)題，我們往往采用動(dòng)態(tài)規(guī)劃算法來(lái)實(shí)現(xiàn)。采用動(dòng)態(tài)規(guī)劃算法，需要弄清狀態(tài)以及狀態(tài)是如何轉(zhuǎn)移的，接著列出狀態(tài)轉(zhuǎn)移方程。首先舉一個(gè)非常簡(jiǎn)單的例子 *例題數(shù)字三角形 分析無(wú)論對(duì)與新手還是老手，這
5、都是再熟悉不過(guò)的題了，很容易地，我們寫(xiě)出狀態(tài)轉(zhuǎn)移方程： f(i,j)=a[i,j]+min{f(i+1,j)+f(i,j+1)}對(duì)于動(dòng)態(tài)規(guī)劃算法解決這個(gè)問(wèn)題，我們根據(jù)狀態(tài)轉(zhuǎn)移方程和狀態(tài)轉(zhuǎn)移方向，比較容易地寫(xiě)出動(dòng)態(tài)規(guī)劃的循環(huán)表示方法。但是，當(dāng)狀態(tài)和轉(zhuǎn)移非常復(fù)雜的時(shí)候，也許寫(xiě)出循環(huán)式的動(dòng)態(tài)規(guī)劃就不是那么簡(jiǎn)單了。我們嘗試從正面的思路去分析問(wèn)題，如上例，不難得出一個(gè)非常簡(jiǎn)單的遞歸過(guò)程：if(i==0)return(a[i,j]);f1=f(i+1,j);f2=f(i,j+1);iff1>f2returna[i,j]+f1;elsereturna[i,j]+f2;
6、顯而易見(jiàn)，這個(gè)算法就是最簡(jiǎn)單的搜索算法。時(shí)間復(fù)雜度為2n，明顯是會(huì)超時(shí)的。分析一下搜索的過(guò)程，實(shí)際上，很多調(diào)用都是不必要的，也就是把產(chǎn)生過(guò)的最優(yōu)狀態(tài)，又產(chǎn)生了一次。為了避免浪費(fèi)，很顯然，我們存放一個(gè)opt數(shù)組：Opt[i,j]-每產(chǎn)生一個(gè)f(i,j)，將f(i,j)的值放入opt中，以后再次調(diào)用到f(i,j)的時(shí)候，直接從opt[i,j]來(lái)取就可以了?！ ∮谑莿?dòng)態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程被直觀地表示出來(lái)了，這樣節(jié)省了思維的難度，減少了編程的技巧，而運(yùn)行時(shí)間只是相差常數(shù)的復(fù)雜度，而且在相當(dāng)多的情況下，遞歸算法能更好地避免浪費(fèi)，在比賽中是非常實(shí)用的?！ 】偨Y(jié)記憶
7、化搜索是對(duì)動(dòng)態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移方程的直觀表示。本質(zhì)上來(lái)說(shuō)，它仍然是用搜索算法的核心，只不過(guò)使用“記錄求過(guò)的狀態(tài)”的辦法，來(lái)避免重復(fù)搜索，這樣，記憶化搜索的每一步，也可以對(duì)應(yīng)到動(dòng)態(tài)規(guī)劃算法中去。記憶化搜索有優(yōu)化方便、調(diào)試容易、思維直觀的優(yōu)點(diǎn)，但是效率上比循環(huán)的動(dòng)態(tài)規(guī)劃差一個(gè)常數(shù)，但是時(shí)間和空間復(fù)雜度是同一數(shù)量級(jí)的（盡管空間上也差一個(gè)常數(shù)，那就是堆?？臻g）。當(dāng)n比較小的時(shí)候，我們可以忽略這個(gè)常數(shù)，從而記憶化搜索可以和動(dòng)態(tài)規(guī)劃達(dá)到完全相同的效果。[BFS] [雙向搜索] 在bfs算法所能解決的問(wèn)題當(dāng)中，有相當(dāng)一部分，是給你初狀態(tài)和末狀態(tài)，讓你求一條從初狀態(tài)到
8、末狀態(tài)的最
