復(fù)試1人工智能08

1、第8章 盲目搜索用公式表示狀態(tài)空間隱式狀態(tài)空間圖的組成廣度優(yōu)先搜索深度優(yōu)先或回溯搜索迭代加深補(bǔ)充讀物和討論8.1 用公式表示狀態(tài)空間很多實(shí)際問(wèn)題的搜索空間是如此之大，以致我們不能通過(guò)顯式圖來(lái)表示。本章需要上一章所講到的基本搜索過(guò)程的細(xì)節(jié)。首先，我們非常關(guān)心如何用公式表示這些搜索問(wèn)題；第二，我們必須找到隱式表示大的搜索圖的方法；第三，我們需要用高效的算法來(lái)對(duì)這些大圖進(jìn)行搜索。在一些規(guī)劃的問(wèn)題中，如堆積木，想像代表各種環(huán)境狀態(tài)的數(shù)據(jù)結(jié)構(gòu)和改變它們的動(dòng)作是不難的。然而，找到可管理狀態(tài)空間圖的表示是很難的。必須仔細(xì)分析問(wèn)題考慮對(duì)稱性，忽略不相關(guān)的細(xì)節(jié)，發(fā)現(xiàn)適當(dāng)?shù)某橄蟮取５⒁粋€(gè)搜索問(wèn)題的任務(wù)仍然是一

2、個(gè)需要人工參與的大問(wèn)題。8.1 用公式表示狀態(tài)空間除了agent堆積木等問(wèn)題外，數(shù)碼問(wèn)題也常被用來(lái)演示如何在狀態(tài)空間中生成動(dòng)作序列?？紤]到多樣化，一個(gè)典型的例子是15數(shù)碼問(wèn)題。它由放在一個(gè)4X4的方陣中的15個(gè)數(shù)碼組成，其中的一個(gè)單元是空的，它的周邊單元的數(shù)碼可以移到該單元中。此問(wèn)題的任務(wù)是找到一個(gè)數(shù)碼移動(dòng)序列使初始的無(wú)序數(shù)碼轉(zhuǎn)變?yōu)橐恍┨厥獾呐帕小?數(shù)碼問(wèn)題是一個(gè)簡(jiǎn)化版本。在一個(gè)3X3的方陣中有8個(gè)數(shù)碼。假定該問(wèn)題的目標(biāo)是把數(shù)碼從開始狀態(tài)移動(dòng)到目標(biāo)狀態(tài)。8.1 用公式表示狀態(tài)空間8數(shù)碼問(wèn)題的開始和目標(biāo)狀態(tài)28316475123847658.1 用公式表示狀態(tài)空間一個(gè)明顯的圖標(biāo)狀態(tài)描述是一個(gè)3X

3、3的方陣。方陣中的每個(gè)單元中包含1-8之間的數(shù)字或一個(gè)代表空格的符號(hào)。在構(gòu)造一個(gè)問(wèn)題的狀態(tài)空間時(shí)我們有一些代表性的選擇。在8數(shù)碼問(wèn)題中，我們可以想像有8X4種不同的移動(dòng)，它們是1上移、1下移、1左移、1右移。當(dāng)然，在一個(gè)給定的狀態(tài)中，并不是所有的這些移動(dòng)都是可能的。一個(gè)更精練的公式只有四個(gè)移動(dòng)，即空格左移、空格上移、空格下移、空格上移。一個(gè)給定的開始狀態(tài)和一組可能的移動(dòng)隱式地定義了從開始狀態(tài)可到達(dá)的一個(gè)狀態(tài)圖。在8數(shù)碼表示的狀態(tài)空間中節(jié)點(diǎn)數(shù)是9！=362880個(gè)8.2 隱式狀態(tài)空間圖的組成有三個(gè)基本部分參與表示隱式狀態(tài)空間圖1) 一個(gè)標(biāo)識(shí)開始節(jié)點(diǎn)的描述。這個(gè)描述是對(duì)環(huán)境初始狀態(tài)建模的一些數(shù)據(jù)結(jié)

4、構(gòu)2）把代表環(huán)境狀態(tài)的狀態(tài)描述轉(zhuǎn)換成代表動(dòng)作后狀態(tài)描述的轉(zhuǎn)換函數(shù)。這些函數(shù)也常被叫做算子。在agent問(wèn)題中，它們是動(dòng)作結(jié)果的模型。當(dāng)一個(gè)算子應(yīng)用到一個(gè)節(jié)點(diǎn)時(shí)，它產(chǎn)生該節(jié)點(diǎn)的一個(gè)后繼節(jié)點(diǎn)。3）目標(biāo)狀態(tài)，可以是狀態(tài)描述中的一個(gè)真假值函數(shù)，或者是和目標(biāo)狀態(tài)一致的狀態(tài)描述的真實(shí)實(shí)例列表。8.2 隱式狀態(tài)空間圖的組成有兩類主要的搜索過(guò)程。其中之一，沒(méi)有指定問(wèn)題的任何推理信息。例如要搜索這一部分而不是另一部分，就像到目前為止的只要發(fā)現(xiàn)一條到目標(biāo)的路徑即可。這種過(guò)程被稱為盲目的。另一種，指定了要解決問(wèn)題的信息以幫助集中搜索。這個(gè)過(guò)程叫啟發(fā)式搜索（heuristic）。8.3 廣度優(yōu)先搜索最簡(jiǎn)單的搜索過(guò)程是

5、廣度優(yōu)先搜索（breadth-first search）。該過(guò)程把所有的算子應(yīng)用到開始節(jié)點(diǎn)以產(chǎn)生一個(gè)顯式的狀態(tài)空間圖，再把所有可能的算子應(yīng)用到開始節(jié)點(diǎn)的所有直接后繼，再到后繼的后繼，等等。搜索節(jié)點(diǎn)一律從開始節(jié)點(diǎn)向外擴(kuò)展。由于每一步將所有可能的算子應(yīng)用到一個(gè)節(jié)點(diǎn)，因此可把它們組成一個(gè)叫做后繼函數(shù)（successor function）的函數(shù)。當(dāng)把后繼函數(shù)應(yīng)用到一個(gè)節(jié)點(diǎn)時(shí)，產(chǎn)生一個(gè)節(jié)點(diǎn)集。該節(jié)點(diǎn)集就是把所有能應(yīng)用到那個(gè)節(jié)點(diǎn)的算子應(yīng)用到該節(jié)點(diǎn)而產(chǎn)生的。一個(gè)節(jié)點(diǎn)的后繼函數(shù)的每一次應(yīng)用稱為節(jié)點(diǎn)的擴(kuò)展（expanding）。8.3 廣度優(yōu)先搜索相同深度的節(jié)點(diǎn)按照一些固定的順序擴(kuò)展。在擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)，按空格

6、左移、上移、右移、下移的順序應(yīng)用算子。廣度優(yōu)先的一個(gè)特征是：當(dāng)發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)時(shí)，我們已經(jīng)找到了到達(dá)目標(biāo)的一條最短路徑。然而廣度優(yōu)先搜索的一個(gè)缺點(diǎn)是它要求產(chǎn)生和存儲(chǔ)一個(gè)大小是最淺目標(biāo)節(jié)點(diǎn)深度的指數(shù)的樹。相同代價(jià)搜索是廣度優(yōu)先搜索的一種變體，在該方法中，節(jié)點(diǎn)從開始節(jié)點(diǎn)順著代價(jià)等高點(diǎn)向外擴(kuò)展，而不是順著相同深度等高線。如果圖中所有弧的代價(jià)相同，那么相同代價(jià)搜索就和廣度優(yōu)先搜索一致。8.4 深度優(yōu)先搜索深度優(yōu)先搜索一次對(duì)節(jié)點(diǎn)應(yīng)用一個(gè)算子以產(chǎn)生該節(jié)點(diǎn)的一個(gè)后繼。每一個(gè)節(jié)點(diǎn)都留下一個(gè)標(biāo)記，用來(lái)指示如果需要時(shí)所必須的附加算子。對(duì)每一個(gè)節(jié)點(diǎn)，必須有一個(gè)決策來(lái)決定哪個(gè)算子先用，哪個(gè)次之等等。只要有一個(gè)后繼產(chǎn)生，它

7、的下一個(gè)后繼就會(huì)被生成，一直向下傳下去。為了防止從開始節(jié)點(diǎn)的搜索深度太深，需要一個(gè)深度約束（depth bound）。超過(guò)這個(gè)深度約束時(shí)不再產(chǎn)生后繼（假定沒(méi)有任何目標(biāo)節(jié)點(diǎn)超過(guò)這個(gè)深度約束）。這種限制允許我們忽略搜索圖的一部分，這些部分已經(jīng)確定不能高效地到達(dá)目標(biāo)節(jié)點(diǎn)。8.4 深度優(yōu)先搜索深度優(yōu)先算法使我們只保存搜索樹的一部分，它由當(dāng)前正在搜索的路徑和指示該路徑上還沒(méi)有完全展開的節(jié)點(diǎn)標(biāo)志組成。因此，深度優(yōu)先搜索的存儲(chǔ)器要求是深度約束的線性函數(shù)。深度優(yōu)先搜索的一個(gè)缺點(diǎn)是當(dāng)發(fā)現(xiàn)目標(biāo)時(shí)，我們不能保證找到的路徑是最短長(zhǎng)度。另一個(gè)缺點(diǎn)是如果只有一個(gè)很淺的目標(biāo)，且該目標(biāo)位于搜索過(guò)程的后部時(shí)，也必須瀏覽大部分搜索空間。8.5 迭代加深一種叫做迭代加深（iterative deepening）的技術(shù)既能滿足深度優(yōu)先搜索的線性存儲(chǔ)要求，同時(shí)又能保證發(fā)現(xiàn)一個(gè)最小深度的目標(biāo)節(jié)點(diǎn)（如果一個(gè)目標(biāo)節(jié)點(diǎn)能被發(fā)現(xiàn)）。在迭代加深方法中，連續(xù)的深度優(yōu)先搜索被引入，每一個(gè)深度約束逐次加1