《人工智能及其應(yīng)用》課件第5章 搜索求解策略

第5章搜索求解策略技術(shù)日新月異，人類生活方式正在快速轉(zhuǎn)變，這一切給人類歷史帶來了一系列不可思議的奇點。我們曾經(jīng)熟悉的一切，都開始變得陌生?！s翰·馮·諾依曼,19585.1搜索的概念

搜索的主要過程①從初始或目的狀態(tài)出發(fā)，并將它作為當(dāng)前狀態(tài)。②掃描操作算子集，將適用當(dāng)前狀態(tài)的一些操作算子作用在其上而得到新的狀態(tài)，并建立指向其父結(jié)點的指針。③檢查所生成的新狀態(tài)是否滿足結(jié)束狀態(tài)，如果滿足，則得到解，并可沿著有關(guān)指針從結(jié)束狀態(tài)反向到達(dá)開始狀態(tài)，給出一解答路徑；否則，將新狀態(tài)作為當(dāng)前狀態(tài)，返回第②步再進(jìn)行搜索。5.2狀態(tài)空間表示

5.2狀態(tài)空間表示2.狀態(tài)空間的圖描述

狀態(tài)空間可用有向圖來描述，圖的結(jié)點表示問題的狀態(tài)，圖的弧表示狀態(tài)之間的關(guān)系，就是求解問題的步驟。

初始狀態(tài)對應(yīng)于實際問題的已知信息，是圖中的根結(jié)點。問題的狀態(tài)空間描述中，尋找從一種狀態(tài)轉(zhuǎn)換為另一種狀態(tài)的某個操作算子序列就等價于在一個圖中尋找某一路徑。5.2狀態(tài)空間表示

5.3盲目搜索回溯

回溯搜索是從初始狀態(tài)出發(fā)，不停地試探性地尋找路徑，直到到達(dá)目的或“不可解結(jié)點”，即“死胡同”為止。

回溯策略是當(dāng)遇到不可解結(jié)點時就回溯到路徑中最近的父結(jié)點上，查看該結(jié)點是否還有其他的子結(jié)點未被擴展。

若有，則沿這些子結(jié)點繼續(xù)搜索；如果找到目標(biāo)，就成功退出搜索，返回解題路徑。5.3.1回溯

回溯搜索的算法用三張表來保存狀態(tài)空間中的不同性質(zhì)結(jié)點。(1)路徑狀態(tài)表

路徑狀態(tài)（PathStates，PS）表保存當(dāng)前搜索路徑上的狀態(tài)。如果找到了目的，PS就是解路徑上的狀態(tài)有序集。(2)新的路徑狀態(tài)表的

新的路徑狀態(tài)（NewPathStates，NPS）表包含了等待搜索的狀態(tài)，其后裔狀態(tài)還未被搜索到，即未被生成擴展。(3)不可解狀態(tài)表

不可解狀態(tài)（NoSolvableStates，NSS）表列出了找不到解路徑的狀態(tài)。

如果在搜索中擴展出的狀態(tài)是它的元素，則可立即將之排除，不必沿該狀態(tài)繼續(xù)搜索。5.3.1回溯

目標(biāo)狀態(tài)之一5.3.1回溯5.3.1回溯5.3.2廣度優(yōu)先搜索

5.3.3廣度優(yōu)先搜索

5.3.3廣度優(yōu)先搜索

5.3.3深度優(yōu)先搜索

深度優(yōu)先搜索（Depth-FirstSearch，DFS）是盡可能快地深入樹中，每當(dāng)搜索方法可以做出選擇時，它選擇最左(或最右)的分支的次序A、B、D、E、C、F、G訪問節(jié)點來搜索狀態(tài)，它類似樹的先根遍歷，是樹的先根遍歷的推廣。5.3.3深度優(yōu)先搜索

5.4啟發(fā)式圖搜索5.4.1啟發(fā)式策略

啟發(fā)式（Heuristic）策略就是利用與問題有關(guān)的啟發(fā)信息引導(dǎo)搜索。在狀態(tài)空間搜索中，啟發(fā)式被定義成一系列操作算子，并能從狀態(tài)空間中選擇最有希望到達(dá)問題解的路徑。

問題求解系統(tǒng)可在兩種基本情況下運用啟發(fā)式策略。

①由于在問題陳述和數(shù)據(jù)獲取方面存在模糊性，可能會使一個問題沒有一個確定的解，這就要求系統(tǒng)能運用啟發(fā)式策略做出最有可能的解釋。

②雖然一個問題可能有確定解，但是其狀態(tài)空間特別大，搜索中生成擴展的狀態(tài)數(shù)會隨著搜索的深度呈指數(shù)級增長。5.4.1啟發(fā)式策略

5.4.1啟發(fā)式策略

5.4.2啟發(fā)信息和估價函數(shù)啟發(fā)信息按運用的方法不同可分為三種。

①陳述性啟發(fā)信息，一般被用于更準(zhǔn)確、更精煉地描述狀態(tài)，使問題的狀態(tài)空間縮小，如待求問題的特定狀況等屬于此類信息。

②過程性啟發(fā)信息，一般被用于構(gòu)造操作算子，使操作算子少而精，如一些規(guī)律性知識等屬于此類信息。

③控制性啟發(fā)信息，它是表示控制策略方面的知識，包括協(xié)調(diào)整個問題求解過程中所使用的各種處理方法、搜索策略、控制結(jié)構(gòu)等有關(guān)的知識。5.4.2啟發(fā)信息和估價函數(shù)

5.4.2啟發(fā)信息和估價函數(shù)

5.4.3A搜索算法

5.4.3A搜索算法

5.4.3A搜索算法例5.7A搜索算法求解8拼圖問題。

8拼圖問題是3拼圖問題的擴展，在一個3×3的方格盤上，放有1~8的數(shù)字，余下一格為空，空格移動規(guī)則同3拼圖問題。5.4.3A搜索算法

5.4.3A搜索算法例5.7A搜索算法求解8拼圖問題。

5.4.4A*搜索算法

A*搜索算法是由著名的人工智能學(xué)者Nilsson提出的，它是目前最有影響的啟發(fā)式圖搜索算法，也稱為最佳圖搜索算法。定義h*(??)為狀態(tài)??到目的狀態(tài)的最優(yōu)路徑的代價，則當(dāng)A*搜索算法的啟發(fā)函數(shù)h(n)小于等于h*(??)，即滿足h(n)≤h*(??)