搜索算法的通用優(yōu)化方法

[DFS]
[搜索剪枝]
在很多情況下，我們已經(jīng)找到了一組比較好的解。但是計(jì)算機(jī)仍然會(huì)義無(wú)返顧地去搜索比它更“劣”的其他解，搜索到后也只能回溯。為了避免出現(xiàn)這種情況，我們需要靈活地去定制回溯搜索的邊界。
*例題 計(jì)算機(jī)網(wǎng)絡(luò)連接
要將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)度最短。
分析這個(gè)題目用回溯搜索來(lái)解決。但是，由于回溯搜索的搜索量比較大，達(dá)到了n!，是不可能搜索完n=30的情況的，所以，我們考慮對(duì)它進(jìn)行優(yōu)化：
假如目前搜索到了一組解，電纜總長(zhǎng)度為kx，那么，如果說(shuō)以后搜索到的連接方法（不一定是最終連接方法）的連接長(zhǎng)度>=kx，那么這個(gè)方案的總長(zhǎng)度一定不小于kx，那么，就不必要搜索下去了，直接換下一個(gè)結(jié)點(diǎn)繼續(xù)搜索。
路徑A1-A2-…An與路徑An-An-1-…A1這兩條路徑是一個(gè)“正反”的關(guān)系，本質(zhì)上是相同的，于是我們可以規(guī)定起點(diǎn)始的下標(biāo)總是小于終點(diǎn)的下標(biāo)
假如路徑的A-B-C-D的長(zhǎng)度<A-C-B-D的長(zhǎng)度，那么包含A-C-B-D路徑的路徑的長(zhǎng)度一定不是最短。
有了上述的優(yōu)化，題目就可以得到很快的解決了。
在深度優(yōu)先搜索的過(guò)程當(dāng)中，往往有很多走不通的“死路”。假如我們把這些“死路”排除在外，不是可以節(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è)棋子以后，把它的“勢(shì)力范圍”給圈出來(lái)，并且告訴以后的皇后：這里不能放置。舉簡(jiǎn)單的例子：放置皇后(1,1)，由于打“.”的格子在放了(1,1)這顆子之后，被標(biāo)注為了“不能走”，所以這些點(diǎn)我們就不去理會(huì)了。這樣就節(jié)省了很多時(shí)間，大大提高了搜索的效率。
而對(duì)于很多回溯的題目，我們都可以采用分枝定界法，把搜索樹中不必要的枝剪去，大大提高了搜索的效率。




[記憶化]
對(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ì)與新手還是老手，這都是再熟悉不過(guò)的題了，很容易地，我們寫出狀態(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)移方向，比較容易地寫出動(dòng)態(tài)規(guī)劃的循環(huán)表示方法。但是，當(dāng)狀態(tài)和轉(zhuǎn)移非常復(fù)雜的時(shí)候，也許寫出循環(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);
if f1>f2 return a[i, j] + f1; else return a[i, j] + f2;
顯而易見(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í)用的。
　　　　總結(jié)記憶化搜索是對(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)到末狀態(tài)的最短路，實(shí)際上，bfs的結(jié)點(diǎn)產(chǎn)生系統(tǒng)也最適合解決這一類的問(wèn)題。對(duì)于無(wú)休止以指數(shù)級(jí)膨脹的隊(duì)列長(zhǎng)度，選手們往往束手無(wú)策。
　　　　　　其實(shí)這一類問(wèn)題，有一個(gè)比較難實(shí)現(xiàn)，但是卻能很好提高算法效率的辦法，那就是，我們從初始結(jié)點(diǎn)開始擴(kuò)展，每擴(kuò)展一層（暫時(shí)稱它為f1），再?gòu)哪繕?biāo)結(jié)點(diǎn)按照產(chǎn)生系統(tǒng)相反的辦法來(lái)擴(kuò)展結(jié)點(diǎn)（稱它為f2），直到f1和f2產(chǎn)生出了相同的結(jié)點(diǎn)，把中間路線輸出就可以了。
　　　　　　這一類問(wèn)題，很明顯，需要狀態(tài)產(chǎn)生是可逆并且容易實(shí)現(xiàn)的。太復(fù)雜的逆向狀態(tài)產(chǎn)生也許會(huì)帶來(lái)更大的副面效果，為了更好地對(duì)比這兩種算法的優(yōu)劣，我繪制了一張函數(shù)圖像：
很容易看出，雙向搜索比單向搜索在數(shù)量級(jí)不斷增大的時(shí)候，雙向搜索所體現(xiàn)出的優(yōu)勢(shì)就非常明顯了。擴(kuò)展次數(shù)越多，這個(gè)差距越明顯。假設(shè)一個(gè)結(jié)點(diǎn)產(chǎn)生系統(tǒng)呈二叉樹狀增長(zhǎng)，那么擴(kuò)展n次的代價(jià)，單向是2n，而雙向則是2*2n/2=2n/2+1，兩者相差甚遠(yuǎn)。
　　　　*例題 魔板問(wèn)題
　　　　分析這個(gè)題描述的非常明確：給定初始狀態(tài)和目標(biāo)狀態(tài)和狀態(tài)產(chǎn)生系統(tǒng)，要求從初狀態(tài)到末狀態(tài)的最短路徑，符合上述雙向bfs的特點(diǎn)。很明顯，我們可以用雙向廣度搜索來(lái)解決。
　　　　　　對(duì)于每一個(gè)狀態(tài)，有兩種存儲(chǔ)方式：
直接用8個(gè)Byte類型存儲(chǔ)
用一個(gè)Longint類型壓縮存儲(chǔ)
雖然（2）略浪費(fèi)了一些時(shí)間，但是卻節(jié)省了一半的空間，對(duì)于狀態(tài)比較多的情況，這是很合算的，因?yàn)檎加每臻g變大，勢(shì)必造成時(shí)間的增加，在狀態(tài)較多的情況下，兩者是比較平衡的。
雙向bfs比較難于掌握，比較重要的原因，是因?yàn)樗族e(cuò)。本來(lái)檢查左右兩邊是否重合的過(guò)程就比較復(fù)雜，而且一旦兩邊擴(kuò)展的結(jié)點(diǎn)沒(méi)有查找到（兩端的搜索“失之交臂”），往往該程序會(huì)陷入死循環(huán)。所以實(shí)際處理的時(shí)候，一定要相當(dāng)細(xì)心。
本題還可以和下面即將介紹的散列表聯(lián)用，會(huì)收到非常良好的效果。
小結(jié)雙向bfs應(yīng)用范圍還是相當(dāng)廣泛的，所有已知初狀態(tài)和末狀態(tài)，讓你求一條從初狀態(tài)到末狀態(tài)的最短路的一類問(wèn)題，幾乎都可以用本算法來(lái)解決。本算法思想非常簡(jiǎn)單，但是實(shí)現(xiàn)卻比較困難，需要比較多的編程經(jīng)驗(yàn)和比較豐富的編程技巧，但是換來(lái)的效果也是非常明顯的，一般競(jìng)賽時(shí)不推薦使用，但是真正做題是，雙向bfs無(wú)疑是一種高效的優(yōu)化途徑。
[散列表]
很明顯，寬度優(yōu)先搜索產(chǎn)生的狀態(tài)是非常多的，因?yàn)閿U(kuò)展結(jié)點(diǎn)是不必要回溯，所以寬度搜索是一種以空間換時(shí)間的搜索策略，對(duì)空間占用量比較大，所以空間上的優(yōu)化成為寬度搜索的主要優(yōu)化之一，而避免重復(fù)狀態(tài)又是減少空間浪費(fèi)的最主要途徑。拿迷宮問(wèn)題為例，如果根本不避免重復(fù)狀態(tài)直接搜索，其空間復(fù)雜度約為2m+n，而如果避免了重復(fù)狀態(tài)，時(shí)間復(fù)雜度為m*n，這兩個(gè)數(shù)據(jù)的大小有著天壤之別。
避免重復(fù)狀態(tài)，也就是在生成一個(gè)狀態(tài)以后，把它記錄在一種形式的表里，接著在以后產(chǎn)生狀態(tài)以后，判斷這個(gè)表里是否含有這個(gè)狀態(tài)，不難看出，這實(shí)際上就是一個(gè)插入和查找的過(guò)程。
為了使插入和查找更加地迅速，我們可以采取散列表這種數(shù)據(jù)結(jié)構(gòu)，因?yàn)橹挥兴?，才能在非常短的時(shí)間內(nèi)實(shí)現(xiàn)插入和查找，插入的時(shí)間復(fù)雜度和鏈接表相當(dāng)，而查找的速度遠(yuǎn)遠(yuǎn)快于二分法。當(dāng)建立一個(gè)完整狀態(tài)的隊(duì)列（狀態(tài)表）不是很困難的時(shí)候，散列表往往也能夠隨之起到很重要的作用，大大提高時(shí)間復(fù)雜度。
　　　　*例題 解密牛語(yǔ)
　　　　分析基于密碼編譯規(guī)則，我們很容易地可以想出一個(gè)非常簡(jiǎn)單的dfs方法，當(dāng)然，那是明顯要超時(shí)的，于是我們不得不采用寬度優(yōu)先搜索算法。這個(gè)題有幾個(gè)比較常規(guī)的剪枝，在這里就不一一列舉了。我們看一看搜索的主體部分。
Bfs不能避免的是重復(fù)狀態(tài)，而用循環(huán)判斷重復(fù)是得不償失的，在狀態(tài)多的情況下，循環(huán)法甚至比dfs效率更低，而且低得多。本題難就難在字符串的散列壓縮上。首先，我們需要明確的，是散列表對(duì)于字符串，是不可能做到一對(duì)一的映射的，那么我們不可避免地，要把字符串以一定的函數(shù)轉(zhuǎn)換為編號(hào)，并且進(jìn)行取mod。事實(shí)證明，我們?cè)趆ash表里再存儲(chǔ)一次狀態(tài)，空間上是吃不消的（盡管那樣是保證正確的），于是我們根據(jù)字符序數(shù)和位置取得hash地址，并且直接對(duì)hash[p]賦值，選取適當(dāng)?shù)膆ash函數(shù)，還是可以有效地解決問(wèn)題的。
根據(jù)hash表的原則，mod的數(shù)值最好取1.1a~1.6a之間的一個(gè)質(zhì)數(shù)，在具體實(shí)現(xiàn)中，我們?nèi)?02973，收到比較良好的效果。
　　　　總結(jié)散列表同記憶化搜索一樣，是非常重要的搜索優(yōu)化方式，同記憶化搜索一樣，它能夠把搜索算法的效率從大指數(shù)級(jí)提高到小指數(shù)級(jí)、多項(xiàng)式級(jí)甚至常數(shù)級(jí)。同時(shí)，作為一種高效查找方法，散列表以及散列表的思想滲透在了計(jì)算機(jī)技術(shù)當(dāng)中，成為很多算法的核心。
在這里，使用散列表還有很多技巧：例如也許從現(xiàn)有狀態(tài)出發(fā)，推出不重復(fù)的散列地址來(lái)很困難，選手就可以嘗試著用一個(gè)比較簡(jiǎn)單的方法推出一個(gè)可能重復(fù)的、或者數(shù)量非常大的特征狀態(tài)，然后用mod大數(shù)或者拉鏈解決沖突的方法來(lái)處理，同樣能夠收到良好的效果。
散列表的優(yōu)化技術(shù)并不困難，但是散列函數(shù)的構(gòu)造、處理沖突的技巧和散列表運(yùn)用的角度，是很值得思考的問(wèn)題。具體方法可以參見(jiàn)《數(shù)據(jù)結(jié)構(gòu)》和相關(guān)例題。




[估價(jià)函數(shù)]
啟發(fā)式搜索的主要目標(biāo)是使用一個(gè)函數(shù)去判斷所有狀態(tài)的“好壞”，以提高搜索找到解的效率。
通常，估價(jià)函數(shù)表示成一個(gè)函數(shù)或是一個(gè)狀態(tài)，這個(gè)函數(shù)叫做“估價(jià)函數(shù)”。對(duì)于相同的題目，有時(shí)有不同的估價(jià)函數(shù)。直觀地看，越優(yōu)秀的估價(jià)函數(shù)，搜索的速度就越快。當(dāng)然，估價(jià)函數(shù)不一定是十全十美的（否則就是貪心法了），總歸會(huì)對(duì)某些狀態(tài)予以不太準(zhǔn)確的評(píng)價(jià)，于是，評(píng)價(jià)值（函數(shù)返回值）和實(shí)際好壞的差異越小，估價(jià)函數(shù)就越優(yōu)秀。
注意！一個(gè)人腦看起來(lái)似乎非常非常弱智甚至笑它太傻的估價(jià)函數(shù)可能收到非常大的效果，也許搜索算法的運(yùn)行時(shí)間（或空間）會(huì)縮小100000倍甚至更多。
對(duì)于啟發(fā)式搜索的應(yīng)用，有以下幾點(diǎn)：
（1）啟發(fā)式剪枝
最簡(jiǎn)單也是最常用的啟發(fā)式搜索是利用估價(jià)函數(shù)來(lái)剪枝。假設(shè)我們的問(wèn)題是要求找最小總花費(fèi)。對(duì)于一個(gè)可接受的估價(jià)函數(shù)，當(dāng)前花費(fèi)是A，啟發(fā)函數(shù)返回了B，當(dāng)前子問(wèn)的最優(yōu)解是A+B。如果找到的一個(gè)解一個(gè)花費(fèi)是C，C<A+B，這個(gè)狀態(tài)就不必要搜索了。
這樣編寫和調(diào)試也比較簡(jiǎn)單（假設(shè)一個(gè)狀態(tài)需要長(zhǎng)時(shí)間而被剪掉……），且可以極大地提高程序效率。它對(duì)DFS尤其有效。
（2）最佳優(yōu)先搜索
這種方法好比就是貪心算法。
每次不擴(kuò)展所有子結(jié)點(diǎn)，而是按“好壞程度”來(lái)擴(kuò)展。與貪心不同的是，貪心只嘗試“最優(yōu)”路徑，但是BFS首先擴(kuò)展“希望大”的，再擴(kuò)展“希望小”的，如果結(jié)合上述描述，搜索會(huì)得到很好的結(jié)果。
（3）A*法
A*法是類似貪心的BFS。
BFS一般擴(kuò)展最小耗費(fèi)的點(diǎn)。A*算法在另一方面，擴(kuò)展最有希望的點(diǎn)（估價(jià)函數(shù)返回值最優(yōu)）。
狀態(tài)被保存在一個(gè)優(yōu)先隊(duì)列中，按照Cost*價(jià)值排列。每一次，程序處理最低優(yōu)先的點(diǎn)，且把它的孩子按照適當(dāng)順序處理。
對(duì)于一個(gè)可容許的估價(jià)函數(shù)，第一個(gè)找到的狀態(tài)保證是最優(yōu)的。
*例題 八數(shù)碼問(wèn)題
明顯的，我們可以用hash表的辦法，映射每一個(gè)八數(shù)碼狀態(tài)，總搜索量為9!=362880。這個(gè)數(shù)值很小，是完全可以忍受的。但是，如果采用了估價(jià)函數(shù)進(jìn)行優(yōu)化，采用最佳優(yōu)先搜索方法，會(huì)收到更好的效果。
八數(shù)碼問(wèn)題有一個(gè)非常經(jīng)典的估價(jià)函數(shù)：
對(duì)于數(shù)碼每一個(gè)方格和目標(biāo)的差距相加，例如：
估價(jià)函數(shù)返回的值為：
2 + 1 + 1 + 0 + 1 + 1 + 2 + 0 + 2 = 10
返回值越小，說(shuō)明該狀態(tài)離目標(biāo)狀態(tài)最近。雖然這個(gè)啟發(fā)函數(shù)不完美，誤判的情況很多，但是它能夠非常大地提高搜索效率，在n比較大的時(shí)候，有助于在非常短的時(shí)間內(nèi)找到可行解，并且可以用收縮節(jié)點(diǎn)的辦法，找出更優(yōu)的可行解。
小結(jié)啟發(fā)式搜索并不是完美的搜索。無(wú)論怎樣的啟發(fā)函數(shù)，都會(huì)存在一定的缺陷，但是缺陷并不影響搜索效率的提高。競(jìng)賽和實(shí)際問(wèn)題中，越來(lái)越多的問(wèn)題，不要求最優(yōu)解，只要求可行解，但是往往找這些可行解相當(dāng)?shù)睦щy，此時(shí)往往就需要啟發(fā)函數(shù)來(lái)幫忙。啟發(fā)函數(shù)會(huì)在極其短的時(shí)間內(nèi)找到一個(gè)較優(yōu)解，接著，我們可以根據(jù)這個(gè)解進(jìn)行限界甚至收縮，得到滿意的結(jié)果。
[搜索算法的特例優(yōu)化方法]
[擴(kuò)展結(jié)點(diǎn)上的優(yōu)化]
眾所周知，對(duì)于某些動(dòng)態(tài)規(guī)劃題，對(duì)狀態(tài)轉(zhuǎn)移的設(shè)計(jì)要求是非常高的。往往用o(log2n)的時(shí)間復(fù)雜度實(shí)現(xiàn)狀態(tài)的轉(zhuǎn)移，與用o(n)的時(shí)間復(fù)雜度實(shí)現(xiàn)狀態(tài)轉(zhuǎn)移效率有天壤之別。
這種優(yōu)化技巧很明顯可以用在記憶化的dfs上，而且往往收到很好的效果，因?yàn)橛洃浕痙fs與循環(huán)實(shí)現(xiàn)的動(dòng)態(tài)規(guī)劃只有常數(shù)上的差別，而對(duì)于某些狀態(tài)不完全的動(dòng)態(tài)規(guī)劃，記憶化搜索的效率甚至好過(guò)循環(huán)。
其實(shí)在搜索算法中，狀態(tài)轉(zhuǎn)移上的優(yōu)化（也就是擴(kuò)展結(jié)點(diǎn)上的優(yōu)化），在優(yōu)化中仍然能起很大的作用，只是大家總是忙于探索如何減少搜索算法的浪費(fèi)，忽略了這一點(diǎn)。
*例題 最大機(jī)
分析對(duì)于兩個(gè)排序機(jī)a[i]和a[j]，如果a[i].endvex在a[j].startvex和a[j].endvex之間，我們就把它們連一條邊，很明顯，我們所要求的排序機(jī)數(shù)量，就是a[p].startvex=1, a[q].startvex=n的最短路徑。因?yàn)檫@個(gè)最短路徑非常特殊，所有的邊權(quán)都是1，所以我們采取用寬度優(yōu)先搜索的辦法來(lái)實(shí)現(xiàn)。
粗略地看一下，bfs的時(shí)間復(fù)雜度是o(m)，是完全可以承受的，但是不能忽略的是，如果我們用Dijkstra式的擴(kuò)展方式，那么，擴(kuò)展結(jié)點(diǎn)的復(fù)雜度是o(m),對(duì)于每一個(gè)結(jié)點(diǎn)都擴(kuò)展一次，就是m^2。而m最大到500000，m^2的算法是必然行不通的。
但是不是這樣就可以否定bfs算法呢？答案是否定的。
緊扣著產(chǎn)生結(jié)點(diǎn)的規(guī)律，又因?yàn)閚<=50000，于是我們開一個(gè)hash表，hash[i]表示可以以第i個(gè)排序位置為起點(diǎn)的排序機(jī)，一開始不是把m個(gè)排序機(jī)的信息單純放在數(shù)組中，而是放在這個(gè)hash表中，以待查，每次擴(kuò)展結(jié)點(diǎn)的時(shí)候進(jìn)行掃描的時(shí)候，不必要把m個(gè)都掃描一次，只要對(duì)映射在a[p].startvex到a[p].endvex的結(jié)點(diǎn)掃描一次就可以了，而且，因?yàn)檫厵?quán)為1，所以掃描過(guò)的結(jié)點(diǎn)就可以不掃描了，于是可以直接把散列表中的結(jié)點(diǎn)刪除，以增加下一次掃描的速度。
散列表解決沖突可以使用一個(gè)單鏈表（方便插入與刪除）。而因?yàn)橹挥衖>j的時(shí)候，a[j]才可以和a[i]相連，所以hash單元里也可以是一棵以結(jié)點(diǎn)號(hào)為關(guān)鍵字的二叉排序樹，以提高檢索速度。對(duì)于擴(kuò)展結(jié)點(diǎn)時(shí)的掃描，也可以再開一個(gè)hash表來(lái)映射結(jié)點(diǎn)，這樣兩個(gè)不同的hash表進(jìn)行映射，大大增加了效率，算法時(shí)間復(fù)雜度接近o(m*f(x))，f(x)為hash查找的平均時(shí)間。
我們?cè)倏纯磩?dòng)態(tài)規(guī)劃算法。一般的動(dòng)態(tài)規(guī)劃也是m^2，如果用二叉排序樹或二叉平衡樹（盡管那很煩瑣）來(lái)實(shí)現(xiàn)，可以優(yōu)化到mlog2m，但是log2m比f(wàn)(x)要大的多：500000個(gè)元素映射到50000個(gè)hash單元中，平均每個(gè)單元只有10個(gè)元素，加上二叉排序樹的復(fù)雜度是log2(k)，這個(gè)數(shù)值大約是3.3，而log2m的數(shù)值大約是18.9。兩者效率相差約5.7倍。
小結(jié)搜索的時(shí)間的確主要耗費(fèi)在檢查狀態(tài)樹上，但是當(dāng)結(jié)點(diǎn)非常多的時(shí)候，我們?nèi)匀挥斜匾煤每紤]應(yīng)該如何優(yōu)化結(jié)點(diǎn)的擴(kuò)展。畢竟每轉(zhuǎn)移一次狀態(tài)耗費(fèi)n的時(shí)間，在n很大的時(shí)候是得不償失的。
狀態(tài)擴(kuò)展的本質(zhì)是查找。當(dāng)狀態(tài)轉(zhuǎn)移數(shù)非常數(shù)時(shí)，可以考慮排序+二分查找，也可以構(gòu)建索引、散列或者是二叉排序樹，也可以將這幾個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行有機(jī)結(jié)合，例如索引元素是散列，散列解決沖突用排序樹。每每遇到這個(gè)種類的問(wèn)題，我們需要充分利用數(shù)據(jù)結(jié)構(gòu)上的技巧，把狀態(tài)轉(zhuǎn)移時(shí)間降到最低。
[圖論模型的轉(zhuǎn)化]
在眾多搜索問(wèn)題中，有相當(dāng)一部分需要通過(guò)對(duì)問(wèn)題進(jìn)行構(gòu)圖，并且轉(zhuǎn)化成圖論問(wèn)題，如最短路徑、最小生成樹、最大流等。而伴隨著圖的不同轉(zhuǎn)化方式，所適用的辦法不一定相同，就拿排序機(jī)為例，如果按照上例的構(gòu)圖方法，就是最短路徑問(wèn)題，如果換一種表示方法，我們還可以把它轉(zhuǎn)化成最小生成樹問(wèn)題。
為什么要討論這個(gè)問(wèn)題呢？因?yàn)椴煌瑘D論模型的轉(zhuǎn)換，可能導(dǎo)致使用算法的不同，也可能導(dǎo)致算法復(fù)雜度不同。上例中，最小生成樹法和最短路徑法，本質(zhì)上基本是相同的，所以經(jīng)過(guò)優(yōu)化，時(shí)間復(fù)雜度也基本相同。下面，我們討論一個(gè)例題，就可以體會(huì)到圖論模型轉(zhuǎn)換的重要性。
*例題 多米諾骨牌
分析方法1：順著題目的思路，非常明顯，對(duì)于n個(gè)骨牌，如果兩個(gè)骨牌可以連接，則把它們之間連一條邊，很明顯，這個(gè)問(wèn)題轉(zhuǎn)化成了建立以后圖的哈密頓回路。眾所周知，哈密頓回路是經(jīng)典的NP問(wèn)題。實(shí)現(xiàn)這個(gè)算法，有比較多的辦法。穩(wěn)定而且保守的辦法是對(duì)這張圖進(jìn)行dfs以及回溯。每次探索結(jié)點(diǎn)。當(dāng)然，這個(gè)算法的復(fù)雜度數(shù)量級(jí)為o(n!)，這個(gè)數(shù)值是非常大的，盡管實(shí)際上遠(yuǎn)達(dá)不到這個(gè)數(shù)值，但是當(dāng)n>=20的時(shí)候，在時(shí)限內(nèi)出解也是非常困難的。
方法2：利用這個(gè)題目的特殊性，我們可以把0-6這7種牌面作為結(jié)點(diǎn)，而多米諾骨牌作為這些結(jié)點(diǎn)之間連結(jié)的邊，從而重新構(gòu)圖，最后所求的問(wèn)題，轉(zhuǎn)換為了歐拉路問(wèn)題。對(duì)于歐拉路問(wèn)題，有一個(gè)經(jīng)典算法：
使用一般圖的深度優(yōu)先搜索方法，注意訪問(wèn)過(guò)的邊不要訪問(wèn)第二次，接著在回溯的時(shí)候，記錄回溯的邊。最后把這些邊整理一下，就得到了這個(gè)圖的歐拉回路。
而如果一個(gè)圖不連通或不滿足存在0或2個(gè)奇度點(diǎn)，則這個(gè)圖不存在歐拉回路。這個(gè)程序的時(shí)間復(fù)雜度是o(n2)。對(duì)于n=100來(lái)說(shuō)，是非常小的一個(gè)數(shù)字，相比n!的復(fù)雜度，已經(jīng)有了本質(zhì)的飛躍。經(jīng)過(guò)進(jìn)一步的優(yōu)化，可以將程序復(fù)雜度優(yōu)化為o(e)，也就是o(n)。
小結(jié)事實(shí)上，圖論模型的轉(zhuǎn)換，就是問(wèn)題類型上的轉(zhuǎn)換，也就是思考問(wèn)題角度的轉(zhuǎn)換。進(jìn)行轉(zhuǎn)化的目的，也就是簡(jiǎn)化問(wèn)題或者使得問(wèn)題能夠更好地解決。
從而，我們看到，解決一個(gè)搜索問(wèn)題，不但需要微觀上各種數(shù)據(jù)結(jié)構(gòu)、算法性、程序設(shè)計(jì)的技巧，也需要宏觀上去解決問(wèn)題分析的問(wèn)題。因?yàn)閿?shù)據(jù)結(jié)構(gòu)、算法上的優(yōu)化，是不能帶來(lái)本質(zhì)上優(yōu)化的，但是圖論模型的轉(zhuǎn)換做得到，一個(gè)巧妙的圖論模型往往會(huì)帶來(lái)意想不到的效果。
[化整為零式的拆點(diǎn)方法]
看一個(gè)很簡(jiǎn)單的例子：迷宮問(wèn)題。有n*m的方格，可以向相鄰方向移動(dòng)，求從(1,1)點(diǎn)到(n,m)點(diǎn)的最短路徑。
這是一個(gè)最短路徑問(wèn)題，熟悉bfs的同學(xué)一定會(huì)用o(n*m)的算法來(lái)實(shí)現(xiàn)，當(dāng)然，這個(gè)題也可以用Dijkstra算法來(lái)實(shí)現(xiàn)。分析一下復(fù)雜度：有n^2個(gè)點(diǎn)，有4*n^2條邊，Dijkstra算法的標(biāo)準(zhǔn)復(fù)雜度是o(16*n^4)，優(yōu)化后可以為o(n2log2(n))。
同樣的，如果我們這個(gè)迷宮改變一下，有的通過(guò)代價(jià)是2，有的通過(guò)代價(jià)是1，那么，似乎第1種簡(jiǎn)單bfs的辦法就行不通了。第二種Dijkstra仍然行的通，但是時(shí)間效率并不理想。
于是，從把復(fù)雜問(wèn)題簡(jiǎn)單化的角度考慮，我們可以嘗試著把復(fù)雜結(jié)點(diǎn)拆成簡(jiǎn)單結(jié)點(diǎn)來(lái)處理。
*例題 救援行動(dòng)
分析拿到題目，乍一看，似乎可以用最簡(jiǎn)單的bfs解決，其實(shí)不然。最基本簡(jiǎn)單的bfs算法在處理點(diǎn)的時(shí)候，因?yàn)樯疃榷炔煌韵葦U(kuò)展到的不一定最優(yōu)，從而違背了最優(yōu)子結(jié)構(gòu)，每個(gè)點(diǎn)不能只被擴(kuò)展一次，從而造成了空間浪費(fèi)。那么，我們嘗試把復(fù)雜問(wèn)題向簡(jiǎn)單問(wèn)題靠攏。
對(duì)于一個(gè)“看守”（也就是移動(dòng)到該單元格需要2單位時(shí)間），我們?yōu)槭裁床荒馨阉闯蓛蓚€(gè)一般結(jié)點(diǎn)組成的必經(jīng)路徑呢？想到這里，問(wèn)題的思路就已經(jīng)非常明晰了。進(jìn)行“拆點(diǎn)”的過(guò)程如下圖：
分析起來(lái)比較簡(jiǎn)單，實(shí)現(xiàn)起來(lái)，如果還是用最短路徑的方法，掃描次數(shù)為4*n*m，這已經(jīng)比Dijkstra算法進(jìn)了一大步（從o(plog2p)的算法到o(p)的算法），為此，有一個(gè)細(xì)節(jié)上的處理技巧：在bfs擴(kuò)展結(jié)點(diǎn)的時(shí)候，當(dāng)擴(kuò)展到一個(gè)為“X”的結(jié)點(diǎn)以后，占用一個(gè)單位空間，把同樣的結(jié)點(diǎn)再擴(kuò)展一遍，并且將原來(lái)的結(jié)點(diǎn)置為“無(wú)效（防止以后繼續(xù)擴(kuò)展）”。從而，這個(gè)算法掃描結(jié)點(diǎn)的次書為2*n*m，比直接進(jìn)行圖論轉(zhuǎn)換效率高一倍。
小結(jié)應(yīng)用同類方法可以解決的，還有SGOI的街道問(wèn)題等經(jīng)典問(wèn)題。這一類問(wèn)題，往往拿到以后難于處理，沒(méi)有頭續(xù)，想出的一般算法又不一定能應(yīng)對(duì)問(wèn)題的數(shù)量級(jí)，且問(wèn)題分析后，發(fā)現(xiàn)問(wèn)題牽涉的狀態(tài)都是建立在較小整數(shù)的基礎(chǔ)上。
解決這一類問(wèn)題，“拆點(diǎn)”其實(shí)是一種高級(jí)的算法技巧，需要比較高的問(wèn)題分析能。上例拆開的，僅僅是最簡(jiǎn)單意義上的拆結(jié)點(diǎn)，而且只對(duì)固定的結(jié)點(diǎn)拆成了兩個(gè)，但是，它體現(xiàn)了拆點(diǎn)法的最本質(zhì)思想。拆結(jié)點(diǎn)將非常規(guī)問(wèn)題常規(guī)化。我們可以作一個(gè)比較，對(duì)于上例，n<=200，所以Dijkstra算法也是能通過(guò)的，當(dāng)然，為了掃描節(jié)約時(shí)間，還必須把圖建成鄰接表的形式，且需要用菲波那契堆來(lái)實(shí)現(xiàn)算法，編程復(fù)雜度是可想而知的。而拆點(diǎn)的bfs方法，雖然思維難度稍微大一些，但是不但提高了效率，還簡(jiǎn)化了編程復(fù)雜度，甚至可以直接在bfs的基本模塊上修改。
拆點(diǎn)算法擴(kuò)大了算法的常數(shù)項(xiàng)，但是換來(lái)的，往往比想出一種復(fù)雜高效算法更快、更巧、更省力。
[不斷變化圖論模型的搜索]
某些搜索問(wèn)題乍看之下不好解決，于是就把它們進(jìn)行適當(dāng)?shù)霓D(zhuǎn)換，通常，我們會(huì)把一個(gè)實(shí)際問(wèn)題抽象出一個(gè)圖論模型來(lái)，接著在圖論模型的基礎(chǔ)上進(jìn)行搜索。
現(xiàn)實(shí)中的問(wèn)題，并不是所有的問(wèn)題用一個(gè)單一的、固定不變的圖論模型就能輕易解決的，某些時(shí)候，構(gòu)造好的圖論模型也在不斷變化。
解決這一類問(wèn)題，我們必須很好地把握問(wèn)題的本質(zhì)，善于發(fā)覺(jué)變化中的不變，發(fā)現(xiàn)變化中的規(guī)律。把一些看起來(lái)可以無(wú)限重復(fù)、循環(huán)的問(wèn)題，通過(guò)數(shù)學(xué)手段的證明，轉(zhuǎn)換成有限次數(shù)的搜索，最后制定出完美的搜索算法。
*例題 火山
分析最基本的想法：根據(jù)時(shí)間，進(jìn)行dfs搜索，搜索所有路徑，最后找出最短的路徑，并且把它輸出。
很顯然，為了避免走到火山口上，這個(gè)題每一個(gè)方格可以經(jīng)過(guò)一次，兩次甚至更多。于是dfs搜索即使限定了搜索界限，效率仍然非常低下，但是n,m<=15的情況下，解決問(wèn)題還是沒(méi)有問(wèn)題的。那么，有沒(méi)有更迅速的算法呢？
答案是肯定的。首先，我們要明確的是，所有火山噴發(fā)的周期是lcm(1,2,3,4,5,6)。這個(gè)數(shù)值是60，也就是說(shuō)，無(wú)論如何，解的步數(shù)也不會(huì)超過(guò)60*2=120，這對(duì)于dfs是很有用的界限。
接著，我們可以構(gòu)造一個(gè)[1..Maxn, 1..Maxn, 1..Maxt]的數(shù)組來(lái)表示迷宮，對(duì)于狀態(tài)[x, y, t]={true, false}分別表示在t時(shí)間(x, y)點(diǎn)能否經(jīng)過(guò)（當(dāng)格是否有火山噴發(fā)），這樣，我們把原先棘手難于處理的圖論模型轉(zhuǎn)換成了比較簡(jiǎn)單的圖論模型。
繼續(xù)分析，我們可以證明，如果在[x, y, Time0]到達(dá)過(guò)(x, y)點(diǎn)，那么有另外一條路徑，在Time0時(shí)同樣到達(dá)了(x, y)點(diǎn)，那么這就是沒(méi)有意義的。換句話說(shuō)，這個(gè)圖論模型無(wú)論如何變化，仍然具有最短路徑的最優(yōu)子結(jié)構(gòu)。
這個(gè)圖論模型具有如下特點(diǎn)：
邊權(quán)為1
最優(yōu)子結(jié)構(gòu)
深度有限
有了這3個(gè)特點(diǎn)，我們很容易想到最簡(jiǎn)單的bfs，而且，根據(jù)(2)我們可以知道，當(dāng)訪問(wèn)過(guò)(x, y, Time)這個(gè)結(jié)點(diǎn)以后，這個(gè)結(jié)點(diǎn)就不能再被訪問(wèn)了，于是Array[x, y, Time]就可以標(biāo)為False。
這個(gè)算法的復(fù)雜度是o(N*M*T)。對(duì)于這個(gè)題目而言，極限數(shù)據(jù)只需要運(yùn)算27000次，是非?？焖俚乃惴?。
小結(jié)筆者第一次接觸這種類型的題，是在GDOI-Z4邀請(qǐng)賽AMI。那個(gè)題的規(guī)模更小，最短路徑也可以通過(guò)。這個(gè)優(yōu)化技巧，適用于很多地方，它把無(wú)限化為了有限，把運(yùn)動(dòng)化成了靜止，不但給分析問(wèn)題、解題帶來(lái)了很大的方便，而且迅速地提高了程序效率。