【正文】 人工智能 2023秋 狀態(tài)空間的盲目搜索 (5) 若節(jié)點 n不可擴(kuò)展，則轉(zhuǎn)第（ 2）步。 (6）擴(kuò)展節(jié)點 n，生成子節(jié)點 ni(I=1,2,…), 將這些子節(jié)點按邊代價由小到大放入 Open表的首部，并為每個子節(jié)點設(shè)置指向父節(jié)點指針。然后轉(zhuǎn)第（ 2）步。 例 城市交通問題。 66 人工智能 2023秋 狀態(tài)空間的啟發(fā)式搜索 啟發(fā)性信息和估價函數(shù) 啟發(fā)式搜索方法所依據(jù)的是問題自身的啟發(fā)性信息，啟發(fā)性信息又是通過估價函數(shù)作用到搜索過程中。 啟發(fā)性信息是至于具體問題求解過程無關(guān)的，并可指導(dǎo)搜索過程朝著最有希望方向前進(jìn)的控制信息。 67 人工智能 2023秋 狀態(tài)空間的啟發(fā)式搜索 啟發(fā)性信息一般有三種 : (1)有效地幫助確定擴(kuò)展節(jié)點的信息。 (2)有效地幫助決定哪些后繼節(jié)點應(yīng)被生成的信息。 (3)能決定在擴(kuò)展一個節(jié)點時哪些節(jié)點應(yīng)從搜索樹上刪除的信息。 搜索過程的啟發(fā)性信息的啟發(fā)能力越強(qiáng)，擴(kuò)展的無用節(jié)點就越少。 68 人工智能 2023秋 狀態(tài)空間的啟發(fā)式搜索 用來估計節(jié)點重要性的函數(shù)稱為估價函數(shù)。 估價函數(shù) f(n)被定義為從初始節(jié)點 S0出發(fā)到，約束經(jīng)過節(jié)點 n到達(dá)目標(biāo)節(jié)點 Sg的所有路徑中最小路徑代價的估計值。其一般形式為： F(n)=g(n)+h(n) 其中： g(n)是從初始節(jié)點 S0到節(jié)點 n的實際代價； h(n)是從節(jié)點 n到目標(biāo)節(jié)點 Sg的最優(yōu)路徑的估計代價。 69 人工智能 2023秋 狀態(tài)空間的啟發(fā)式搜索 例 八數(shù)碼難題 P183 A算法 在圖搜索算法中，如果能在搜索的每一步都利用估價函數(shù) F(n)=g(n)+h(n)對 Open表中的節(jié)點進(jìn)行排序，則該搜索算法為 A算法，由于估價函數(shù)中帶有自身的啟發(fā)性信息， A算法又稱為啟發(fā)式搜索算法。 70 人工智能 2023秋 狀態(tài)空間的啟發(fā)式搜索 在全局擇優(yōu)搜索中，每當(dāng)需要擴(kuò)展節(jié)點時總是從Open表的所有節(jié)點中選擇一個估計函數(shù)值最小的節(jié)點進(jìn)行擴(kuò)展，其搜索過程可描述如下： （ 1） 把初始節(jié)點 S0放入 Open表中，f(S0)=g(S0)+h(S0)。 （ 2）如果 Open表為空，則問題無解，失敗退出。 71 人工智能 2023秋 狀態(tài)空間的啟發(fā)式搜索 （ 3）把 Open表的第一個節(jié)點取出放入 Closed表，并記該節(jié)點為節(jié)點 n。 （ 4） 考察節(jié)點 n是否為目標(biāo)節(jié)點。若是則得到了問題的解，成功退出； (5) 若節(jié)點 n不可擴(kuò)展 ， 則轉(zhuǎn)第（ 2）步。 (6）擴(kuò)展節(jié)點 n， 生成子節(jié)點 ni(i=1,2,…), 計算每一個子節(jié)點的估價值 f(ni)(I=1,2,…), 并為每個子節(jié)點設(shè)置指向父節(jié)點指針。然后將這些子節(jié)點放入 Open表中。 72 人工智能 2023秋 狀態(tài)空間的啟發(fā)式搜索 （ 7）根據(jù)各節(jié)點的估價函數(shù)值，對 Open表中的全部節(jié)點按從小到大的順序重新進(jìn)行排序。 （ 8）轉(zhuǎn)第（ 2）步。 如果估價函數(shù) F(n)=g(n),則退化為代價樹的廣度優(yōu)先搜索； 如果估價函數(shù) F(n)=d(n),則退化為廣度優(yōu)先搜索； 可見，廣度優(yōu)先搜索和代價樹的廣度優(yōu)先搜索是全局擇優(yōu)搜索的兩個特例。 例 八數(shù)碼難題 P184 73 人工智能 2023秋 狀態(tài)空間的啟發(fā)式搜索 在局部擇優(yōu)搜索中，每當(dāng)需要擴(kuò)展節(jié)點時總是從剛生成的子節(jié)點中選擇一個估價函數(shù)值最小的節(jié)點進(jìn)行擴(kuò)展。其搜索過程可描述如下： （ 1） 把初始節(jié)點 S0放入 Open表中，f(S0)=g(S0)+h(S0)。 （ 2）如果 Open表為空，則問題無解，失敗退出。 74 人工智能 2023秋 狀態(tài)空間的啟發(fā)式搜索 （ 3）把 Open表的第一個節(jié)點取出放入 Closed表，并記該節(jié)點為節(jié)點 n。 （ 4） 考察節(jié)點 n是否為目標(biāo)節(jié)點。若是則得到了問題的解，成功退出； (5) 若節(jié)點 n不可擴(kuò)展 ， 則轉(zhuǎn)第（ 2）步。 (6）擴(kuò)展節(jié)點 n， 生成子節(jié)點 ni(i=1,2,…), 計算每一個子節(jié)點的估價值 f(ni)(i=1,2,…), 并按股價值從小到大的順序依次放入 Open表的首部，并為每個子節(jié)點設(shè)置指向父節(jié)點指針。然后轉(zhuǎn) (2)步。 75 人工智能 2023秋 狀態(tài)空間的啟發(fā)式搜索 可見，深度優(yōu)先搜索和代價樹的深度優(yōu)先搜索是局部擇優(yōu)搜索的兩個特例。 A*算法 在啟發(fā)式搜索中沒有對估價函數(shù) f(n)做任何限制。實際上，估價函數(shù)對搜索過程是十分重要的，如果選擇不當(dāng)，則有可能找不到問題的界，為此，需要對估價函數(shù)進(jìn)行適當(dāng)?shù)南拗啤?A*算嘎就是對估價寒暑加上一些先之后的到的一種啟發(fā)式搜索算法。 76 人工智能 2023秋 狀態(tài)空間的啟發(fā)式搜索 *算法的可納性 *算法的最優(yōu)性 (n)的單調(diào)限制 A*算法應(yīng)用舉例 例 八樹碼難題 P190 例 修道士和野人問題 P190 77 人工智能 2023秋 與 /或樹的盲目搜索 與 /或樹的一般搜索 與 /或樹的搜索過程實際上是一個不斷搜索尋找解樹的過程，其一般搜索過程為： （ 1） （ 2） （ 3) （ 4） 見書 P191 78 人工智能 2023秋 與 /或樹的盲目搜索 與 /或樹的廣度優(yōu)先搜索 P192 與 /或樹的深度優(yōu)先搜索 P193 79 人工智能 2023秋 與 /或樹的啟發(fā)式搜索 解樹的代價與希望樹 與或樹的啟發(fā)式搜索過程 80 人工智能 2023秋 博奕樹的啟發(fā)式搜索 概述 極大極小過程 81 人工智能 2023秋 本章小結(jié)： 82 人工智能 2023秋 謝謝！ 83 人工智能 2023秋 演講完畢，謝謝觀看！