人工智能及應用

1、人工智能及應用人工智能及應用第一頁，共24頁。啟發(fā)式搜索啟發(fā)式搜索l前面討論的搜索策略中沒有考慮問題本身的特前面討論的搜索策略中沒有考慮問題本身的特性信息，而只是按事先規(guī)定的路線進行搜索。性信息，而只是按事先規(guī)定的路線進行搜索。l如果在搜索過程中使用在搜索過程中獲得的問如果在搜索過程中使用在搜索過程中獲得的問題自身的一些特性信息來指導搜索顯然會有利題自身的一些特性信息來指導搜索顯然會有利于搜索。我們將利用問題自身特性信息來引導于搜索。我們將利用問題自身特性信息來引導搜索過程的搜索方法稱為啟發(fā)式搜索。搜索過程的搜索方法稱為啟發(fā)式搜索。第二頁，共24頁。啟發(fā)性信息的作用啟發(fā)性信息的作用l啟發(fā)性信息

2、對搜索的指導作用可歸納為啟發(fā)性信息對搜索的指導作用可歸納為3個方個方面。面。選擇下一個要被擴展的結(jié)點。選擇下一個要被擴展的結(jié)點。在結(jié)點擴展時，選擇有用的結(jié)點。在結(jié)點擴展時，選擇有用的結(jié)點。修剪掉某些不可能導致搜索成功的結(jié)點。修剪掉某些不可能導致搜索成功的結(jié)點。第三頁，共24頁。估價函數(shù)估價函數(shù)l啟發(fā)信息在搜索過程中的主要作用是對結(jié)點的啟發(fā)信息在搜索過程中的主要作用是對結(jié)點的重要性進行評估，通過這個評估來實現(xiàn)重要性進行評估，通過這個評估來實現(xiàn)OPEN表中結(jié)點的排序表中結(jié)點的排序l這個評估一般是通過估價函數(shù)實現(xiàn)的。這個評估一般是通過估價函數(shù)實現(xiàn)的。第四頁，共24頁。估價函數(shù)估價函數(shù)l估價函數(shù)估價函

3、數(shù)f(n)的一般形式為：的一般形式為：f(n)=g(n)+h(n)其中：其中：結(jié)點結(jié)點n是搜索圖中當前被擴展的結(jié)點。是搜索圖中當前被擴展的結(jié)點。f(n)是從初始狀態(tài)經(jīng)由結(jié)點是從初始狀態(tài)經(jīng)由結(jié)點n到達目標結(jié)點的所有到達目標結(jié)點的所有路徑中最小路徑代價的估計值。路徑中最小路徑代價的估計值。g(n)是從初始結(jié)點到結(jié)點是從初始結(jié)點到結(jié)點n的實際代價。的實際代價。h(n)是從結(jié)點是從結(jié)點n到達目標結(jié)點的最優(yōu)路徑的估計代到達目標結(jié)點的最優(yōu)路徑的估計代價。價。第五頁，共24頁。估價函數(shù)示例估價函數(shù)示例l例：八數(shù)碼問題。設初始狀態(tài)和目標狀態(tài)如下例：八數(shù)碼問題。設初始狀態(tài)和目標狀態(tài)如下圖，且估價函數(shù)為：圖，且估

4、價函數(shù)為：f(n)=d(n)+w(n) 其中：其中：d(n)表示結(jié)點的結(jié)點深度；表示結(jié)點的結(jié)點深度；w(n)表示表示結(jié)點結(jié)點n不在位的數(shù)碼個數(shù)。請計算初始狀態(tài)的不在位的數(shù)碼個數(shù)。請計算初始狀態(tài)的估價函數(shù)值。估價函數(shù)值。2 31 8 47 6 52 38 47 6 5S S0 0S Sg g第六頁，共24頁。估價函數(shù)示例估價函數(shù)示例解：此例估價函數(shù)中有解：此例估價函數(shù)中有 g(n)=d(n)-路徑的深度代表實際代價；路徑的深度代表實際代價； h(n)=w(n)-不在位數(shù)碼說明結(jié)點與目標的差不在位數(shù)碼說明結(jié)點與目標的差距。距。 f(S S0 0)=d(S S0 0)+w(S S0 0)=0+4=4

5、 第七頁，共24頁。A算法算法l在一般圖搜索算法中，如果每一步都利用估價在一般圖搜索算法中，如果每一步都利用估價函數(shù)函數(shù)f(n)=g(n)+h(n)對對OPEN表中的結(jié)點進行表中的結(jié)點進行排序，則稱該搜索算法為排序，則稱該搜索算法為A算法。算法。l由于估價函數(shù)帶有問題自身的啟發(fā)性信息，所由于估價函數(shù)帶有問題自身的啟發(fā)性信息，所以以A算法也是啟發(fā)式搜索算法。算法也是啟發(fā)式搜索算法。第八頁，共24頁。A算法算法-全局擇優(yōu)搜索全局擇優(yōu)搜索l產(chǎn)生一個僅有初始結(jié)點產(chǎn)生一個僅有初始結(jié)點S S0 0的的OPENOPEN表，建立表，建立一個一個僅有初始結(jié)點僅有初始結(jié)點S S0 0的圖的圖G G, ,置置S S

6、0 0的估價函數(shù)的估價函數(shù)f(Sf(S0 0)=g(S)=g(S0 0)+h(S)+h(S0 0) )；l產(chǎn)生一個空的產(chǎn)生一個空的CLOSEDCLOSED表；表；l如果如果OPENOPEN表為空，則失敗退出；表為空，則失敗退出；l在在OPENOPEN表的首部取一個結(jié)點表的首部取一個結(jié)點n n，將其放入，將其放入CLOSEDCLOSED表，在表，在OPENOPEN表刪除結(jié)點表刪除結(jié)點n n；第九頁，共24頁。A算法算法-全局擇優(yōu)搜索全局擇優(yōu)搜索l考察結(jié)點考察結(jié)點n n是否為目標結(jié)點，若是，則得到問是否為目標結(jié)點，若是，則得到問題的解，成功退出；題的解，成功退出；l若結(jié)點不可擴展，則轉(zhuǎn)第若結(jié)點不可

7、擴展，則轉(zhuǎn)第3 3步；步；l擴展結(jié)點擴展結(jié)點n n，計算子結(jié)點的，計算子結(jié)點的f(ni), f(ni), 并為每一并為每一個子結(jié)點指定父結(jié)點個子結(jié)點指定父結(jié)點, ,將子結(jié)點放入將子結(jié)點放入OPENOPEN表表中；中；l按估價函數(shù)為按估價函數(shù)為OPENOPEN表中的結(jié)點排序，轉(zhuǎn)第表中的結(jié)點排序，轉(zhuǎn)第3 3步。步。第十頁，共24頁。A算法算法-全局擇優(yōu)搜索全局擇優(yōu)搜索l例：八數(shù)碼問題。設初始狀態(tài)和目標狀態(tài)如下例：八數(shù)碼問題。設初始狀態(tài)和目標狀態(tài)如下圖，且估價函數(shù)為：圖，且估價函數(shù)為： f(n)=d(n)+w(n) 其中：其中：d(n)表示結(jié)點的結(jié)點深度；表示結(jié)點的結(jié)點深度；w(n)表示表示結(jié)點結(jié)點

8、n不在位的數(shù)碼個數(shù)。請使用全局擇優(yōu)搜不在位的數(shù)碼個數(shù)。請使用全局擇優(yōu)搜索求解問題。索求解問題。2 31 8 47 6 52 38 47 6 5S S0 0S Sg g第十一頁，共24頁。A算法算法-全局擇優(yōu)搜索全局擇優(yōu)搜索解：搜索圖為 2 31 8 47 6 52 31 8 47 6 52 8 31 47 6 52 3 1 8 47 6 51 2 3 8 47 6 52 8 3 1 47 6 52 8 31 4 7 6 52 8 31 6 47 51 2 38 47 6 5S S0 0S Sg gS S1 1S S2 2S S3 3S S4 4S S5 5S S6 6S S7 7S S8 84

9、44646771 2 37 8 4 6 563第十二頁，共24頁。A算法算法-局部擇優(yōu)搜索局部擇優(yōu)搜索l產(chǎn)生一個僅有初始結(jié)點產(chǎn)生一個僅有初始結(jié)點S S0 0的的OPENOPEN表，建立表，建立一個一個僅有初始結(jié)點僅有初始結(jié)點S S0 0的圖的圖G G, ,置置S S0 0的估價函數(shù)的估價函數(shù)f(Sf(S0 0)=g(S)=g(S0 0)+h(S)+h(S0 0) )；l產(chǎn)生一個空的產(chǎn)生一個空的CLOSEDCLOSED表；表；l如果如果OPENOPEN表為空，則失敗退出；表為空，則失敗退出；l在在OPENOPEN表的首部取一個結(jié)點表的首部取一個結(jié)點n n，將其放入，將其放入CLOSEDCLOSE

10、D表，在表，在OPENOPEN表刪除結(jié)點表刪除結(jié)點n n；第十三頁，共24頁。A算法算法-局部擇優(yōu)搜索局部擇優(yōu)搜索l考察結(jié)點考察結(jié)點n n是否為目標結(jié)點，若是，則得到問是否為目標結(jié)點，若是，則得到問題的解，成功退出；題的解，成功退出；l若結(jié)點不可擴展，則轉(zhuǎn)第若結(jié)點不可擴展，則轉(zhuǎn)第3 3步；步；l擴展結(jié)點擴展結(jié)點n n，計算子結(jié)點的，計算子結(jié)點的f(ni), f(ni), 并為每一并為每一個子結(jié)點指定父結(jié)點個子結(jié)點指定父結(jié)點, , 按估價函數(shù)將子結(jié)點按估價函數(shù)將子結(jié)點排序，并放入排序，并放入OPENOPEN表的首部，轉(zhuǎn)第表的首部，轉(zhuǎn)第3 3步。步。第十四頁，共24頁。關于關于A算法算法l全局擇優(yōu)

11、搜索：當全局擇優(yōu)搜索：當f(n)=g(n)，算法退化為代，算法退化為代價樹廣度優(yōu)先搜索；價樹廣度優(yōu)先搜索；f(n)=d(n)，算法退化為，算法退化為廣度優(yōu)先搜索。廣度優(yōu)先搜索。l局部擇優(yōu)搜索：當局部擇優(yōu)搜索：當f(n)=g(n)，算法退化為代，算法退化為代價樹深度優(yōu)先搜索；價樹深度優(yōu)先搜索；f(n)=d(n)，算法退化為，算法退化為深度優(yōu)先搜索。深度優(yōu)先搜索。第十五頁，共24頁。A*算法算法設設f*(n)是從初始狀態(tài)經(jīng)由結(jié)點是從初始狀態(tài)經(jīng)由結(jié)點n到達目標結(jié)點到達目標結(jié)點的所有路徑中最小路徑代價值，的所有路徑中最小路徑代價值，f(n)是它的估是它的估計值。則計值。則f*(n)應由兩部分組成：應由

12、兩部分組成：g g(n)是從初始結(jié)點到結(jié)點是從初始結(jié)點到結(jié)點n的最小代價。的最小代價。h(n)是從結(jié)點是從結(jié)點n到達目標結(jié)點的最優(yōu)路徑的代價到達目標結(jié)點的最優(yōu)路徑的代價值，有多個目標結(jié)點時取其代價最小者。值，有多個目標結(jié)點時取其代價最小者。 所以所以 f*(n)= g g(n)+ h(n)第十六頁，共24頁。A*算法算法對對A算法算法-全局擇優(yōu)搜索中的增加如下限制：全局擇優(yōu)搜索中的增加如下限制：lg(n)是對是對g*(n)的估計，并且的估計，并且g(n)0lh(n)是是h*(n)的下界，即對任意結(jié)點都有的下界，即對任意結(jié)點都有h(n)h1(n)則被則被A2*擴展的結(jié)點一定被擴展的結(jié)點一定被A1

13、*擴展。擴展。第十九頁，共24頁。A*算法的最優(yōu)性算法的最優(yōu)性如果啟發(fā)函數(shù)滿足以下兩個條件：如果啟發(fā)函數(shù)滿足以下兩個條件：lh(目標結(jié)點目標結(jié)點)=0l對任意結(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)限制。第二十頁，共24頁。A*算法的最優(yōu)性算法的最優(yōu)性結(jié)論：如果結(jié)論：如果h滿足單調(diào)條件，則當滿足單調(diào)條件，則當A*算法擴展結(jié)算法擴展結(jié)點點n時，該結(jié)點就已經(jīng)找到通往它的最佳路徑，時，該結(jié)點就已經(jīng)找到通往它的最佳路徑，即即g(n)=g*(n)第二十一頁，共24頁。A*算法算法-示例示例l例：八數(shù)碼問題。設初始狀態(tài)和目標狀態(tài)如下圖，例：八數(shù)碼問題。設初始狀態(tài)和目標狀態(tài)如下圖，且估價函數(shù)為：且估價函數(shù)為： f(n)=d(n)+w(n) 其中：其中：d(n)表示結(jié)點的結(jié)點深度；表示結(jié)點的結(jié)點深度；w(n)表示結(jié)點表示結(jié)點n不不在位的數(shù)碼個數(shù)。請使用在位的數(shù)碼個數(shù)。請使用A*算法求解問題。算法求解問題。2 31 8 47 6 52 38 47 6 5S S0 0S Sg g第二十二頁，共24頁。A*算法算法-示