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