不知情搜尋演算法


不知情的搜尋是一類通用搜尋演算法,它以強力方式執行。除了如何遍歷樹之外,不知情的搜尋演算法沒有關於狀態或搜尋空間的附加資訊,因此它也稱為盲搜尋。

以下是各種型別的無知搜尋演算法:

  • 廣度優先搜尋
  • 深度優先搜尋
  • 深度限制搜尋
  • 疊代加深深度優先搜尋
  • 統一成本搜尋
  • 雙向搜尋

1. 廣度優先搜尋

  • 廣度優先搜尋是遍歷樹或圖的最常見搜尋策略。此演算法在樹或圖中搜尋橫向,因此稱為廣度優先搜尋。
  • BFS演算法從樹的根節點開始搜尋,並在移動到下一級節點之前擴充套件當前級別的所有後繼節點。
  • 廣度優先搜尋演算法是通用圖搜尋演算法的範例。
  • 使用FIFO佇列資料結構實現廣度優先搜尋。

優點:

  • 如果存在任何解決方案,BFS將提供解決方案。
  • 如果針對給定問題存在多個解決方案,則BFS將提供需要最少步驟的最小解決方案。

缺點:

  • 它需要大量記憶體,因為必須將樹的每個級別儲存到記憶體中以擴充套件下一級別。
  • 如果解決方案遠離根節點,BFS需要大量時間。

範例:

在下面的樹結構中,已經顯示了使用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是最優的。

2. 深度優先搜尋

  • 深度優先搜尋是用於遍歷樹或圖資料結構的遞迴演算法。
  • 它從根節點開始並在移動到下一個路徑之前跟隨每個路徑到其最大深度節點。
  • DFS使用堆疊資料結構來實現它。
  • DFS演算法的過程類似於BFS演算法。

注意:回溯是一種使用遞迴查詢所有可能解決方案的演算法技術。

優點:

  • DFS需要非常少的記憶體,因為它只需要在從根節點到當前節點的路徑上儲存一堆節點。
  • 到達目標節點所需的時間比BFS演算法少(如果它在正確的路徑中移動)。

缺點:

  • 許多狀態有可能繼續發生,並且無法保證找到解決方案。
  • DFS演算法用於深入搜尋,有時可能會進入無限迴圈。

範例

在下面的搜尋樹中,顯示了深度優先搜尋的流程,它將遵循以下順序:

根節點 ---> 左節點 ----> 右節點

它將從根節點S開始搜尋,然後遍歷A,然後是B,然後是遍歷E的E和E,它將回溯樹,因為E沒有其他後繼,但仍未找到目標節點。在回溯之後,它將遍歷節點C然後G,並且在此處它將在找到目標節點時終止。

深度優先搜索

完整性:DFS搜尋演算法在有限狀態空間內完成,因為它將擴充套件有限搜尋樹中的每個節點。
時間複雜度:DFS的時間複雜度將等同於演算法遍歷的節點。它的公式如下:

其中,m = 任何節點的最大深度,這可能遠大於d(Shallowest解算深度)

空間複雜度:DFS演算法只需要儲存來自根節點的單個路徑,因此DFS的空間複雜度等於邊緣集的大小,即O(bm)。
最佳:DFS搜尋演算法不是最優的,因為它可能產生大量步驟或高成本以到達目標節點。

3. 深度有限搜尋演算法

深度有限搜尋演算法類似於具有預定限制的深度優先搜尋。深度限制搜尋可以解決深度優先搜尋中無限路徑的缺點。在該演算法中,深度限制的節點將被視為沒有後繼節點。

可以使用兩個失敗條件終止深度限制搜尋:

  • 標準故障值:表示問題沒有任何解決方案。
  • 截止故障值:它在給定的深度限制內沒有定義問題的解決方案。

優點:

  • 深度限制搜尋是記憶體高效。

缺點:

  • 深度限制搜尋也具有不完整性的缺點。
  • 如果問題有多個解決方案,則可能不是最佳選擇。

範例

深度有限搜索算法

  • 完整性:如果解決方案高於深度限制,則DLS搜尋演算法完成。
  • 時間複雜度:DLS演算法的時間複雜度為O(b?)。
  • 空間複雜度:DLS演算法的空間複雜度為O(b×l)。
  • 最佳:深度限制搜尋可以看作是DFS的一個特例,即使?> d也不是最優的。

4. 統一成本搜尋演算法

統一成本搜尋是用於遍歷加權樹或圖的搜尋演算法。當每個邊緣有不同的成本時,該演算法開始起作用。統一成本搜尋的主要目標是找到具有最低累積成本的目標節點的路徑。統一成本搜尋根據路徑成本從根節點擴充套件節點。它可用於解決需要最優成本的任何圖/樹。統一成本搜尋演算法由優先順序佇列實現。它最優先考慮最低累積成本。如果所有邊的路徑成本相同,則統一成本搜尋等效於BFS演算法。

優點:

  • 統一成本搜尋是最佳的,因為在每個州都選擇成本最低的路徑。

缺點:

  • 它不關心搜尋涉及的步驟數量,只關心路徑成本。由於該演算法可能陷入無限迴圈。

範例

統一成本搜索算法

完整性:

統一成本搜尋已經完成,例如,如果有解決方案,UCS會找到它。

時間複雜性:

C *是最優解的成本,ε是接近目標節點的每一步。然後步數= C /ε+ 1。這裡取+1,因為從狀態0開始並結束為C /ε。

5. 疊代深化深度搜尋

疊代深化演算法是DFS和BFS演算法的組合。此搜尋演算法找出最佳深度限制,並通過逐漸增加限制直到找到目標為止。
該演算法執行深度優先搜尋直到某個「深度限制」,並且在每次疊代之後它不斷增加深度限制,直到找到目標節點。此搜尋演算法結合了廣度優先搜尋的快速搜尋和深度優先搜尋的記憶體效率的優勢。
當搜尋空間很大並且目標節點的深度未知時,疊代搜尋演算法對於無知搜尋是有用的。

優點:

  • 它結合了BFS和DFS搜尋演算法在快速搜尋和記憶體效率方面的優勢。

缺點:

  • IDDFS的主要缺點是它重複了前一階段的所有工作。

範例

以下樹結構顯示疊代加深深度優先搜尋。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

在第四次疊代中,演算法將找到目標節點。

完整性:

  • 如果分支因子是有限的,則該演算法是完整的。

時間複雜性:

  • 假設b是分支因子,深度是d,那麼最壞情況時間複雜度是O(bd)。

空間複雜性:

  • IDDFS的空間複雜度為O(bd)。

最佳:

  • 如果路徑成本是節點深度的非遞減函式,則IDDFS演算法是最佳的。

6. 雙向搜尋演算法

雙向搜尋演算法執行兩個同時搜尋,一個形成稱為前向搜尋的初始狀態,另一個稱為後向搜尋的目標節點,以找到目標節點。雙向搜尋用兩個子圖替換單個搜尋圖,其中一個子圖從一個初始頂點開始搜尋,另一個從目標頂點開始。當這兩個圖形相互交叉時,搜尋停止。

雙向搜尋可以使用搜尋技術,如BFS,DFS,DLS等。

優點:

  • 雙向搜尋很快。
  • 雙向搜尋需要更少的記憶體

缺點:

  • 雙向搜尋樹的實現很困難。
  • 在雙向搜尋中,應該事先知道目標狀態。

範例

在下面的搜尋樹中,應用雙向搜尋演算法。該演算法將一個圖/樹分成兩個子圖。它開始在前向方向上從節點1穿過並且在向後方向上從目標節點16開始。

該演算法終止於節點9,其中兩個搜尋相遇。

 雙向搜索算法

完整性: 如果我們在兩次搜尋中都使用BFS,則完成雙向搜尋。
時間複雜度: 使用BFS進行雙向搜尋的時間複雜度為O(b^d)。
空間複雜性: 雙向搜尋的空間複雜度為O(b^d)。
最佳: 雙向搜尋是最佳的。