人工智能導(dǎo)論-第三章02-2014

1、第三章第三章 確定性推理確定性推理 3.1 推理概述推理概述 3.2 自然演繹推理自然演繹推理 3.3 消解原理消解原理 3.4 圖搜索概述圖搜索概述 3.5 盲目搜索盲目搜索 3.6 啟發(fā)式搜索啟發(fā)式搜索2021-11-2人工智能導(dǎo)論 - 劉珊1搜索搜索 定義定義 依靠經(jīng)驗，利用已有知識，根據(jù)問題的實際情依靠經(jīng)驗，利用已有知識，根據(jù)問題的實際情況，不斷尋找可利用知識，從而構(gòu)造一條代價況，不斷尋找可利用知識，從而構(gòu)造一條代價最小的推理路線，使問題得以解決的最小的推理路線，使問題得以解決的過程稱為過程稱為搜索。搜索。 類型類型 盲目搜索盲目搜索：按預(yù)定的控制策略進行搜索，在搜：按預(yù)定的控制策略進

2、行搜索，在搜索過程中獲得的中間信息并不改變控制策略。索過程中獲得的中間信息并不改變控制策略。 啟發(fā)式搜索啟發(fā)式搜索：在搜索中加入了與問題有關(guān)的啟：在搜索中加入了與問題有關(guān)的啟發(fā)性信息，用于指導(dǎo)搜索朝著最有希望的方向發(fā)性信息，用于指導(dǎo)搜索朝著最有希望的方向前進，加速問題的求解過程并找到最優(yōu)解。前進，加速問題的求解過程并找到最優(yōu)解。 2021-11-2人工智能導(dǎo)論 - 劉珊23.4 圖搜索概述圖圖 一一種種限制限制最少最少的的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)。 顯式顯式圖圖 頂點或頂點或節(jié)節(jié)點、邊、環(huán)點、邊、環(huán) 有限圖、簡單圖、帶權(quán)圖、連通圖、網(wǎng)絡(luò)有限圖、簡單圖、帶權(quán)圖、連通圖、網(wǎng)絡(luò) 隱式隱式圖圖 子集子集樹、

3、排列樹樹、排列樹 圖的存儲圖的存儲 鄰接矩陣：鄰接矩陣：表示頂點之間相鄰關(guān)系的矩陣表示頂點之間相鄰關(guān)系的矩陣 鄰接表：鄰接表：由邊表和由邊表和頂點表兩頂點表兩部分組成部分組成2021-11-2人工智能導(dǎo)論 - 劉珊33.4 圖搜索概述圖搜索圖搜索 窮舉搜索窮舉搜索 啟發(fā)式搜索啟發(fā)式搜索 術(shù)語術(shù)語 問題狀態(tài)、狀態(tài)空間問題狀態(tài)、狀態(tài)空間 解狀態(tài)：一些問題解狀態(tài)：一些問題狀態(tài)狀態(tài) 答案答案狀態(tài)：狀態(tài)：一些解狀態(tài)一些解狀態(tài) 狀態(tài)空間狀態(tài)空間樹：樹：解空間的樹結(jié)構(gòu)解空間的樹結(jié)構(gòu) 活節(jié)點、活節(jié)點、E-節(jié)點、死節(jié)點節(jié)點、死節(jié)點 節(jié)節(jié)點深度點深度 路徑、路徑代價路徑、路徑代價 節(jié)點節(jié)點擴展擴展2021-11-

4、2人工智能導(dǎo)論 - 劉珊43.4 圖搜索概述開始把S0放入OPEN表OPEN表為空表？把OPEN表中第一個節(jié)點(n)移至CLOSED表n為目標(biāo)節(jié)點嗎？擴展n，把其后繼節(jié)點放入OPEN表的末端，提供返回節(jié)點n的指針修改指針方向重排OPEN表失敗成功圖搜索過程框圖是是否否2021-11-2人工智能導(dǎo)論 - 劉珊5S S0 0n nmmp pPath1Path2提高效率提高效率的關(guān)鍵的關(guān)鍵3.4 圖搜索概述圖搜索圖搜索2021-11-2人工智能導(dǎo)論 - 劉珊6狀態(tài)節(jié)點狀態(tài)節(jié)點 父節(jié)點父節(jié)點OPEN表表：存放：存放剛生成的節(jié)剛生成的節(jié)點，點，也也稱為未擴展節(jié)點表。稱為未擴展節(jié)點表。OPEN表的一般形式

5、表的一般形式如右圖：如右圖：CLOSED表表：存放：存放已經(jīng)擴已經(jīng)擴展或?qū)⒁獢U展的節(jié)點。展或?qū)⒁獢U展的節(jié)點。 CLOSED表的一般形式表的一般形式如如右圖右圖：編號編號狀態(tài)節(jié)點狀態(tài)節(jié)點父節(jié)點父節(jié)點3.4 圖搜索概述第三章第三章 確定性推理確定性推理 3.1 推理概述推理概述 3.2 自然演繹推理自然演繹推理 3.3 消解原理消解原理 3.4 圖搜索概述圖搜索概述 3.5 盲目搜索盲目搜索 3.6 啟發(fā)式搜索啟發(fā)式搜索2021-11-2人工智能導(dǎo)論 - 劉珊7盲目搜索盲目搜索 特點：不需重排特點：不需重排OPENOPEN表表 狀態(tài)空間的盲目搜索狀態(tài)空間的盲目搜索 與或圖的盲目搜索與或圖的盲目搜索

6、 類型類型 寬度優(yōu)先搜索（廣度優(yōu)先搜索）寬度優(yōu)先搜索（廣度優(yōu)先搜索） 深度優(yōu)先搜索深度優(yōu)先搜索 等等代價代價搜索搜索2021-11-2人工智能導(dǎo)論 - 劉珊83.5 盲目搜索狀態(tài)空間的寬度優(yōu)先搜索狀態(tài)空間的寬度優(yōu)先搜索 定義定義 以接近起始節(jié)點的程度逐層擴展節(jié)點的搜索方以接近起始節(jié)點的程度逐層擴展節(jié)點的搜索方法法 基本基本思想思想 從初始節(jié)點從初始節(jié)點S0開始逐層向下擴展，在第開始逐層向下擴展，在第n層節(jié)層節(jié)點還沒有全部搜索完之前，不進入第點還沒有全部搜索完之前，不進入第n+1層節(jié)層節(jié)點的搜索點的搜索。 Open表中的節(jié)點總是按進入的先后表中的節(jié)點總是按進入的先后排序。排序。 特點特點 一種高

7、代價搜索，但若有解存在一種高代價搜索，但若有解存在，必，必能能找到找到2021-11-2人工智能導(dǎo)論 - 劉珊93.5 盲目搜索開始開始把把S0放放入入OPEN表表OPEN表為空表？表為空表？把第一個節(jié)點把第一個節(jié)點(n)從從OPEN表移至表移至CLOSED表表是否有后繼節(jié)點是否有后繼節(jié)點為為目標(biāo)節(jié)點？目標(biāo)節(jié)點？擴展擴展n，把，把n的后繼節(jié)點放入的后繼節(jié)點放入OPEN表的末端，提供返回節(jié)點表的末端，提供返回節(jié)點n的指針的指針失敗失敗成功成功寬度優(yōu)先算法框圖是是否否是是否否2021-11-2人工智能導(dǎo)論 - 劉珊103.5 盲目搜索八數(shù)碼難題八數(shù)碼難題2021-11-2人工智能導(dǎo)論 - 劉珊11

8、1238456712384567（目標(biāo)狀態(tài)）（目標(biāo)狀態(tài)）（初始狀態(tài)）（初始狀態(tài)）可以可以使用的使用的操作：空格操作：空格左移，空格上移，空格右左移，空格上移，空格右移，空格下移，空格下移。移。要求要求應(yīng)用寬度優(yōu)先搜索應(yīng)用寬度優(yōu)先搜索策略尋找從初始狀態(tài)到目策略尋找從初始狀態(tài)到目標(biāo)狀態(tài)的解標(biāo)狀態(tài)的解路徑。路徑。3.5 盲目搜索123845671123845671238456712384567123845672345八八數(shù)碼難題數(shù)碼難題的的寬度優(yōu)先搜索寬度優(yōu)先搜索樹樹13456123845671238456712384567123845671 2384567232425262712367822123

9、84567123845671 238456712 3845671238456712384567123845671415161718192021123845672021-11-2人工智能導(dǎo)論 - 劉珊1212384123845674123856712 3841238456712384567123845676789101112131238456756756743.5 盲目搜索狀態(tài)空間的深度優(yōu)先搜索狀態(tài)空間的深度優(yōu)先搜索 定義定義 首先擴展最新產(chǎn)生的首先擴展最新產(chǎn)生的(即最深的即最深的)節(jié)點。節(jié)點。 基本思想基本思想 從從初始節(jié)點初始節(jié)點S0開始，選擇最新產(chǎn)生開始，選擇最新產(chǎn)生的節(jié)點的節(jié)點考察考察擴

10、展，直到找到擴展，直到找到目標(biāo)節(jié)點目標(biāo)節(jié)點為止為止。 OPEN表表中總是中總是將新產(chǎn)生將新產(chǎn)生的節(jié)點放在的節(jié)點放在OPEN表的表的前端。前端。2021-11-2人工智能導(dǎo)論 - 劉珊133.5 盲目搜索八數(shù)碼難題八數(shù)碼難題2021-11-2人工智能導(dǎo)論 - 劉珊141238456712384567（目標(biāo)狀態(tài)）（目標(biāo)狀態(tài)）（初始狀態(tài)）（初始狀態(tài)）可以可以使用的使用的操作：空格操作：空格左移，空格上移，空格右左移，空格上移，空格右移，空格下移，空格下移。移。要求要求應(yīng)用深度優(yōu)先搜索應(yīng)用深度優(yōu)先搜索策略尋找從初始狀態(tài)到目策略尋找從初始狀態(tài)到目標(biāo)狀態(tài)的解標(biāo)狀態(tài)的解路徑。路徑。3.5 盲目搜索12384

11、5671123845671238456712384567123845672345八八數(shù)碼難題數(shù)碼難題的的深深度優(yōu)先搜索度優(yōu)先搜索樹樹12384567123845672425123845671 2384567262713456123845672312367822123845671412384567151 2384567162021-11-2人工智能導(dǎo)論 - 劉珊151238412384567675674123856712 3848956743.5 盲目搜索狀態(tài)空間的深度優(yōu)先搜索狀態(tài)空間的深度優(yōu)先搜索 與寬度優(yōu)先搜索算法比較與寬度優(yōu)先搜索算法比較 步驟基本步驟基本相同相同 Open表中的節(jié)點排序表

12、中的節(jié)點排序不同不同 一種非完備一種非完備策略策略 深度深度限制限制 防止搜索過程沿著無益的路徑擴展下去防止搜索過程沿著無益的路徑擴展下去，給，給出出一個節(jié)點擴展的最大深度一個節(jié)點擴展的最大深度2021-11-2人工智能導(dǎo)論 - 劉珊163.5 盲目搜索狀態(tài)空間的等代價搜索狀態(tài)空間的等代價搜索 代價樹：代價樹：帶有代價邊的狀態(tài)空間帶有代價邊的狀態(tài)空間圖。圖。 定義定義 寬度優(yōu)先搜索的一種推廣寬度優(yōu)先搜索的一種推廣 用用g(n1)表示從表示從S0到節(jié)點到節(jié)點n1的的路徑路徑的代價，的代價，用用C(n1, n2)表示從表示從父節(jié)父節(jié)點點n1到到子節(jié)點子節(jié)點n2的代價，則從的代價，則從S0到節(jié)點到節(jié)

13、點n2的代價可以表示為：的代價可以表示為： g(n2)=g(n1)+ C(n1, n2)2021-11-2人工智能導(dǎo)論 - 劉珊17S S0 0n1 1n2 2C(n1 1, n2 2)g(n1 1)3.5 盲目搜索開始開始把把S0放放入入OPEN表表OPEN表為空表？表為空表？把具有最小把具有最小g(i)值的節(jié)點值的節(jié)點i從從OPEN表移至表移至CLOSED表表是否為是否為目標(biāo)節(jié)點？目標(biāo)節(jié)點？失敗失敗成功成功等代價搜索算法框圖是是否否是是否否令令g(s)=0S0是否是否目標(biāo)節(jié)點目標(biāo)節(jié)點？是是成功成功擴展擴展i，計算其后繼節(jié)點，計算其后繼節(jié)點j的的g(j)，按，按由小到由小到大大排序排序，放，

14、放入入OPEN表表否否2021-11-2人工智能導(dǎo)論 - 劉珊183.5 盲目搜索城市交通問題城市交通問題 設(shè)有設(shè)有5個城市，它們之間的交通線路個城市，它們之間的交通線路如下如下圖圖所示，圖中的數(shù)字表示兩個城市之間的所示，圖中的數(shù)字表示兩個城市之間的交通費用，即代價。交通費用，即代價。用等代價搜索用等代價搜索，求從，求從A市出發(fā)到市出發(fā)到E市，費用最小的交通路線。市，費用最小的交通路線。 2021-11-2人工智能導(dǎo)論 - 劉珊19ACDEB3424533.5 盲目搜索城市交通問題城市交通問題 解：將原網(wǎng)絡(luò)圖轉(zhuǎn)化為代價樹：解：將原網(wǎng)絡(luò)圖轉(zhuǎn)化為代價樹：2021-11-2人工智能導(dǎo)論 - 劉珊20

15、AC1 1B1 1D1 1D2 2E1 1E2 2B2 2C2 2E3 3E4 43424534235ACDEB3424533.5 盲目搜索與或圖搜索與或圖搜索2021-11-2人工智能導(dǎo)論 - 劉珊21 深度優(yōu)先搜索深度優(yōu)先搜索 窮舉窮舉式搜索式搜索 盲目搜索盲目搜索 寬度優(yōu)先搜索寬度優(yōu)先搜索 盲目盲目碰撞搜索碰撞搜索與或圖搜索與或圖搜索 啟發(fā)式搜索啟發(fā)式搜索3.5 盲目搜索與或圖與或圖 概念回顧概念回顧 終節(jié)點終節(jié)點 可解節(jié)點可解節(jié)點 不可解節(jié)點不可解節(jié)點 有關(guān)概念有關(guān)概念 K連接符連接符 耗散值耗散值 解圖解圖 最佳解圖最佳解圖 2021-11-2人工智能導(dǎo)論 - 劉珊22non1n2n

16、4n3n5n6n7n8初始節(jié)點初始節(jié)點目標(biāo)節(jié)點目標(biāo)節(jié)點目標(biāo)節(jié)點目標(biāo)節(jié)點3.5 盲目搜索耗散值耗散值 Ck為為k連接符的路徑耗散連接符的路徑耗散值，值，N為目標(biāo)為目標(biāo)節(jié)點節(jié)點集合，集合，n1 ,n2 ,.ni 為由為由k連接符連接符連接的連接的i個節(jié)點個節(jié)點， C(n, N)為為節(jié)點節(jié)點n到到N的的耗散值，則耗散值，則： C(n, N) = Ck+C(n1, N)+C(ni, N) 若若n屬于屬于N，C(n,N)=0 若若n是局部圖的一個葉節(jié)點是局部圖的一個葉節(jié)點,則則C(n,N)=h(n) 根節(jié)點的耗散值為解圖的耗散值根節(jié)點的耗散值為解圖的耗散值2021-11-2人工智能導(dǎo)論 - 劉珊23.i

17、個nn1n2ni3.5 盲目搜索耗散值耗散值 假設(shè)假設(shè)K連接符的耗散連接符的耗散值為值為K， N=n7, n8 計算計算C(n0,N)2021-11-2人工智能導(dǎo)論 - 劉珊24n0n4n7n8n5與或圖的盲目搜索與或圖的盲目搜索 常用的方法也是深度優(yōu)先常用的方法也是深度優(yōu)先和寬度和寬度優(yōu)先兩種優(yōu)先兩種基本基本策略策略 與或圖的一般搜索與或圖的一般搜索 從代表原始問題的根節(jié)點開始，按一定的規(guī)則從代表原始問題的根節(jié)點開始，按一定的規(guī)則(歸約操作歸約操作)對當(dāng)前節(jié)點進行對當(dāng)前節(jié)點進行與或與或擴展，并為每擴展，并為每個子節(jié)點設(shè)置指向父節(jié)點的指針；個子節(jié)點設(shè)置指向父節(jié)點的指針； 選擇選擇適當(dāng)適當(dāng)?shù)淖庸?jié)

18、點進行的子節(jié)點進行擴展擴展，多次調(diào)用可解標(biāo)，多次調(diào)用可解標(biāo)記過程和不可解標(biāo)記過程，直到根節(jié)點被標(biāo)記記過程和不可解標(biāo)記過程，直到根節(jié)點被標(biāo)記為可接或不可解節(jié)點為止。為可接或不可解節(jié)點為止。2021-11-2人工智能導(dǎo)論 - 劉珊253.5 盲目搜索與或圖的寬度優(yōu)先搜索與或圖的寬度優(yōu)先搜索2021-11-2人工智能導(dǎo)論 - 劉珊263.5 盲目搜索實例實例 下圖所示的與或圖中，節(jié)點按標(biāo)注順序下圖所示的與或圖中，節(jié)點按標(biāo)注順序進行擴展，其中進行擴展，其中t1、t2、t3是是終止終止節(jié)點，節(jié)點， A、B、C為不可解的端節(jié)為不可解的端節(jié)點。點。2021-11-2人工智能導(dǎo)論 - 劉珊2715423t2t

19、3t1BCA3.5 盲目搜索與或圖與或圖的深度優(yōu)先搜索的深度優(yōu)先搜索2021-11-2人工智能導(dǎo)論 - 劉珊283.5 盲目搜索第三章第三章 確定性推理確定性推理 3.1 推理概述推理概述 3.2 自然演繹推理自然演繹推理 3.3 消解原理消解原理 3.4 圖搜索概述圖搜索概述 3.5 盲目搜索盲目搜索 3.6 啟發(fā)式搜索啟發(fā)式搜索2021-11-2人工智能導(dǎo)論 - 劉珊29啟發(fā)式搜索啟發(fā)式搜索 特點特點 重排重排OPEN表，選擇最有希望的節(jié)點加以擴展表，選擇最有希望的節(jié)點加以擴展 類型類型 A算法、算法、A*算法算法等等 啟發(fā)式信息啟發(fā)式信息 用來加速搜索過程的有關(guān)問題領(lǐng)域的特征信息用來加速

20、搜索過程的有關(guān)問題領(lǐng)域的特征信息 估價估價函數(shù)函數(shù) 用于評定用于評定侯選擴展侯選擴展節(jié)點節(jié)點 一般形式一般形式：f(n)=g(n)+h(n) 應(yīng)用估價應(yīng)用估價函數(shù)函數(shù)值重排值重排OPEN表表2021-11-2人工智能導(dǎo)論 - 劉珊30g(n)是從初始節(jié)點是從初始節(jié)點S0到節(jié)點到節(jié)點n的實際代價；的實際代價；h(n)是從節(jié)是從節(jié)點點n到目標(biāo)節(jié)點到目標(biāo)節(jié)點Sg的最優(yōu)路的最優(yōu)路徑的估計徑的估計代價代價。3.6 啟發(fā)式搜索A算法算法 搜索中，如果重排搜索中，如果重排OPENOPEN表是表是依據(jù)估計函依據(jù)估計函數(shù)數(shù)f(xf(x)=g(x)+h(x)=g(x)+h(x)進行的，則稱該過程為進行的，則稱該過

21、程為A A算法。算法。 全局擇優(yōu)搜索：擴展節(jié)點時，總是從全局擇優(yōu)搜索：擴展節(jié)點時，總是從OPENOPEN表的所有節(jié)點中選擇。表的所有節(jié)點中選擇。 局部擇優(yōu)搜索：擴展節(jié)點時，從剛生成的局部擇優(yōu)搜索：擴展節(jié)點時，從剛生成的節(jié)點中選擇。節(jié)點中選擇。2021-11-2人工智能導(dǎo)論 - 劉珊313.6 啟發(fā)式搜索A算法算法 實質(zhì)：選擇實質(zhì)：選擇OPEN表上具有最小表上具有最小f值的節(jié)點作為下一個值的節(jié)點作為下一個要擴展的節(jié)點要擴展的節(jié)點。2021-11-2人工智能導(dǎo)論 - 劉珊32全局擇優(yōu)搜索A算法框圖開始開始把把S S放入放入OPENOPEN表，計算估價函數(shù)表，計算估價函數(shù) f (s)f (s)OPE

22、NOPEN表為空表？表為空表？選取選取OPENOPEN表中表中f f值最小的節(jié)點值最小的節(jié)點i i放入放入CLOSEDCLOSED表表i i為目標(biāo)節(jié)點嗎？為目標(biāo)節(jié)點嗎？擴展擴展i i，得后繼節(jié)點，得后繼節(jié)點j j，計算，計算f(j)f(j)，提供返回節(jié)，提供返回節(jié)點點i i的指針，利用的指針，利用f(j)f(j)對對OPENOPEN表重新排序，調(diào)表重新排序，調(diào)整親子關(guān)系及指針整親子關(guān)系及指針失敗失敗成功成功是是否否是是否否3.6 啟發(fā)式搜索八數(shù)碼難題八數(shù)碼難題2021-11-2人工智能導(dǎo)論 - 劉珊331238456712384567（目標(biāo)狀態(tài)）（目標(biāo)狀態(tài)）（初始狀態(tài)）（初始狀態(tài)）假設(shè)估計函數(shù)

23、為假設(shè)估計函數(shù)為f(n)=d(n)+W(n)，d(n)表示節(jié)點表示節(jié)點n在搜索樹中的在搜索樹中的深度，深度，W(n)表示節(jié)點表示節(jié)點n中中“不在位不在位”的數(shù)碼的數(shù)碼個數(shù)。個數(shù)。3.6 啟發(fā)式搜索5714563123845671238456712384567（4）（6）（6）2123845671238456712384567（6）（5）（5）1238456712 384567（5）（7）1238456712384567（6）（7）12384567（5）813245671 2384567（5）（7）八數(shù)碼難題的有序搜索樹123846（4）72021-11-2人工智能導(dǎo)論 - 劉珊3453.6 啟

24、發(fā)式搜索估價函數(shù)估價函數(shù) 定義定義 定義定義f f* *(n)=g(n)=g* *(n)+h(n)+h* *(n)(n) , ,表示表示從初始狀態(tài)經(jīng)由從初始狀態(tài)經(jīng)由節(jié)點節(jié)點n n到達目標(biāo)節(jié)點的所有路徑中最小路徑代到達目標(biāo)節(jié)點的所有路徑中最小路徑代價值。價值。 g g* *( (n)n)是從是從初始初始節(jié)節(jié)點到節(jié)點點到節(jié)點n n的最小的最小代價代價 h h* *(n(n) )是是從節(jié)點從節(jié)點n n到達到達目標(biāo)節(jié)點目標(biāo)節(jié)點的最優(yōu)路徑的代的最優(yōu)路徑的代價值，有多個價值，有多個目標(biāo)節(jié)點目標(biāo)節(jié)點時取其代價最小者時取其代價最小者 f f* *( (n)n)的估價值定義的估價值定義為：為：f(n)=g(n)

25、+h(n) f(n)=g(n)+h(n) g g是是g g* *的估計的估計 ，h h是是h h* *的的估計估計2021-11-2人工智能導(dǎo)論 - 劉珊353.6 啟發(fā)式搜索幾個定義幾個定義 定義定義1 1：如果如果對所有的對所有的x x存在存在h(x)hh(x)h* *(x(x) )，則則稱稱h(x)h(x)為為h h* *(x)(x)的下界，它表示某種偏于的下界，它表示某種偏于保守的估計保守的估計。 定義定義2 2：采用采用h h* *(x)(x)的下界的下界h(x)h(x)為啟發(fā)為啟發(fā)函數(shù)函數(shù)的的A A算法（全局擇優(yōu)），算法（全局擇優(yōu)），稱為稱為A A* *算法算法。 可納性：如果搜索

26、算法能在有限步內(nèi)找到可納性：如果搜索算法能在有限步內(nèi)找到一條從一條從初始節(jié)點到目標(biāo)節(jié)點的初始節(jié)點到目標(biāo)節(jié)點的最佳路徑，最佳路徑，則稱該搜索算法是則稱該搜索算法是可采納的?？刹杉{的。 A A* *算法是可采納的。算法是可采納的。2021-11-2人工智能導(dǎo)論 - 劉珊363.6 啟發(fā)式搜索A*算法的最優(yōu)性算法的最優(yōu)性 設(shè)有兩個設(shè)有兩個A*算法算法A1*和和A2*，它們有，它們有 A1*: f1(n)=g1(n)+h1(n) A2*: f2(n)=g2(n)+h2(n) 如果對所有非如果對所有非目標(biāo)節(jié)點目標(biāo)節(jié)點均均有有 h2(n)h1(n)，則則被被A2*擴展擴展的節(jié)點的節(jié)點一定被一定被A1*擴展

27、。擴展。2021-11-2人工智能導(dǎo)論 - 劉珊373.6 啟發(fā)式搜索h(n)的單調(diào)限制的單調(diào)限制 如果啟發(fā)函數(shù)如果啟發(fā)函數(shù)滿足以下兩個條件：滿足以下兩個條件： h(目標(biāo)節(jié)點目標(biāo)節(jié)點)=0 對對任意節(jié)點任意節(jié)點n和它的和它的子節(jié)點子節(jié)點m，都，都有有 0h(n)-h(m) C(n,m)，C(n,m)是節(jié)點到是節(jié)點到其其子節(jié)點的子節(jié)點的邊邊代價代價 則則稱稱h(n)滿足單調(diào)限制滿足單調(diào)限制。 如果如果h(n)滿足單調(diào)限制，滿足單調(diào)限制，則當(dāng)則當(dāng)A*算法算法擴展節(jié)擴展節(jié)點點n時，時，該節(jié)點就該節(jié)點就已經(jīng)找到通往它的最佳已經(jīng)找到通往它的最佳路徑。路徑。 如果如果h(n)滿足單調(diào)限制，則滿足單調(diào)限制，

28、則A*算法擴展的節(jié)算法擴展的節(jié)點序列的點序列的f 值是非遞減的，即值是非遞減的，即f(ni)f(ni+1)2021-11-2人工智能導(dǎo)論 - 劉珊383.6 啟發(fā)式搜索八數(shù)碼難題八數(shù)碼難題2021-11-2人工智能導(dǎo)論 - 劉珊391238456712384567（目標(biāo)狀態(tài)）（目標(biāo)狀態(tài)）（初始狀態(tài)）（初始狀態(tài)）假設(shè)估計函數(shù)為假設(shè)估計函數(shù)為f(n)=d(n)+p(n)，d(n)表示節(jié)點表示節(jié)點n在搜索樹中的在搜索樹中的深度，深度，p(n)表示節(jié)點表示節(jié)點n中每個數(shù)碼中每個數(shù)碼與其目標(biāo)位置之間距離的總和。與其目標(biāo)位置之間距離的總和。3.6 啟發(fā)式搜索402512384567h*=4f = 4111

29、/2/2021人工智能導(dǎo)論123845671238456712384567f=6f=6g*=1h*=3f = 412384567f=631238456712 384567g*=2h*=2f=4f=612384567g*=3h*=1f=4813245671 2384567g*=4h*=0f=4f=64八數(shù)碼難題八數(shù)碼難題h(n)=P(n)的的A*算法算法搜索樹搜索樹3.6 啟發(fā)式搜索2021-11-2人工智能導(dǎo)論 - 劉珊與或圖的啟發(fā)式搜索與或圖的啟發(fā)式搜索 與或圖的啟發(fā)式搜索同樣依賴于評價函數(shù)，與或圖的啟發(fā)式搜索同樣依賴于評價函數(shù)，其形式一般定義為其形式一般定義為f(n)=g(n)+h(n)

30、與或圖的啟發(fā)式搜索同樣可以用與或圖的啟發(fā)式搜索同樣可以用open表和表和closed表實現(xiàn)，但是表實現(xiàn)，但是open表根據(jù)表根據(jù)K連接符的連接符的耗散值排序耗散值排序， closed表中多了一列表中多了一列“可解可解性性”判別。判別。2021-11-2人工智能導(dǎo)論 - 劉珊413.6 啟發(fā)式搜索AO* 算法算法 1、 把初始節(jié)點把初始節(jié)點S0放入放入OPEN表；表； 2、 移出移出OPEN表的耗散值最小的表的耗散值最小的K連接符對應(yīng)的節(jié)連接符對應(yīng)的節(jié)點點N放入放入CLOSED表，并冠以序號表，并冠以序號n； 3、 若若節(jié)點節(jié)點n可可擴展，則做下列工作：擴展，則做下列工作： 擴展擴展n:將其子節(jié)點配上指向父節(jié)點的指針后放入將其子節(jié)點配上指向父節(jié)點的指針后放入OPEN表；表； 可解性可解性判別：考察這些子節(jié)點中是否有終止節(jié)點。若判別：考察這些子節(jié)點中是否有終止節(jié)點。若有，則標(biāo)記它們?yōu)榭山夤?jié)點，并將它們放入有，則標(biāo)記它們?yōu)榭山夤?jié)點，并將它們放入CLOSED表，表，然后由它的可解返回推斷其先輩節(jié)點的可解性，并對然后由它的可解返回推斷其先輩節(jié)點的可解性，并對其中的可解節(jié)點進行標(biāo)記。如果初始節(jié)點其中的可解節(jié)點進行標(biāo)記。如果初始節(jié)點S0也被標(biāo)記也被