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

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

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

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

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

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

5.3盲目搜索回溯

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

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

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

回溯搜索的算法用三張表來(lái)保存狀態(tài)空間中的不同性質(zhì)結(jié)點(diǎn)。(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)還未被搜索到，即未被生成擴(kuò)展。(3)不可解狀態(tài)表

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

如果在搜索中擴(kuò)展出的狀態(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）是盡可能快地深入樹(shù)中，每當(dāng)搜索方法可以做出選擇時(shí)，它選擇最左(或最右)的分支的次序A、B、D、E、C、F、G訪(fǎng)問(wèn)節(jié)點(diǎn)來(lái)搜索狀態(tài)，它類(lèi)似樹(shù)的先根遍歷，是樹(shù)的先根遍歷的推廣。5.3.3深度優(yōu)先搜索

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

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

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

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

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

5.4.1啟發(fā)式策略

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

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

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

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

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

5.4.3A搜索算法

5.4.3A搜索算法

5.4.3A搜索算法例5.7A搜索算法求解8拼圖問(wèn)題。

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

5.4.3A搜索算法例5.7A搜索算法求解8拼圖問(wèn)題。

5.4.4A*搜索算法

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