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

[DFS]
[搜索剪枝]
在很多情況下，我們已經(jīng)找到了一組比較好的解。但是計算機仍然會義無返顧地去搜索比它更“劣”的其他解，搜索到后也只能回溯。為了避免出現(xiàn)這種情況，我們需要靈活地去定制回溯搜索的邊界。
*例題 計算機網(wǎng)絡(luò)連接
要將n(n<=30)臺計算機連成網(wǎng)絡(luò)，連接方法：去除首尾兩臺計算機與一臺計算機相連以外，其他計算機只與兩臺計算機相連。連接的長度則為計算機連接的電纜的長度。
求：一種連接方式，使需要電纜的長度最短。
分析這個題目用回溯搜索來解決。但是，由于回溯搜索的搜索量比較大，達到了n!，是不可能搜索完n=30的情況的，所以，我們考慮對它進行優(yōu)化：
假如目前搜索到了一組解，電纜總長度為kx，那么，如果說以后搜索到的連接方法（不一定是最終連接方法）的連接長度>=kx，那么這個方案的總長度一定不小于kx，那么，就不必要搜索下去了，直接換下一個結(jié)點繼續(xù)搜索。
路徑A1-A2-…An與路徑An-An-1-…A1這兩條路徑是一個“正反”的關(guān)系，本質(zhì)上是相同的，于是我們可以規(guī)定起點始的下標總是小于終點的下標
假如路徑的A-B-C-D的長度<A-C-B-D的長度，那么包含A-C-B-D路徑的路徑的長度一定不是最短。
有了上述的優(yōu)化，題目就可以得到很快的解決了。
在深度優(yōu)先搜索的過程當中，往往有很多走不通的“死路”。假如我們把這些“死路”排除在外，不是可以節(jié)省很多的時間嗎？
打一個比方，前面有一個路徑，別人已經(jīng)提示：“這是死路，肯定不通”，而你的程序仍然很“執(zhí)著”地要繼續(xù)朝這個方向走，走到頭來才發(fā)現(xiàn)，別人的提示是正確的。這樣，浪費了很多的時間。針對這種情況，我們可以把“死路”給標記一下不走，就可以得到更高的搜索效率。
*例題 皇后問題
分析 取n=4為例
采用一般的回溯，就是每一行的每個格子放與不放都搜索一下：
然后回溯一次，換下一個點繼續(xù)搜索。
這個算法的效率，是
實際上，在放置了(1,1)這個皇后，再把皇后放置在(2,1)就是毫無意義的：前面一個皇后一定能攻擊到它。
為了避免這種情況，我們這樣做：
走了一個棋子以后，把它的“勢力范圍”給圈出來，并且告訴以后的皇后：這里不能放置。舉簡單的例子：放置皇后(1,1)，由于打“.”的格子在放了(1,1)這顆子之后，被標注為了“不能走”，所以這些點我們就不去理會了。這樣就節(jié)省了很多時間，大大提高了搜索的效率。
而對于很多回溯的題目，我們都可以采用分枝定界法，把搜索樹中不必要的枝剪去，大大提高了搜索的效率。




[記憶化]
對于一些有最優(yōu)子結(jié)構(gòu)的問題，我們往往采用動態(tài)規(guī)劃算法來實現(xiàn)。采用動態(tài)規(guī)劃算法，需要弄清狀態(tài)以及狀態(tài)是如何轉(zhuǎn)移的，接著列出狀態(tài)轉(zhuǎn)移方程。首先舉一個非常簡單的例子
　　　　*例題 數(shù)字三角形
　　　　分析無論對與新手還是老手，這都是再熟悉不過的題了，很容易地，我們寫出狀態(tài)轉(zhuǎn)移方程：
　　　　　　f(i, j)=a[i, j] + min{f(i + 1, j) + f(i, j + 1)}
對于動態(tài)規(guī)劃算法解決這個問題，我們根據(jù)狀態(tài)轉(zhuǎn)移方程和狀態(tài)轉(zhuǎn)移方向，比較容易地寫出動態(tài)規(guī)劃的循環(huán)表示方法。但是，當狀態(tài)和轉(zhuǎn)移非常復(fù)雜的時候，也許寫出循環(huán)式的動態(tài)規(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;
顯而易見，這個算法就是最簡單的搜索算法。時間復(fù)雜度為2n，明顯是會超時的。分析一下搜索的過程，實際上，很多調(diào)用都是不必要的，也就是把產(chǎn)生過的最優(yōu)狀態(tài)，又產(chǎn)生了一次。為了避免浪費，很顯然，我們存放一個opt數(shù)組：
Opt[i, j] - 每產(chǎn)生一個f(i, j)，將f(i, j)的值放入opt中，以后再次調(diào)用到f(i, j)的時候，直接從opt[i, j]來取就可以了。
　　　　　　于是動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程被直觀地表示出來了，這樣節(jié)省了思維的難度，減少了編程的技巧，而運行時間只是相差常數(shù)的復(fù)雜度，而且在相當多的情況下，遞歸算法能更好地避免浪費，在比賽中是非常實用的。
　　　　總結(jié)記憶化搜索是對動態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移方程的直觀表示。本質(zhì)上來說，它仍然是用搜索算法的核心，只不過使用“記錄求過的狀態(tài)”的辦法，來避免重復(fù)搜索，這樣，記憶化搜索的每一步，也可以對應(yīng)到動態(tài)規(guī)劃算法中去。記憶化搜索有優(yōu)化方便、調(diào)試容易、思維直觀的優(yōu)點，但是效率上比循環(huán)的動態(tài)規(guī)劃差一個常數(shù)，但是時間和空間復(fù)雜度是同一數(shù)量級的（盡管空間上也差一個常數(shù)，那就是堆棧空間）。當n比較小的時候，我們可以忽略這個常數(shù)，從而記憶化搜索可以和動態(tài)規(guī)劃達到完全相同的效果。




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




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