人工智能及應(yīng)用

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

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

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

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

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

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

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

8、n不在位的數(shù)碼個(gè)數(shù)。請(qǐng)使用全局擇優(yōu)搜不在位的數(shù)碼個(gè)數(shù)。請(qǐng)使用全局擇優(yōu)搜索求解問(wèn)題。索求解問(wèn)題。2 31 8 47 6 52 38 47 6 5S S0 0S Sg g第十一頁(yè)，共24頁(yè)。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第十二頁(yè)，共24頁(yè)。A算法算法-局部擇優(yōu)搜索局部擇優(yōu)搜索l產(chǎn)生一個(gè)僅有初始結(jié)點(diǎn)產(chǎn)生一個(gè)僅有初始結(jié)點(diǎn)S S0 0的的OPENOPEN表，建立表，建立一個(gè)一個(gè)僅有初始結(jié)點(diǎn)僅有初始結(jié)點(diǎn)S S0 0的圖的圖G G, ,置置S S0 0的估價(jià)函數(shù)的估價(jià)函數(shù)f(Sf(S0 0)=g(S)=g(S0 0)+h(S)+h(S0 0) )；l產(chǎn)生一個(gè)空的產(chǎn)生一個(gè)空的CLOSEDCLOSED表；表；l如果如果OPENOPEN表為空，則失敗退出；表為空，則失敗退出；l在在OPENOPEN表的首部取一個(gè)結(jié)點(diǎn)表的首部取一個(gè)結(jié)點(diǎn)n n，將其放入，將其放入CLOSEDCLOSE

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

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

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

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