如果有興趣了解更多相關(guān)內(nèi)容，歡迎來我的個(gè)人網(wǎng)站看看：瞳孔空間

搜索是人工智能中的一個(gè)基本問題，并與推理密切相關(guān)。搜索策略的優(yōu)劣將直接影響到智能系統(tǒng)的性能與推理效率。

一：搜索的基本概念

搜索：根據(jù)問題的實(shí)際情況不斷尋找可利用的知識(shí)，構(gòu)造出一條代價(jià)較小的推理路線，使問題得到圓滿解決的過程。包括兩方面：

• 找到從初識(shí)事實(shí)到問題最終答案的一條推理路徑
• 找到的這條路徑在時(shí)間和空間上復(fù)雜度最小

搜索的分類(按是否使用啟發(fā)信息)：

• 盲目搜索(Uninformed search)：盲目搜索按預(yù)定的控制策略進(jìn)行搜索，搜索過程中獲得的中間信息不用來改變搜索策略。搜索總是按預(yù)定的路線進(jìn)行，不考慮問題本身的特性，這種搜索有盲目性，效率不高，不利于求解復(fù)雜問題。即不利用領(lǐng)域知識(shí)來幫助搜索
• 啟發(fā)式搜索(Heuristic search, Infomed search)：啟發(fā)式搜索中利用問題領(lǐng)域相關(guān)的信息作為啟發(fā)信息，用來指導(dǎo)搜索朝著最有希望的方向前進(jìn)，提高搜索效率并力圖找到最優(yōu)解

啟發(fā)式搜索需要利用問題領(lǐng)域相關(guān)的信息幫助搜索，但并不是對每一類問題都容易抽取出啟發(fā)信息，所以在很多情況下仍然需要盲目搜索。

搜索的適用情況：不良結(jié)構(gòu)或非結(jié)構(gòu)化問題；難以獲得求解所需的全部信息；沒有現(xiàn)成的算法可供求解使用

搜索問題的形式化表示：搜索首先要將問題進(jìn)行形式化表示，常用的形式化表示方式有狀態(tài)空間法、與或樹表示法(問題歸約法)等

搜索策略常用評價(jià)指標(biāo)：

• 完備性(Completeness)：如果問題有解，算法就能找到，稱此搜索方法是完備的
• 最優(yōu)性(Optimality)：如果解存在，總能找到最優(yōu)解
• 時(shí)間復(fù)雜度(Time Complexity)
• 空間復(fù)雜度(Space Complexity)

二：問題的狀態(tài)空間表示

2.1：概念

狀態(tài)(state)：事物是運(yùn)動(dòng)的、變化的，為描述問題的運(yùn)動(dòng)、變化，定義一組變量描述問題的變化特征和屬性

• 形式化表示：(s₁,s₂…s_i,…,s_n)
• 當(dāng)對每一個(gè)分量都給以確定的值時(shí)，就得到了一個(gè)具體的狀態(tài)

操作符(Operator)：也稱為算符，它是把問題從一種狀態(tài)變換為另一種狀態(tài)的手段

• 操作可以是一個(gè)機(jī)械步驟，一個(gè)運(yùn)算，一條規(guī)則或一個(gè)過程
• 操作可理解為狀態(tài)集合上的一個(gè)函數(shù)，它描述了狀態(tài)之間的關(guān)系

狀態(tài)空間(State space)：用來描述一個(gè)問題的全部狀態(tài)以及這些狀態(tài)之間的相互關(guān)系。常用一個(gè)三元組表示為：(S,F,G)

• S為問題的所有初始狀態(tài)的集合
• F為操作(函數(shù)、規(guī)則等)的集合
• G為目標(biāo)狀態(tài)的集合

狀態(tài)空間圖：狀態(tài)空間的有向圖表示

• 結(jié)點(diǎn)(節(jié)點(diǎn))：節(jié)點(diǎn)表示問題的狀態(tài)
• 弧(有向邊)：標(biāo)記操作符；可能的路徑代價(jià)

下圖即為狀態(tài)空間圖，S_i，S_j為兩個(gè)表示狀態(tài)的節(jié)點(diǎn)；O₁是導(dǎo)致狀態(tài)變化的操作符；cost(S_i,S_j)是從S_i變化到S_j的代價(jià)(花費(fèi))

狀態(tài)空間法求解問題的基本過程：

• 首先為問題選擇適當(dāng)?shù)?狀態(tài)"及“操作”的形式化描述方法
• 然后從某個(gè)初始狀態(tài)出發(fā)，每次使用一個(gè)滿足前提條件的"操作"，并且此操作產(chǎn)生了新的狀態(tài)，遞增地建立起操作序列，直到達(dá)到目標(biāo)狀態(tài)為止
• 此時(shí)，由初始狀態(tài)到目標(biāo)狀態(tài)所使用的算符(操作符)序列就是該問題的一個(gè)解

2.2：例題

2.2.1：八數(shù)碼問題

八數(shù)碼問題也叫九宮問題，是人工智能中狀態(tài)搜索中的經(jīng)典問題，其中，該問題描述為：在3×3的棋盤，擺有八個(gè)棋子，每個(gè)棋子上標(biāo)有1至8的某一數(shù)字，不同棋子上標(biāo)的數(shù)字不相同。棋盤上還有一個(gè)空格，與空格相鄰的棋子可以移到空格中。要求解決的問題是：給出一個(gè)初始狀態(tài)和一個(gè)目標(biāo)狀態(tài)，找出一種從初始轉(zhuǎn)變成目標(biāo)狀態(tài)的移動(dòng)棋子步數(shù)最少的移動(dòng)步驟。

解法：

狀態(tài)表示：

定義操作符（產(chǎn)生式規(guī)則）：

狀態(tài)空間搜索：

這其實(shí)不是解法，只是用狀態(tài)空間表示了八數(shù)碼問題，下面兩個(gè)問題也是這樣。如果想了解解法，可以繼續(xù)往下看，在啟發(fā)式搜索的內(nèi)容中會(huì)介紹具體解法。但更多更詳細(xì)的八數(shù)碼解法，建議看看這個(gè)博客：八數(shù)碼問題

2.2.2：TSP問題

TSP(Traveling Salesman Problem)問題，即旅行商問題。假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路徑，路徑的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。如下圖，旅行商從A出發(fā)，請找出一條花費(fèi)最少的旅行路徑。

解：

狀態(tài)表示：

定義操作符：

狀態(tài)空間搜索：

計(jì)算花費(fèi)的例子：

同樣，這也沒有真正解決TSP問題，只是用狀態(tài)空間表示了這個(gè)問題，具體解決方案可以參照下面的啟發(fā)式搜索內(nèi)容，當(dāng)然更詳細(xì)的解決方案我還是推薦這篇文章：智能優(yōu)化算法解決TSP旅行商問題–小總結(jié)

2.2.3：過河問題

在河的左岸有3個(gè)傳教士、3個(gè)野人和一條船，傳教士們想用這條船把所有人都運(yùn)過河去，但有以下條件限制：

1. 修道士和野人都會(huì)劃船，但船每次最多只能運(yùn)2個(gè)人；
2. 在任何岸邊野人數(shù)目都不能超過修道士，否則修道士會(huì)被野人吃掉。

假定野人會(huì)服從任何一種過河安排，請規(guī)劃出一個(gè)確保傳道士安全過河的計(jì)劃。

解：

狀態(tài)表示：

操作符(產(chǎn)生式規(guī)則)：


狀態(tài)空間搜索：

具體解法可以參考：野人傳教士過河問題

三：狀態(tài)空間搜索

3.1：基本概念

狀態(tài)空間搜索的基本思想：先把問題的初始狀態(tài)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)對其進(jìn)行擴(kuò)展，生成一組子節(jié)點(diǎn)，然后檢查問題的目標(biāo)狀態(tài)是否出現(xiàn)在這些子節(jié)點(diǎn)中。若出現(xiàn)，則搜索成功，找到了問題的解；若沒出現(xiàn)，則再按照某種搜索策略從已生成的子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)。重復(fù)上述過程，直到目標(biāo)狀態(tài)出現(xiàn)在子節(jié)點(diǎn)中或者沒有可供操作的節(jié)點(diǎn)為止。所謂對一個(gè)節(jié)點(diǎn)進(jìn)行“擴(kuò)展”是指對該節(jié)點(diǎn)用某個(gè)可用操作進(jìn)行作用，生成該節(jié)點(diǎn)的一組子節(jié)點(diǎn)。

擴(kuò)展節(jié)點(diǎn)：對某一節(jié)點(diǎn)(狀態(tài))，選擇合適的操作符作用在節(jié)點(diǎn)上，使產(chǎn)生后繼狀態(tài)(子節(jié)點(diǎn))的操作。類似數(shù)據(jù)結(jié)構(gòu)中的尋找鄰接點(diǎn)，但這里的鄰接點(diǎn)是選擇操作后產(chǎn)生的。

open表和closed表：這兩個(gè)表用來存放節(jié)點(diǎn)，Open表存放未擴(kuò)展節(jié)點(diǎn)，Closed表存放已擴(kuò)展節(jié)點(diǎn)和待擴(kuò)展結(jié)點(diǎn)，也可根據(jù)需要擴(kuò)展表的結(jié)構(gòu)，比如加入代價(jià)字段等。兩個(gè)表的結(jié)構(gòu)可以相同，大致如下：

3.2：圖搜索一般過程

1. 建立一個(gè)只含初始狀態(tài)節(jié)點(diǎn)S的搜索圖G，建立一個(gè)OPEN表，用來存放未擴(kuò)展節(jié)點(diǎn)，將S放入
   OPEN表中
2. 建立一個(gè)CLOSED表，用來存放已擴(kuò)展和待擴(kuò)展節(jié)點(diǎn)，初始為空
3. LOOP：若OPEN為空，則失敗、退出
4. 選擇OPEN表中的第一個(gè)節(jié)點(diǎn)，將其移到CLOSED表中，稱此節(jié)點(diǎn)為n節(jié)點(diǎn)
5. 若n為目標(biāo)節(jié)點(diǎn)，則成功、退出。此解是追蹤圖G沿著指針從n到S這條路徑得到的。
6. 擴(kuò)展n節(jié)點(diǎn)，生成n的后繼節(jié)點(diǎn)集合M=M1+M2+M3，其中n的后繼結(jié)點(diǎn)分為3種情況。設(shè)M1表示圖G中新結(jié)點(diǎn)(最新生成的)；M2在圖G中已經(jīng)存在，處于OPEN表中；M3在圖G中已經(jīng)存在，且已經(jīng)在CLOSED表中：
   • 對M1型結(jié)點(diǎn)，加入到圖G中，并放入OPEN表中，設(shè)置一個(gè)指向父節(jié)點(diǎn)n
     的指針;(DS中的未訪問鄰接點(diǎn))
   • 對M2型結(jié)點(diǎn)，已經(jīng)在OPEN中，確定是否需要修改父節(jié)點(diǎn)指針;(DS中
     已訪問鄰接點(diǎn)，但這個(gè)頂點(diǎn)的鄰接點(diǎn)未搜索)
   • 對M3型結(jié)點(diǎn)，已經(jīng)在CLOSED表中，確定是否修改其父結(jié)點(diǎn)指針;是否
     修改其后裔節(jié)點(diǎn)的指針;(DS中已訪問鄰接點(diǎn)，且這個(gè)頂點(diǎn)的鄰接點(diǎn)都已經(jīng)搜索過)
7. 按某一控制策略，重新排序OPEN表
8. goto LOOP

圖搜索的幾點(diǎn)說明：

1. 這是狀態(tài)空間的一般搜索過程，具有通用性，后面討論的各種搜索策略都是此過程的一個(gè)特例。不同特例的區(qū)別在于OPEN表的排序方式不同
2. 擴(kuò)展節(jié)點(diǎn)n，生成的子節(jié)點(diǎn)，分為三種情況：M1是圖G中沒有的新節(jié)點(diǎn)；M2是已在圖G中，但沒有被擴(kuò)展，即在OPEN表中；M3是已在圖G中，且已經(jīng)被擴(kuò)展生成了子節(jié)點(diǎn)，即已在CLOSED表中

四：狀態(tài)空間盲目搜索

盲目搜索按預(yù)定的控制策略進(jìn)行搜索，搜索過程中獲得的中間信息不用來改變搜索策略。搜索總是按預(yù)定的路線進(jìn)行，不考慮問題本身的特性，這種搜索有盲目性，效率不高，不利于求解復(fù)雜問題。

4.1：廣度優(yōu)先搜索

廣度優(yōu)先搜索(BFS-Breadth First Search)：由近及遠(yuǎn)逐層訪問圖中頂點(diǎn)(典型的層次遍歷)。

節(jié)點(diǎn)深度：起始節(jié)點(diǎn)S(根節(jié)點(diǎn)，圖中選定起始搜索頂點(diǎn))深度為0；其他節(jié)點(diǎn)等于父節(jié)點(diǎn)深度加1。

基本思想：從初始節(jié)點(diǎn)S開始，依據(jù)到S的深度，逐層擴(kuò)展節(jié)點(diǎn)并考察其是否目標(biāo)節(jié)點(diǎn)。在第n層節(jié)點(diǎn)沒有完全擴(kuò)展之前，不對第n+1層節(jié)點(diǎn)進(jìn)行擴(kuò)展。即：OPEN表排序策略為新產(chǎn)生的節(jié)點(diǎn)放到OPEN表的末端。

BFS遍歷搜索算法：從初始狀態(tài)節(jié)點(diǎn)S出發(fā)廣度優(yōu)先搜索遍歷圖的算法bfs(S)

1. 訪問S
2. 依次訪問S的各鄰接點(diǎn)
3. 設(shè)最近一層訪問序列為V_i1，V_i2，…,V_ik，則依次訪問V_i1，V_i2，…，V_ik的未被訪問過的鄰接點(diǎn)
4. 重復(fù)3，直到找不到未被訪問的鄰接點(diǎn)為止

例如，對下圖進(jìn)行廣度優(yōu)先遍歷：

頂點(diǎn)訪問序列為：1 -> 2 -> 8 -> 3 -> 4 -> 9 -> 10 -> 5 -> 6 -> 7

BFS(1)的生成樹：

狀態(tài)空間廣度優(yōu)先搜索：

1. 把初始節(jié)點(diǎn)S0放入Open表中
2. 如果Open表為空，則問題無解，失敗退出
3. 把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為n
4. 考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則得到問題的解，成功退出
5. 若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第2步;
6. 擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入Open表的尾部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第2步

八數(shù)碼問題的BFS解法：

性能：

• 完備的
• 最優(yōu)的一對搜索深度指標(biāo)
• 時(shí)間復(fù)雜度：O(a^b)
  • 樹的分枝因子(度)：樹中最大的子節(jié)點(diǎn)數(shù)(按最壞情況考慮)設(shè)為a
  • 搜索深度：b
• 空間復(fù)雜度：O(a^b)

優(yōu)點(diǎn)：

• 只要問題有解，則總可以得到解，而且是最短路徑(深度)的解

缺點(diǎn)：

• 當(dāng)目標(biāo)節(jié)點(diǎn)距離初始節(jié)點(diǎn)較遠(yuǎn)時(shí)會(huì)產(chǎn)生許多無用的節(jié)點(diǎn)，搜索效率低
• 空間是大問題(和時(shí)間相比)

應(yīng)用實(shí)例：搜索引擎的網(wǎng)絡(luò)爬蟲——網(wǎng)頁超鏈接的廣度優(yōu)先搜索：處理一個(gè)網(wǎng)頁上的所有超鏈接后，再進(jìn)入下一層頁面處理

搜索引擎所用的第一代網(wǎng)絡(luò)爬蟲主要是基于傳統(tǒng)的圖算法，如寬度優(yōu)先或深度優(yōu)先算法來索引整個(gè)Web，一個(gè)核心的URL集被用來作為一個(gè)種子集合，這種算法遞歸的跟蹤超鏈接到其它頁面，而通常不管頁面的內(nèi)容，因?yàn)樽罱K的目標(biāo)是這種跟蹤能覆蓋整個(gè)Web。這種策略通常用在通用搜索引擎中，因?yàn)橥ㄓ盟阉饕娅@得的網(wǎng)頁越多越好，沒有特定的要求.

4.2：深度優(yōu)先搜索

深度優(yōu)先搜索(DFS-Depth First Search)：從初始節(jié)點(diǎn)S開始，優(yōu)先擴(kuò)展最新產(chǎn)生的節(jié)點(diǎn)(最深的節(jié)點(diǎn))。即：OPEN表排序策略為新產(chǎn)生的節(jié)點(diǎn)放到OPEN表的前端，優(yōu)先擴(kuò)展。

DFS遍歷搜索算法：從初始狀態(tài)頂點(diǎn)S出發(fā)深度優(yōu)先遍歷圖的方法

1. 訪問S——visit (S)
2. 依次從S的未被訪問過的鄰接點(diǎn)出發(fā)進(jìn)行深度遍歷

頂點(diǎn)訪問序列為：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

執(zhí)行DFS(1)的生成樹：

狀態(tài)空間深度優(yōu)先搜索：

1. 把初始節(jié)點(diǎn)s放入OPEN表
2. 如果OPEN表為空，則問題無解，退出
3. 把OPEN表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)取出，放入CLOSED表
4. 考查節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)，若是，則求得了問題的解，退出
5. 若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第2步
6. 擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN表的首部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，轉(zhuǎn)第2步

DFS解決八數(shù)碼問題思路：

性能：

• 非完備的。如果當(dāng)前搜索分支為無窮分支且無解，搜索將一直持續(xù)下去而得不到解。
• 非最優(yōu)的
• 時(shí)間復(fù)雜度：O(a^b)
  • 樹的分枝因子(度)：樹中最大的子節(jié)點(diǎn)數(shù)(按最壞情況考慮)，設(shè)為a
  • 搜索深度：b
• 空間復(fù)雜度：O(a*b)

應(yīng)用實(shí)例：搜索引擎中的網(wǎng)絡(luò)爬蟲——選取一個(gè)網(wǎng)頁，選擇一個(gè)超鏈接，進(jìn)入下一個(gè)頁面，選擇一個(gè)超鏈接，再進(jìn)入下一個(gè)頁面，直到一個(gè)頁面沒有超鏈接，再逐層返回處理下一個(gè)超鏈接。

注意：

• 這里的BFS和DFS與數(shù)據(jù)結(jié)構(gòu)中的算法的唯一區(qū)別是不一定要遍歷所有頂點(diǎn)
• 這里只要到達(dá)目標(biāo)頂點(diǎn)，算法即結(jié)束

4.3：有界深度優(yōu)先搜索

在深度優(yōu)先搜索中，如果進(jìn)入無窮且無解分支，搜索將一直持續(xù)下去，得不到問題的解，白白浪費(fèi)計(jì)算機(jī)的時(shí)間、空間資源。為了防止出現(xiàn)此類情況人們提出了有界深度優(yōu)先搜索策略。

指定最大搜索深度dmax作為深度界限，仍按深度優(yōu)先搜索方法搜索，當(dāng)搜索到深度界限仍未到達(dá)目標(biāo)，則視此搜索路徑無解，繼續(xù)搜索其他路徑。

有界深度優(yōu)先搜索性能同深度優(yōu)先搜索。

有界深度搜索過程如下:

1. 把初始節(jié)點(diǎn)S放入OPEN表，置S的深度d(S)=0
2. 如果OPEN表為空，則問題無解，退出
3. 把OPEN表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)取出，放入CLOSED表
4. 考查節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)，若是，則求得了問題的解，退出
5. 如果節(jié)點(diǎn)n的深度d(節(jié)點(diǎn)n)=dmax。則轉(zhuǎn)第2步
6. 若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第2步
7. 擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN表的首部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，轉(zhuǎn)第2步

4.4：迭代加深深度優(yōu)先搜索

在有界深度優(yōu)先搜索中，如果深度界限設(shè)定不合適，太小則可能遺漏問題的解，太大則浪費(fèi)時(shí)空資源。

迭代加深搜索中，深度界限是動(dòng)態(tài)變化的，從深度為1開始，找不到目標(biāo)，就把深度界限加1，重新開始深度優(yōu)先搜索，直到找到解或無解為止

性能：

• 完備的
• 最優(yōu)的：對于深度指標(biāo)
• 時(shí)間復(fù)雜度：O(a^b)
  • 樹的分枝因子(度)：樹中最大的子節(jié)點(diǎn)數(shù)(按最壞情況考慮)設(shè)為a
  • 搜索深度：b
• 空間復(fù)雜度：O(a*b)

五：狀態(tài)空間的啟發(fā)式搜索

啟發(fā)式搜索，又叫做有信息搜索

盲目搜索是按事先規(guī)定的路線進(jìn)行搜索。這些策略搜索效率低下，浪費(fèi)計(jì)算機(jī)時(shí)空資源，容易造成組合爆炸?？赡軄G掉最優(yōu)解甚至全部解。而啟發(fā)式搜索策略在搜索過程中，會(huì)針對問題自身的特性，利用問題領(lǐng)域的相關(guān)信息來幫助搜索，使得搜索朝著最有希望的方向前進(jìn)，提高搜索效率。

5.1：啟發(fā)性信息和估價(jià)函數(shù)

啟發(fā)信息：關(guān)于問題領(lǐng)域的，用來幫助搜索的信息。

啟發(fā)信息按信息用途分類：

• 用于決定下一個(gè)要擴(kuò)展的節(jié)點(diǎn)：總是選擇最有希望產(chǎn)生目標(biāo)的節(jié)點(diǎn)（鄰接點(diǎn)）優(yōu)先擴(kuò)展，即OPEN表按此希望值排序。這類啟發(fā)信息使用最為廣泛
• 用于決定產(chǎn)生哪些子節(jié)點(diǎn)：擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)，有選擇的生成子節(jié)點(diǎn)（選擇訪問鄰接點(diǎn))，有些明顯無用或沒有優(yōu)勢的子節(jié)點(diǎn)不讓其產(chǎn)生出來
• 用于決定從搜索圖中修剪或拋棄哪些節(jié)點(diǎn)
  • 減小待搜索空間
  • 搜索圖中，不訪問這些頂點(diǎn)，或直接刪除掉這些頂點(diǎn)

估價(jià)函數(shù)(evaluation function)與啟發(fā)函數(shù)(heuristic function)：

• 利用啟發(fā)信息，構(gòu)造一個(gè)函數(shù)，對搜索路徑全程的代價(jià)或希望進(jìn)行評估
• 下右圖，當(dāng)前節(jié)點(diǎn)為n，定義估價(jià)函數(shù)f(n)：從初始節(jié)點(diǎn)S開始，約束通過n，到達(dá)目標(biāo)節(jié)點(diǎn)G的全程代價(jià)的估計(jì)值。即：f(n)=g(n)+h(n)
  • g(n)為從S到n，已經(jīng)走過的路徑代價(jià)估計(jì)，通常即用實(shí)際花費(fèi)代價(jià)，也比較容易計(jì)算
  • h(n)是從n到達(dá)目標(biāo)G代價(jià)的估值，這一段路徑是沒有走過的，必須根據(jù)問題特性，利用啟發(fā)信息進(jìn)行估算。搜索的啟發(fā)性即體現(xiàn)在h(n)上，所以把h(n)叫做啟發(fā)函數(shù)

估價(jià)函數(shù)的構(gòu)造對多數(shù)問題不是一件容易的事。搜索的有效性取決于估價(jià)函數(shù)的構(gòu)造，不當(dāng)?shù)墓纼r(jià)函數(shù)可能失去最優(yōu)解甚至全部解。此外，構(gòu)造估價(jià)函數(shù)時(shí)要考慮時(shí)空代價(jià)的折中。保證有效性的優(yōu)先次序是至少保證能找到解，然后保證能獲得較優(yōu)解，最后是獲得一個(gè)最優(yōu)解。

5.2：A算法

A算法又叫最好優(yōu)先搜索(Best First Search)、有序搜索(Ordered Search)。在圖搜索算法中，如果能在搜索的每一步都利用估價(jià)函數(shù)f(n)=g(n)+h(n)對Open表中的節(jié)點(diǎn)進(jìn)行排序，則該搜索算法為A算法。

A算法描述：

1. 把初始節(jié)點(diǎn)S放入Open表中，f(S)=g(S)+h(S)
2. 如果Open表為空，則問題無解，失敗退出
3. 把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為n
4. 考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則找到了問題的解，成功退出
5. 若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第2步
6. 擴(kuò)展節(jié)點(diǎn)n，生成其子節(jié)點(diǎn)n_i(i=1，2，…)，計(jì)算每一個(gè)子節(jié)點(diǎn)的估價(jià)值f(n_i)(i=1，2，…)，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針，然后將這些子節(jié)點(diǎn)放入Open表中
7. 根據(jù)各節(jié)點(diǎn)的估價(jià)A數(shù)值，對Open表中的全部節(jié)點(diǎn)按從小到天的順序重新進(jìn)行排序
8. 轉(zhuǎn)第2步

性能：

• 完備的
• 非最優(yōu)的
• 時(shí)間復(fù)雜度：O(a^b)
  • 樹的分枝因子(度)：樹中最大的子節(jié)點(diǎn)數(shù)(按最壞情況考慮)設(shè)為a
  • 搜索深度：b
• 空間復(fù)雜度：O(a^b)

例題：下圖為一個(gè)城市地圖，用最好優(yōu)先搜索求從a城市出發(fā)到達(dá)i城市的路徑。g(n)用從a城市到n城市走過的實(shí)際距離。h(n)用后面的表給出，您可以設(shè)想h(n)為n到達(dá)i的直線距離。

求解過程如下，用A算法求解路徑為：aeghi(418)，其中，實(shí)際路徑代價(jià)(距離)為418

A搜索算法得到的解為aeghi，在本題中為最優(yōu)解，因?yàn)楸绢}滿足了A算法的條件。但需要注意的是A算法不保證能取得全局最優(yōu)解。

A算法求解八數(shù)碼問題：

5.3：爬山搜索算法

爬山搜索是一種貪婪算法，其本質(zhì)上是梯度下降法。在評估函數(shù)f(n)=g(n)+h(n)中，令g(n)=0，即f(n)=h(n)，A算法即成為爬山搜索算法。

爬山算法每次從當(dāng)前的節(jié)點(diǎn)開始，與周圍的鄰接點(diǎn)進(jìn)行比較：

• 若當(dāng)前節(jié)點(diǎn)是最大的，那么返回當(dāng)前節(jié)點(diǎn)，作為最大值
• 若當(dāng)前節(jié)點(diǎn)是最小的，就用最高的鄰接點(diǎn)替換當(dāng)前節(jié)點(diǎn)，從而實(shí)現(xiàn)向山峰的高處攀爬的目的

如此循環(huán)往復(fù)，直到達(dá)到最高點(diǎn)為止。但該算法的主要問題是：局部最大，即某個(gè)節(jié)點(diǎn)會(huì)比周圍任何一個(gè)鄰居都高，但只是局部最優(yōu)解，并非全局最優(yōu)解。

如下圖，在處于當(dāng)前解時(shí)，爬山法搜索到局部最優(yōu)解后，就會(huì)停止搜索，因?yàn)樵诰植孔顑?yōu)解這個(gè)點(diǎn)，無論向哪個(gè)方向小幅度的移動(dòng)，都無法得到更優(yōu)解

此外，其還存在以下兩種問題：

• 高地問題：搜索一旦到達(dá)高地，就無法確定搜索最佳方向，會(huì)產(chǎn)生隨機(jī)走動(dòng)，使得搜索效率降低
• 山脊問題：搜索可能會(huì)在山脊的兩面來回震蕩，前進(jìn)步伐很小

用爬山算法求解上面的TSP問題：

由于g(n)=0，所以解為aei：

本題有3條解路徑：

• aei，全程實(shí)際代價(jià)為440
• aefi，全程實(shí)際代價(jià)為450
• aeghi，全程實(shí)際代價(jià)為418

而爬山搜索得到的解為aei，可見不是全局最優(yōu)解。但對比前面A算法，可見爬山搜索效率較高。

5.4：等代價(jià)搜索

等代價(jià)搜索(Uniformed-cost search)，即Dijkstra(迪杰斯特拉)算法。在評估函數(shù)f(n)=g(n)+h(n)中，令h(n)=0，f(n)=g(n)，且g(n)為實(shí)際路徑代價(jià)，此時(shí)的A算法稱為等代價(jià)搜索。

為什么等代價(jià)搜索屬于盲目搜索：因?yàn)閔(n)=0，沒有了啟發(fā)性，所以屬于盲目搜索

性能：

• 最優(yōu)性—找到全局最優(yōu)解
• 完備性
• 時(shí)空復(fù)雜度同A算法
• 搜索效率低

用等代價(jià)搜索求解上述TSP問題：

求解如下

5.5：A*算法

對A算法中的評估函數(shù)加上一些限制，使為A*算法。

公式表示為： f*(n)=g*(n)+h*(n)

• f*(n) 是從初始狀態(tài)經(jīng)由狀態(tài)n到目標(biāo)狀態(tài)的最小路徑代價(jià)
• g*(n) 是在狀態(tài)空間中從初始狀態(tài)到狀態(tài)n的實(shí)際代價(jià)
• h*(n) 是從狀態(tài)n到目標(biāo)狀態(tài)的路徑的最小估計(jì)代價(jià)。若有多個(gè)目標(biāo)結(jié)點(diǎn)，取其中的最接近值

當(dāng)A算法的評估函數(shù)f(n)=g(n)+h(n)滿足以下條件，即為A*算法：

• g(n) >= g*(n) && g(n) > 0
• h(n) <= h*(n)

實(shí)際使用時(shí)，常使g(n)=g*(n)，即從S到n的實(shí)際最小代價(jià)

• g(n)表示從點(diǎn)S到達(dá)節(jié)點(diǎn)n的當(dāng)前最小代價(jià)
• g*(n)表示從節(jié)點(diǎn)S到節(jié)點(diǎn)n的實(shí)際最小代價(jià)
• h(n)表示從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)G的預(yù)估代價(jià)
• h*(n)表示從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)G的實(shí)際最小代價(jià)

真實(shí)h(n)的選取：保證找到最短路徑（最優(yōu)解的）條件，關(guān)鍵在于估價(jià)函數(shù)f(n)的選?。ɑ蛘哒fh(n)的選?。?。
以h(n)表達(dá)狀態(tài)n到目標(biāo)狀態(tài)估計(jì)的距離，那么h(n)的選取大致有如下情況：

• 在極端情況下，當(dāng)啟發(fā)函數(shù)h(n)始終為0，則將由g(n)決定節(jié)點(diǎn)的優(yōu)先級，此時(shí)算法就退化成了Dijkstra算法。
• 如果h(n)始終小于等于h*(n)，則A*算法保證一定能夠找到最短路徑。但是當(dāng)h(n)的值越小，算法將遍歷越多的節(jié)點(diǎn)，也就導(dǎo)致算法越慢。
• 如果h(n)完全等于h*(n)，則A*算法將找到最佳路徑，并且速度很快?？上У氖?，并非所有場景下都能做到這一點(diǎn)。因?yàn)樵跊]有達(dá)到終點(diǎn)之前，我們很難確切算出距離終點(diǎn)還有多遠(yuǎn)。
• 如果h(n)的值比h*(n)大，則A*算法不能保證找到最短路徑，不過此時(shí)會(huì)很快。
• 在另外一個(gè)極端情況下，如果h(n)相較于g(n)大很多，則此時(shí)只有h(n)產(chǎn)生效果，這也就變成了最佳優(yōu)先搜索。

A*算法的特點(diǎn)：文章來源地址http://www.zghlxwxcb.cn/news/detail-498039.html

• 最優(yōu)性：保證最優(yōu)解存在時(shí)能找到最優(yōu)解
• 可采納性：算法能在有限步內(nèi)終止，并能找到最優(yōu)解

5.6：f(n)=g(n)+h(n)討論

• f(n)=g(n)，h(n)=0，g(n)為實(shí)際路徑代價(jià)：等代價(jià)搜索——效率不高，能得到最優(yōu)解
• f(n)=h(n)，g(n)=0，爬山搜索——效率極高，往往陷入局部最優(yōu)
• f(n)=g(n)+h(n)，g(n)>0，h(n)>0，最好優(yōu)先搜索——但是設(shè)計(jì)估價(jià)函數(shù)時(shí)要充分考慮g(n)和h(n)的數(shù)量級要相當(dāng)。否則當(dāng)g(n)>>h(n)時(shí)，接近等代價(jià)搜索；h(n)>>g(n)時(shí)，接近爬山搜索
• f(n)=g(n)+h(n)，g(n)>0，且g(n)>=g*(n)，h(n)<=h*(n)，A*算法——為了兼顧搜索效率，在滿足上述條件前提下，要盡可能取較大的h(n)值，盡可能提高搜索效率
• f(n)=0，即g(n)=0，h(n)=0，盲目搜索

到了這里，關(guān)于搜索技術(shù)——盲目與啟發(fā)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！