不知情的搜尋是一類通用搜尋演算法,它以強力方式執行。除了如何遍歷樹之外,不知情的搜尋演算法沒有關於狀態或搜尋空間的附加資訊,因此它也稱為盲搜尋。
以下是各種型別的無知搜尋演算法:
優點:
缺點:
範例:
在下面的樹結構中,已經顯示了使用BFS演算法從根節點S到目標節點K遍歷樹。BFS搜尋演算法遍歷層,因此它將遵循虛線箭頭所示的路徑,遍歷路徑將是:
S---> A--->B---->C--->D---->G--->H--->E---->F---->I---->K
時間複雜度 :BFS演算法的時間複雜度可以通過BFS中遍歷的節點數來獲得,直到最淺的節點。其中 d= 最淺解的深度,b是每個狀態的節點。
空間複雜度:BFS演算法的空間複雜度由邊界的儲存器大小O(bd)
給出。
完整性:BFS完成,這意味著如果最淺的目標節點處於某個有限的深度,那麼BFS將找到解決方案。
最優性:如果路徑成本是節點深度的非遞減函式,則BFS是最優的。
注意:回溯是一種使用遞迴查詢所有可能解決方案的演算法技術。
優點:
缺點:
在下面的搜尋樹中,顯示了深度優先搜尋的流程,它將遵循以下順序:
根節點 ---> 左節點 ----> 右節點
它將從根節點S開始搜尋,然後遍歷A,然後是B,然後是遍歷E的E和E,它將回溯樹,因為E沒有其他後繼,但仍未找到目標節點。在回溯之後,它將遍歷節點C然後G,並且在此處它將在找到目標節點時終止。
完整性:DFS搜尋演算法在有限狀態空間內完成,因為它將擴充套件有限搜尋樹中的每個節點。
時間複雜度:DFS的時間複雜度將等同於演算法遍歷的節點。它的公式如下:
其中,m = 任何節點的最大深度,這可能遠大於d(Shallowest解算深度)
空間複雜度:DFS演算法只需要儲存來自根節點的單個路徑,因此DFS的空間複雜度等於邊緣集的大小,即O(bm)。
最佳:DFS搜尋演算法不是最優的,因為它可能產生大量步驟或高成本以到達目標節點。
深度有限搜尋演算法類似於具有預定限制的深度優先搜尋。深度限制搜尋可以解決深度優先搜尋中無限路徑的缺點。在該演算法中,深度限制的節點將被視為沒有後繼節點。
可以使用兩個失敗條件終止深度限制搜尋:
優點:
缺點:
統一成本搜尋是用於遍歷加權樹或圖的搜尋演算法。當每個邊緣有不同的成本時,該演算法開始起作用。統一成本搜尋的主要目標是找到具有最低累積成本的目標節點的路徑。統一成本搜尋根據路徑成本從根節點擴充套件節點。它可用於解決需要最優成本的任何圖/樹。統一成本搜尋演算法由優先順序佇列實現。它最優先考慮最低累積成本。如果所有邊的路徑成本相同,則統一成本搜尋等效於BFS演算法。
優點:
缺點:
完整性:
統一成本搜尋已經完成,例如,如果有解決方案,UCS會找到它。
時間複雜性:
設C *
是最優解的成本,ε是接近目標節點的每一步。然後步數= C /ε+ 1。這裡取+1,因為從狀態0開始並結束為C /ε。
疊代深化演算法是DFS和BFS演算法的組合。此搜尋演算法找出最佳深度限制,並通過逐漸增加限制直到找到目標為止。
該演算法執行深度優先搜尋直到某個「深度限制」,並且在每次疊代之後它不斷增加深度限制,直到找到目標節點。此搜尋演算法結合了廣度優先搜尋的快速搜尋和深度優先搜尋的記憶體效率的優勢。
當搜尋空間很大並且目標節點的深度未知時,疊代搜尋演算法對於無知搜尋是有用的。
優點:
缺點:
以下樹結構顯示疊代加深深度優先搜尋。IDDFS演算法執行各種疊代,直到找不到目標節點。演算法執行的疊代如下:
第1次疊代——-> A
第2次疊代——> A,B,C
第3次疊代———> A,B,D,E,C,F,G
第4次疊代———> A,B,D,H,I,E,C,F,K,G
在第四次疊代中,演算法將找到目標節點。
完整性:
時間複雜性:
空間複雜性:
最佳:
雙向搜尋演算法執行兩個同時搜尋,一個形成稱為前向搜尋的初始狀態,另一個稱為後向搜尋的目標節點,以找到目標節點。雙向搜尋用兩個子圖替換單個搜尋圖,其中一個子圖從一個初始頂點開始搜尋,另一個從目標頂點開始。當這兩個圖形相互交叉時,搜尋停止。
雙向搜尋可以使用搜尋技術,如BFS,DFS,DLS等。
優點:
缺點:
在下面的搜尋樹中,應用雙向搜尋演算法。該演算法將一個圖/樹分成兩個子圖。它開始在前向方向上從節點1穿過並且在向後方向上從目標節點16開始。
該演算法終止於節點9,其中兩個搜尋相遇。
完整性: 如果我們在兩次搜尋中都使用BFS,則完成雙向搜尋。
時間複雜度: 使用BFS進行雙向搜尋的時間複雜度為O(b^d)。
空間複雜性: 雙向搜尋的空間複雜度為O(b^d)。
最佳: 雙向搜尋是最佳的。