什么是搜索

• 搜索問題是指既不能通過數(shù)學建模解決，又沒有其他算法可以套用或者非遍歷所有情況才能得出正確結(jié)果。這時就需要采用搜索算法來解決問題。搜索就是一種通過窮舉所有解的狀態(tài)，來求得題目所要求的解或者最優(yōu)解的方法。
• 搜索的基本概念：
  1. 狀態(tài)：對某一系統(tǒng)在某一時刻的數(shù)學描述。
  2. 動作：從當前時刻狀態(tài)轉(zhuǎn)移到下一時刻所處狀態(tài)的操作。
  3. 狀態(tài)轉(zhuǎn)移：對某一時刻的狀態(tài)進行動作后所達到的狀態(tài)。
  4. 路徑：一個狀態(tài)序列，該序列被一系列動作所連接。
  5. 目標測試：評估當前狀態(tài)是否是所求解的目標狀態(tài)。

樹搜索算法

• 基本思想：通過擴展已探索狀態(tài)的后繼，離線模擬探索狀態(tài)空間
  
• 以下圖舉例
• 根據(jù)給定的初始狀態(tài)初始化搜索樹
• 根據(jù)策略strategy決定擴展哪個葉子結(jié)點，直到達到目標狀態(tài)
  

搜索策略

• 通過選擇節(jié)點擴展的順序來定義搜索策略
• 根據(jù)以下維度評估策略：
  • 完整性(完備性）: 如果存在，它是否總能找到解決方案？
  • 時間復雜性(時間復雜度）: 生成的節(jié)點數(shù)
  • 空間復雜性(空間復雜度） : 內(nèi)存中的最大節(jié)點數(shù)
  • 最優(yōu)性(最優(yōu)性）: 它總是找到成本最低的解決方案嗎？
• 時間和空間復雜性是根據(jù)
  • b： maximum branching factor of the search tree搜索樹的最大分支因子—分支因子
  • d： depth of the least-cost solution—最淺的目標節(jié)點的深度
  • m： maximum depth of the state space狀態(tài)空間的最大深度（可以是$\infty$）—最大深度

無信息搜索

不一致的搜索策略只使用問題定義中可用的信息

• Breadth-first search 廣度優(yōu)先搜索
• Uniform-cost search 代價一致搜索
• Depth-first search 深度優(yōu)先搜索
• Depth-limited search 深度受限搜索
• Iterative deepening search 迭代深度優(yōu)先搜索

Breadth-first search

• 擴展最淺的未擴展節(jié)點

• 實施：邊緣結(jié)點是一個FIFO隊列，即，新來的后繼放在末尾

• 時間復雜度 ：BFS算法的時間復雜度可以通過BFS中遍歷的節(jié)點數(shù)來獲得，直到最淺的節(jié)點。其中 d= 最淺解的深度，b是每個狀態(tài)的節(jié)點。

• 空間復雜度：$O(b^{d+1})$(keeps every node in memory)

• 完整性：BFS完成，這意味著如果最淺的目標節(jié)點處于某個有限的深度，那么BFS將找到解決方案。

• 最優(yōu)性：如果路徑成本是節(jié)點深度的非遞減函數(shù)，則BFS是最優(yōu)的。

• 空間是個大問題；可以輕松地以100MB/秒的速度生成節(jié)點，因此24小時=8640GB。

Uniform-cost search

• 一致代價搜索(Uniform Cost Search)，優(yōu)先擴展擁有最小路徑消耗函數(shù)g(n)的結(jié)點，和最佳優(yōu)先搜索(Best-first Search)在代碼實現(xiàn)上一致，即最佳優(yōu)先搜索的評價函數(shù)f(n)等于g(n)時，最佳優(yōu)先搜索即為一致代價搜索。
• 一致代價搜索是用于遍歷加權(quán)樹或圖的搜索算法。
• 當每個邊緣有不同的成本時，該算法開始起作用。
• 一致代價搜索的主要目標是找到具有最低累積成本的目標節(jié)點的路徑。一致代價搜索根據(jù)路徑成本從根節(jié)點擴展節(jié)點。
• 它可用于解決需要最優(yōu)成本的任何圖/樹。一致代價搜索算法由優(yōu)先級隊列實現(xiàn)。它最優(yōu)先考慮最低累積成本。
• 如果所有邊的路徑成本相同，則一致代價搜索等效于寬度優(yōu)先搜索算法。
• 完整性：是，如果每一步代價$\ge \epsilon$。
• 時間復雜性：$O(bceiling(C?/\epsilon )$，$C?$是最佳解決方案的成本，$g\le$最優(yōu)解代價的節(jié)點數(shù)
• 空間復雜度：$O(bceiling(C?/\epsilon )$，$g\le$最優(yōu)解代價的節(jié)點數(shù)
• 最優(yōu)解：節(jié)點按 g(n) 的遞增順序擴展

Depth-first search

• DFS的核心是沿著樹的深度遍歷樹的結(jié)點，盡可能深的探索樹的分支，當結(jié)點v的所有邊都已經(jīng)被探索后，將回溯到發(fā)現(xiàn)v的那條邊的起始結(jié)點。這一過程一直進行到已發(fā)現(xiàn)初始結(jié)點可以到達的所有結(jié)點為止，如果還有未被發(fā)現(xiàn)的結(jié)點，則從中選擇一個作為初始結(jié)點重復上述過程，直到所有結(jié)點都被訪問為止。
• DFS的基本原則可以歸納為：按照某種條件一直往前探索，如果在過程中失敗，比如死路(全部探索完但是仍沒有解)則返回，另選一條道路繼續(xù)，直到到達目標結(jié)點為止。
• 深度優(yōu)先搜索擴展搜索樹中深度最深的結(jié)點。
• 它既不是完備的也不是最優(yōu)的，但它具有線性的空間復雜度。
• 總是擴展在隊列frontier中l(wèi)evel最深的結(jié)點。深度優(yōu)先搜索的其中一個variant是回溯搜索(Backtracking Search)，可以實現(xiàn)更小內(nèi)存開銷。
• 完整性：DFS搜索算法在有限狀態(tài)空間內(nèi)完成，因為它將擴展有限搜索樹中的每個節(jié)點。
• 時間復雜度：DFS的時間復雜度將等同于算法遍歷的節(jié)點。它的公式如下：
  
  其中，m = 任何節(jié)點的最大深度，這可能遠大于d(Shallowest解算深度)
• 空間復雜度：DFS算法只需要存儲來自根節(jié)點的單個路徑，因此DFS的空間復雜度等于邊緣集的大小，即O(bm)。
• 最優(yōu)解：DFS搜索算法不是最優(yōu)的，因為它可能產(chǎn)生大量步驟或高成本以到達目標節(jié)點。

depth-limited search

• 深度受限搜索(Depth-limited Search)，是在深度優(yōu)先搜索基礎上，設置搜索深度限制。因為當搜索狀態(tài)空間很大的時候，深度優(yōu)先搜索DFS會非常尷尬，所以可以通過設置搜索深度界限來避免。
• 深度有限搜索算法類似于具有預定限制的深度優(yōu)先搜索。深度限制搜索可以解決深度優(yōu)先搜索中無限路徑的缺點。在該算法中，深度限制的節(jié)點將被視為沒有后繼節(jié)點。
• 可以使用兩個失敗條件終止深度限制搜索：
  • 標準故障值：表示問題沒有任何解決方案。
  • 截止故障值：它在給定的深度限制內(nèi)沒有定義問題的解決方案。
• 完整性：如果解決方案高于深度限制，則DLS搜索算法完成。
• 時間復雜度：DLS算法的時間復雜度為O(b?)。
• 空間復雜度：DLS算法的空間復雜度為O(b×l)。
• 最優(yōu)解：深度限制搜索可以看作是DFS的一個特例，即使?> d也不是最優(yōu)的。

Iterative deepening search

• 由Depth-limited search演化而成，每輪增加深度限制
• 迭代加深的深度優(yōu)先搜索(Iterative deepening depth-first Search)，逐步增大限制搜索的深度，直到返回目標結(jié)點。

• 迭代加深的深度優(yōu)先搜索是DFS和BFS算法的組合。此搜索算法找出最佳深度限制，并通過逐漸增加限制直到找到目標為止。迭代加深（Iterative deepening）搜索，實質(zhì)上就是限定下界的深度優(yōu)先搜索。即首先允許深度優(yōu)先搜索K層搜索樹，若沒有發(fā)現(xiàn)可行解，再將K+1后重復以上步驟搜索，直到搜索到可行解。
• 在迭代加深搜索的算法中，連續(xù)的深度優(yōu)先搜索被引入，每一個深度約束逐次加1，直到搜索到目標為止。
• 迭代加深搜索算法就是仿廣度優(yōu)先搜索的深度優(yōu)先搜索。既能滿足深度優(yōu)先搜索的線性存儲要求，又能保證發(fā)現(xiàn)一個最小深度的目標結(jié)點。
• 從實際應用來看，迭代加深搜索的效果比較好，并不比廣度優(yōu)先搜索慢很多，但是空間復雜度卻與深度優(yōu)先搜索相同，比廣度優(yōu)先搜索小很多，在一些層次遍歷的題目中，迭代加深不失為一種好方法！
• 該算法執(zhí)行深度優(yōu)先搜索直到某個“深度限制”，并且在每次迭代之后它不斷增加深度限制，直到找到目標節(jié)點。
• 此搜索算法結(jié)合了廣度優(yōu)先搜索的快速搜索和深度優(yōu)先搜索的內(nèi)存效率的優(yōu)勢。當搜索空間很大并且目標節(jié)點的深度未知時，迭代搜索算法對于無知搜索是有用的。

• 示例，以下樹結(jié)構(gòu)顯示迭代加深深度優(yōu)先搜索。IDDFS算法執(zhí)行各種迭代，直到找到目標節(jié)點。算法執(zhí)行的迭代如下
• 第1次迭代——-> A
  第2次迭代——> A，B，C
  第3次迭代———> A，B，D，E，C，F(xiàn)，G
  第4次迭代———> A，B，D，H，I，E，C，F(xiàn)，K，G
  在第四次迭代中，算法將找到目標節(jié)點。
• 完整性：如果分支因子是有限的，則該算法是完整的。
• 時間復雜性：假設b是分支因子，深度是d，那么最壞情況時間復雜度是O(b^d)。
• 空間復雜性：IDDFS的空間復雜度為O(bd)。
• 最優(yōu)解：如果路徑成本是節(jié)點深度的非遞減函數(shù)，則IDDFS算法是最佳的。

圖搜索

• 檢測不到重復狀態(tài)可能會將線性問題變成指數(shù)問題！

• 避免探索冗余路徑的方法是牢記曾經(jīng)走過的路。

• 為了做到這一點，我們給TREE-SEARCH搜索樹算法增加一個參數(shù)–這個數(shù)據(jù)結(jié)構(gòu)稱為探索集(也被稱為 closed 表)，用它記錄每個已擴展過的結(jié)點。

• 新生成的結(jié)點若與已經(jīng)生成的某個結(jié)點相匹配的話–即是在探索集中或是邊緣集中-那么它將被丟棄而不是被加入邊緣集中。

• 新算法叫 GRAPH-SEARCH，圖搜索

小結(jié)

文章來源地址http://www.zghlxwxcb.cn/news/detail-721640.html

到了這里，關(guān)于【人工智能】— 深度優(yōu)先搜索、代價一致搜索、深度有限搜索、迭代深度優(yōu)先搜索、圖搜索的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！