搜索算法（Search Algorithm）是指谷歌的搜索算法是為了給每一次搜索請(qǐng)求找到最為相關(guān)的網(wǎng)站和頁(yè)面而設(shè)定的一種搜索計(jì)算。
正文
搜索算法
搜索算法是利用計(jì)算機(jī)的高性能來(lái)有目的的窮舉一個(gè)問(wèn)題解空間的部分或所有的可能情況，從而求出問(wèn)題的解的一種方法。
一搜索過(guò)程
搜索算法實(shí)際上是根據(jù)初始條件和擴(kuò)展規(guī)則構(gòu)造一棵“解答樹”并尋找符合目標(biāo)狀態(tài)的節(jié)點(diǎn)的過(guò)程。所有的搜索算法從最終的算法實(shí)現(xiàn)上來(lái)看，都可以劃分成兩個(gè)部分——控制結(jié)構(gòu)（擴(kuò)展節(jié)點(diǎn)的方式）和產(chǎn)生系統(tǒng)（擴(kuò)展節(jié)點(diǎn)），而所有的算法優(yōu)化和改進(jìn)主要都是通過(guò)修改其控制結(jié)構(gòu)來(lái)完成的。其實(shí)，在這樣的思考過(guò)程中，我們已經(jīng)不知不覺地將一個(gè)具體的問(wèn)題抽象成了一個(gè)圖論的模型——樹，即搜索算法的使用第一步在于搜索樹的建立。
由圖一可以知道，這樣形成的一棵樹叫搜索樹。初始狀態(tài)對(duì)應(yīng)著根結(jié)點(diǎn)，目標(biāo)狀態(tài)對(duì)應(yīng)著目標(biāo)結(jié)點(diǎn)。排在前的結(jié)點(diǎn)叫父結(jié)點(diǎn)，其后的結(jié)點(diǎn)叫子結(jié)點(diǎn)，同一層中的結(jié)點(diǎn)是兄弟結(jié)點(diǎn)，由父結(jié)點(diǎn)產(chǎn)生子結(jié)點(diǎn)叫擴(kuò)展。完成搜索的過(guò)程就是找到一條從根結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的路徑，找出一個(gè)最優(yōu)的解。這種搜索算法的實(shí)現(xiàn)類似于圖或樹的遍歷，通常可以有兩種不同的實(shí)現(xiàn)方法，即深度優(yōu)先搜索（DFS——Depth First search）和廣度優(yōu)先搜索（BFS——Breadth First Search）。
二深度優(yōu)先搜索
一、算法思想
如算法名稱那樣，深度優(yōu)先搜索所遵循的搜索策略是盡可能“深”地搜索樹。它的基本思想是：為了求得問(wèn)題的解，先選擇某一種可能情況向前（子結(jié)點(diǎn)）探索，在探索過(guò)程中，一旦發(fā)現(xiàn)原來(lái)的選擇不符合要求，就回溯至父親結(jié)點(diǎn)重新選擇另一結(jié)點(diǎn)，繼續(xù)向前探索，如此反復(fù)進(jìn)行，直至求得最優(yōu)解。深度優(yōu)先搜索的實(shí)現(xiàn)方式可以采用遞歸或者棧來(lái)實(shí)現(xiàn)。
由此可見，把通常問(wèn)題轉(zhuǎn)化為樹的問(wèn)題是至關(guān)重要的一步，完成了樹的轉(zhuǎn)換基本完成了問(wèn)題求解。
二、深度優(yōu)先搜索的優(yōu)化
1、優(yōu)化思想
減少所遍歷的狀態(tài)總數(shù)
2、三種方法
(1)減少節(jié)點(diǎn)數(shù)
思想：盡可能減少生成的節(jié)點(diǎn)數(shù)
(2)定制回溯邊界
思想：定制回溯邊界條件，剪掉不可能得到最優(yōu)解的子樹
在很多情況下，我們已經(jīng)找到了一組比較好的解。但是計(jì)算機(jī)仍然會(huì)義無(wú)返顧地去搜索比它更“劣”的其他解，搜索到后也只能回溯。為了避免出現(xiàn)這種情況，我們需要靈活地去定制回溯搜索的邊界。
在深度優(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)記一下不走，就可以得到更高的搜索效率。
(3)記憶化
思想：運(yùn)用記憶化的方法，使得一些遍歷過(guò)的子樹不要重復(fù)遍歷
3、三個(gè)原則
(1)正確性：剪去的“枝條”不包含最優(yōu)答案；
(2)準(zhǔn)確性：在保證第一條原則的情況下，盡可能的剪去更多不包含最優(yōu)答案的枝條；
(3)高效性：通過(guò)剪枝要能夠更快的接近到達(dá)最優(yōu)解。
三廣度優(yōu)先搜索
一、廣度優(yōu)先搜索遍歷
類似樹的按層遍歷，其過(guò)程為：首先訪問(wèn)初始點(diǎn)Vi，并將其標(biāo)記為已訪問(wèn)過(guò)，接著訪問(wèn)Vi的所有未被訪問(wèn)過(guò)可到達(dá)的鄰接點(diǎn)Vi1、Vi2……Vit，并均標(biāo)記為已訪問(wèn)過(guò)，然后再按照Vi1、Vi2……Vit的次序，訪問(wèn)每一個(gè)頂點(diǎn)的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)，并均標(biāo)記為已訪問(wèn)過(guò)，依此類推，直到圖中所有和初始點(diǎn)Vi有路徑相通的頂點(diǎn)都被訪問(wèn)過(guò)為止。
二、處理和優(yōu)化
對(duì)于狀態(tài)數(shù)很多時(shí)，廣度優(yōu)先搜索可以采用循環(huán)隊(duì)列或動(dòng)態(tài)鏈表來(lái)處理。
舉例分析一下：
(1)題目：黑白棋游戲
黑白棋游戲的棋盤由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)的最短著棋序列。
(2)分析
這題我們可以想到用深度優(yōu)先搜索來(lái)做，但是如果下一步出現(xiàn)了以前的狀態(tài)怎么辦？直接判斷時(shí)間復(fù)雜度的可能會(huì)有點(diǎn)大，這題的最優(yōu)解法是用廣度優(yōu)先搜索來(lái)做。我們就可以有初始狀態(tài)按照廣度優(yōu)先搜索遍歷來(lái)擴(kuò)展每一個(gè)點(diǎn)，這樣到達(dá)目標(biāo)狀態(tài)的步數(shù)一定是最優(yōu)的（步數(shù)的增加時(shí)單調(diào)的）。但問(wèn)題是如果出現(xiàn)了重復(fù)的情況我們就必須要判重，但是樸素的判重是可以達(dá)到狀態(tài)數(shù)級(jí)別的，其實(shí)我們可以考慮用hash表來(lái)判重。
Hash表：思路是根據(jù)關(guān)鍵碼值進(jìn)行直接訪問(wèn)。也就是說(shuō)把一個(gè)關(guān)鍵碼值映射到表中的一個(gè)位置來(lái)訪問(wèn)記錄的過(guò)程。在Hash表中，一般插入，查找的時(shí)間復(fù)雜度可以在O（1）的時(shí)間復(fù)雜度內(nèi)搞定。對(duì)于這一題我們可以用二進(jìn)制值表示其hash值，最多2^16次方，所以我們開個(gè)2^16次方的表記錄這個(gè)狀態(tài)出現(xiàn)沒(méi)有，這樣可以在O（1）的時(shí)間復(fù)雜度內(nèi)解決判重問(wèn)題。
進(jìn)一步考慮：從初始狀態(tài)到目標(biāo)狀態(tài)，必定會(huì)產(chǎn)生很多無(wú)用的狀態(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ù)和也就是答案。
上面的想法是雙向廣度優(yōu)先搜索：
就像圖二一樣，多擴(kuò)展了很多不必要的狀態(tài)。
從上面一題可以看到我們用到了兩種優(yōu)化方法，即Hash表優(yōu)化和雙向廣搜優(yōu)化。一般的廣度優(yōu)先搜索用這兩個(gè)優(yōu)化就足以解決。
四深度優(yōu)先搜索和廣度優(yōu)先搜索的比較
參考資料 >