1、搜索FZUACM集訓(xùn)隊(duì) 陳頂搜索FZU某大牛說過，一切題目皆搜索，只不過搜索的空間，范圍不同而已在比賽中碰到的題目其實(shí)很多都是搜索題，只不過搜索的范圍不同，有的只能盲目地搜索，有的可以在小范圍內(nèi)搜索搜索就是給出初始狀態(tài)和目標(biāo)狀態(tài),以及一些約束條件,要求尋找在符合這些約束條件的情況下,從初始狀態(tài)到目標(biāo)狀態(tài)的解搜索的分類暴力枚舉（完全盲目的搜索所有可能的狀態(tài)，沒人不會(huì)吧，這里不再贅述）深度優(yōu)先搜索（DFS）廣度優(yōu)先搜索（BFS）啟發(fā)式搜索A*IDA*較為復(fù)雜的智能搜索，這里不做介紹暴搜這恐怕是大家最喜歡的算法了，想不出來，就暴力！最土最土的暴力就是枚舉了即枚舉所有可行解USACO Prime Cr

2、yptarithm沒有什么好說的，對(duì)于被乘數(shù)和乘數(shù)，枚舉所有給出的數(shù)字，O(105)，完全可以接受當(dāng)然，根據(jù)算式的特點(diǎn)還可以進(jìn)行相應(yīng)的剪枝剪枝何謂剪枝？剪枝就是搜索過程中把不必要，不可能的狀態(tài)去掉，不必列入考慮的范圍就像走迷宮時(shí)已經(jīng)知道哪些路是死路，不繼續(xù)往下走一樣深度優(yōu)先搜索(DFS)在深度優(yōu)先搜索中,從初始節(jié)點(diǎn)開始擴(kuò)展, 總是先擴(kuò)展最新產(chǎn)生的節(jié)點(diǎn).這就使得搜索沿著狀態(tài)空間的某條單一的路徑進(jìn)行下去,直到搜索出符合我們要求的目標(biāo)節(jié)點(diǎn)。因此,深度優(yōu)先搜索第一個(gè)找到的解并不一定是問題的最優(yōu)解,要綜合所有的解,才能確定哪個(gè)解為最優(yōu)解.與棧性質(zhì)相似通過遞歸實(shí)現(xiàn)經(jīng)常需要剪枝回溯，純暴力一般會(huì)超時(shí)USAC

3、O Superprime Rib直接DFS 19，加入當(dāng)前數(shù)末尾，并判斷是不是素?cái)?shù)，是則遞歸處理下一位數(shù)，不是則回溯，直到位數(shù)n。加幾個(gè)剪枝1.首位只能是質(zhì)數(shù)2 3 5 7 2.其余位只能是1 3 7 9 （為什么？）3.若n=1，直接輸出2 3 5 7USACO Superprime RibN皇后問題搜索中一個(gè)經(jīng)典問題在一個(gè)N*N棋盤上放置N個(gè)國(guó)際象棋的皇后，使得相互不攻擊，求放置方案數(shù)暴力枚舉顯然超時(shí)我們使用幾個(gè)bool數(shù)組記錄該行，該列，該對(duì)角線是否有皇后，每次搜索的時(shí)候只要擴(kuò)展沒有皇后的狀態(tài)即可，這樣一來優(yōu)化了不少但是N稍微大一點(diǎn)還是受不了TLE考慮對(duì)稱性將棋盤對(duì)折，一個(gè)方案可行，那么

4、與這個(gè)方案對(duì)稱的方案也可行剪掉一半狀態(tài)了N再大，還是TLE其他優(yōu)化位運(yùn)算劉汝佳黑書上提到啟發(fā)式修補(bǔ)（相當(dāng)深?yuàn)W）Dancing linkN皇后問題表達(dá)式求解總共最多就11個(gè)整數(shù)，10個(gè)符號(hào)只有兩種符號(hào)|和&所有可能的狀態(tài)210完全在1s可承受的范圍之內(nèi)，暴力枚舉！如何實(shí)現(xiàn)？DFS表達(dá)式求解從第一個(gè)數(shù)字后面的第一個(gè)符號(hào)開始向后拓展，逐層深入，對(duì)于每層，要拓展的狀態(tài)只有兩種：|或&程序的遞歸框架出現(xiàn)表達(dá)式求解Void dfs(int x)if (x=n).;return;/到最后一層，計(jì)算表達(dá)式并回溯f=|;/分別拓展兩種狀態(tài)dfs(x+1);f=&;dfs(x+1);Equation這題規(guī)模有點(diǎn)大

5、，像剛才那樣暴力枚舉可能會(huì)超時(shí)，不過答案只有19*10種，我們可以打表怎么打？和剛才那題一樣，DFS，對(duì)于每層，向下拓展只有3種狀態(tài)，+或-或 程序框架類似DFS深度優(yōu)先搜索所遵循的搜索策略是盡可能“深”地搜索。在深度優(yōu)先搜索中，對(duì)于最新發(fā)現(xiàn)的頂點(diǎn)，如果它還有以此為起點(diǎn)而未探測(cè)到的邊，就沿此邊繼續(xù)下去。當(dāng)結(jié)點(diǎn)v的所有邊都己被探尋過，搜索將回溯到發(fā)現(xiàn)結(jié)點(diǎn)v有那條邊的始結(jié)點(diǎn)。這一過程一直進(jìn)行到已發(fā)現(xiàn)從源結(jié)點(diǎn)可達(dá)的所有結(jié)點(diǎn)為止。如果還存在未被發(fā)現(xiàn)的結(jié)點(diǎn)，則選擇其中一個(gè)作為源結(jié)點(diǎn)并重復(fù)以上過程，整個(gè)進(jìn)程反復(fù)進(jìn)行直到所有結(jié)點(diǎn)都被發(fā)現(xiàn)為止。 void dfs(i)for i:=1 to r do if 子

6、節(jié)點(diǎn) mr 符合條件 產(chǎn)生的子節(jié)點(diǎn)mr入棧； if 子節(jié)點(diǎn)mr是目標(biāo)節(jié)點(diǎn) 輸出 else dfs(i+1); 棧頂元素出棧（即刪去mr）；DFS框架廣度優(yōu)先搜索廣度優(yōu)先搜索（BFS）是從初始節(jié)點(diǎn)開始,利用這個(gè)狀態(tài)去生成下一層的狀態(tài)(可能不止一個(gè)),同時(shí)檢查目標(biāo)狀態(tài)是否在這些新生成的狀態(tài)中,如果在,則得到結(jié)果,否則,在利用這些新生成的狀態(tài)繼續(xù)反復(fù)擴(kuò)展,直到目標(biāo)狀態(tài)出現(xiàn)。 先產(chǎn)生的狀態(tài)先進(jìn)行擴(kuò)展.且要擴(kuò)展出這種狀態(tài)的所有下一狀態(tài).與隊(duì)列性質(zhì)相似，實(shí)現(xiàn)時(shí)常利用STL的queue最壞情況需遍歷所有可行狀態(tài)USACO Mothers Milk和FOJ的等分液體類似3個(gè)桶的容量最大為20，而牛奶總量一定，

7、可能的狀態(tài)不超過20*20*20種可以開一個(gè)三維bool數(shù)組can212121記錄狀態(tài)，canijk表示A桶i升牛奶，B桶j升，C桶k升這種狀態(tài)是否可達(dá)初始狀態(tài)為can00c=true目標(biāo)狀態(tài)為求所有k，滿足can0c-kk=true從初始狀態(tài)一遍BFS即可得出解PKU 1915 Knight Moves 廣度優(yōu)先搜索有一類題目就是最短路問題，當(dāng)然這里規(guī)模都比較小像小鼠迷宮那樣一格一格走的模型像這題這種馬走方格的模型給出起點(diǎn)和終點(diǎn)，求最少步數(shù)Distnm保存從起點(diǎn)到地圖各點(diǎn)的最短距離初始狀態(tài)Dists.xs.y=0，目標(biāo)狀態(tài)Diste.xe.y搜索時(shí)按照馬的走法每次向八個(gè)方向擴(kuò)展?fàn)顟B(tài)以此題為例

8、初始化：清空隊(duì)列，Dist數(shù)組賦初值為無窮大，Dists.xs.y=0，s入隊(duì)列While (隊(duì)列非空） 隊(duì)首元素出隊(duì)，作為當(dāng)前狀態(tài) 向八個(gè)方向擴(kuò)展?fàn)顟B(tài)，并判斷是否超出邊界 若當(dāng)前狀態(tài)的dist+1擴(kuò)展?fàn)顟B(tài)的dist 則更新擴(kuò)展?fàn)顟B(tài)dist，擴(kuò)展?fàn)顟B(tài)入隊(duì)目標(biāo)狀態(tài)Diste.xe.y即為所求 BFS 框架 CDGGs knight廣搜常用于求最短路中這道比較經(jīng)典的廣搜題首先對(duì)于棋盤每個(gè)點(diǎn)(x,y)，要求出到所有點(diǎn)的最短距離，用distxyij保存，這需要做n*m次BFS，每次BFS就是一次求最短路的過程對(duì)于CDGG，做一次BFS，求出CDGG到每個(gè)點(diǎn)的最短距離CDGGs knight我們要做的事

9、1.確定集合點(diǎn)2.確定去馱CDGG的那個(gè)騎士，或者讓CDGG自己走3.如果有人馱CDGG，還要確定CDGG和那個(gè)騎士在哪里碰面CDGGs knight如果所有的不確定值都用枚舉的話，超時(shí)將不是一般的嚴(yán)重幾個(gè)剪枝1.確定去馱CDGG的那個(gè)騎士和大家的集合點(diǎn)以后，如果其他騎士到集合點(diǎn)的最短路之和已經(jīng)大于當(dāng)前最小的答案，那么直接退出，不必枚舉CDGG和馱他的騎士的集合點(diǎn)CDGGs knight2.王和騎士的相遇點(diǎn)可能出現(xiàn)在哪些位置上？顯然王走的比騎士要慢，那么應(yīng)該盡量要讓王少走。不難發(fā)現(xiàn)，相遇點(diǎn)只應(yīng)該在王的附近很短的距離以內(nèi)。估算一下，相遇點(diǎn)就在王的坐標(biāo)加減2的范圍內(nèi)枚舉就可以了加上這兩個(gè)剪枝，順利

10、AC Reversi Game 復(fù)活賽中我的一道題題由于棋盤比較小4*4，并且只有0或1兩種狀態(tài)，所以共有216種狀態(tài)，可以承受從起始狀態(tài)到目標(biāo)狀態(tài)的拓展，很明顯，BFS問題Reversi Game 對(duì)于每一種狀態(tài)，將其表示成一個(gè)二進(jìn)制數(shù)，狀態(tài)之間的轉(zhuǎn)換即二進(jìn)制數(shù)某特定的兩位上01的交換已知起始和終止的二進(jìn)制數(shù)，求最小轉(zhuǎn)換步數(shù)Reversi Game 初始時(shí)初始二進(jìn)制數(shù)入隊(duì)每次拓展時(shí)取隊(duì)首元素進(jìn)行拓展枚舉交換的位，16種枚舉與其交換的位，上下左右，4種每次拓展16*4個(gè)狀態(tài)注意判重，去除重復(fù)的狀態(tài)找到目標(biāo)狀態(tài)即退出，記錄下步數(shù)Reversi Game 由于使用二進(jìn)制數(shù)表示狀態(tài)，那么可以使用位運(yùn)

11、算加速主要處理1個(gè)數(shù)的兩位交換Reversi Game void reser(int i,int j,int &num) /交換num的i,j兩位int i,j,iz,jz; iz=num&(1i);jz=num&(1j); if (iz) num|=(1j); else if (jz) num-=(1j); if (jz) num|=(1i); else if (iz) num-=(1=0地圖上0的地方不能走！橫著的時(shí)候占兩格，都不能為0！從起始狀態(tài)到目標(biāo)狀態(tài)過程中，不能經(jīng)過目標(biāo)狀態(tài)！只有最后才可以！當(dāng)然只能是豎起來的時(shí)候才要考慮相當(dāng)惡心的題題BloxOrz 搜索的優(yōu)化很多問題會(huì)有比較復(fù)雜的情況和比較特殊的約束條件,很容易就會(huì)TLE.優(yōu)化就是使得我們?cè)谒阉鬟^程中盡量去除不必要的狀態(tài),使得盡可能快的找到目標(biāo)狀態(tài).常用優(yōu)化方法1.判重去除和以前相同的狀態(tài),避免重復(fù)的搜索空間允許的話 直接利用數(shù)組保存Hash,二叉搜索樹等查找復(fù)雜度為O(nlgn)的數(shù)據(jù)結(jié)構(gòu)來保存利用二進(jìn)制數(shù)的位來保存常用優(yōu)化方法2.加入記憶化對(duì)于某些問題，已經(jīng)搜索過的狀態(tài)記