搜索算法檢視原始碼討論檢視歷史
| 搜索算法 |
搜索算法是利用計算機的高性能來有目的的窮舉一個問題解空間的部分或所有的可能情況，從而求出問題的解的一種方法。現階段一般有枚舉算法、深度優先搜索、廣度優先搜索、A*算法、回溯算法、蒙特卡洛樹搜索、散列函數等算法。在大規模實驗環境中，通常通過在搜索前，根據條件降低搜索規模；根據問題的約束條件進行剪枝；利用搜索過程中的中間解，避免重複計算這幾種方法進行優化。
簡介
搜索算法實際上是根據初始條件和擴展規則構造一棵「解答樹」並尋找符合目標狀態的節點的過程。所有的搜索算法從最終的算法實現上來看，都可以劃分成兩個部分——控制結構（擴展節點的方式）和產生系統（擴展節點），而所有的算法優化和改進主要都是通過修改其控制結構來完成的。其實，在這樣的思考過程中，我們已經不知不覺地將一個具體的問題抽象成了一個圖論的模型——樹，即搜索算法的使用第一步在於搜索樹的建立。由圖一可以知道，這樣形成的一棵樹叫搜索樹。初始狀態對應着根節點，目標狀態對應着目標結點。排在前的結點叫父結點，其後的結點叫子結點，同一層中的結點是兄弟結點，由父結點產生子結點叫擴展。完成搜索的過程就是找到一條從根結點到目標結點的路徑，找出一個最優的解。這種搜索算法的實現類似於圖或樹的遍歷，通常可以有兩種不同的實現方法，即深度優先搜索（DFS——Depth First search）和廣度優先搜索（BFS——Breadth First Search）。
評價
如算法名稱那樣，深度優先搜索所遵循的搜索策略是儘可能「深」地搜索樹。它的基本思想是：為了求得問題的解，先選擇某一種可能情況向前（子結點）探索，在探索過程中，一旦發現原來的選擇不符合要求，就回溯至父親結點重新選擇另一結點，繼續向前探索，如此反覆進行，直至求得最優解。深度優先搜索的實現方式可以採用遞歸或者棧來實現。由此可見，把通常問題轉化為樹的問題是至關重要的一步，完成了樹的轉換基本完成了問題求解在深度優先搜索的過程當中，往往有很多走不通的「死路」。假如我們把這些「死路」排除在外，不是可以節省很多的時間嗎？打一個比方，前面有一個路徑，別人已經提示：「這是死路，肯定不通」，而你的程序仍然很「執着」地要繼續朝這個方向走，走到頭來才發現，別人的提示是正確的。這樣，浪費了很多的時間。針對這種情況，我們可以把「死路」給標記一下不走，就可以得到更高的搜索效率類似樹的按層遍歷，其過程為：首先訪問初始點Vi，並將其標記為已訪問過，接着訪問Vi的所有未被訪問過可到達的鄰接點Vi1、Vi2……Vit，並均標記為已訪問過，然後再按照Vi1、Vi2……Vit的次序，訪問每一個頂點的所有未被訪問過的鄰接點，並均標記為已訪問過，依此類推，直到圖中所有和初始點Vi有路徑相通的頂點都被訪問過為止。[1]