狀態(tài)空間搜索策略

狀態(tài)空間搜索策略第一頁(yè)，共五十一頁(yè)，編輯于2023年，星期三13.1搜索1搜索基本概念2搜索的一般過(guò)程第二頁(yè)，共五十一頁(yè)，編輯于2023年，星期三21.搜索從已知的事實(shí)出發(fā)（問(wèn)題的初始狀態(tài)）尋找可用的知識(shí)（搜索）一步一步推出最終結(jié)論（問(wèn)題的目標(biāo)狀態(tài)）

問(wèn)題求解搜索第三頁(yè)，共五十一頁(yè)，編輯于2023年，星期三3

2搜索的一般過(guò)程

OPEN：存放剛剛生成的節(jié)點(diǎn)CLOSED：存放將要擴(kuò)展和/或已經(jīng)擴(kuò)展的節(jié)點(diǎn)OPENCLOSED第四頁(yè)，共五十一頁(yè)，編輯于2023年，星期三41）把初始節(jié)點(diǎn)S0放入OPEN，并建立只包含S0的圖，記為G。2）檢查OPEN是否為空，是，無(wú)解，退出。3）把OPEN第一個(gè)節(jié)點(diǎn)取出放入CLOSED，并記為節(jié)點(diǎn)n。4）考察節(jié)點(diǎn)是否為目標(biāo)節(jié)點(diǎn)，是，得解，退出。5）擴(kuò)展節(jié)點(diǎn)n，生成一組子節(jié)點(diǎn)。把其中不是節(jié)點(diǎn)n先輩的那些子節(jié)點(diǎn)記為集合M，把這些子節(jié)點(diǎn)作為節(jié)點(diǎn)n的子節(jié)點(diǎn)加入G。第五頁(yè)，共五十一頁(yè)，編輯于2023年，星期三56）針對(duì)M中子節(jié)點(diǎn)的不同情況：(1)對(duì)于那些未曾在G中出現(xiàn)過(guò)的M成員設(shè)置一個(gè)指向父節(jié)點(diǎn)（即節(jié)點(diǎn)n）的指針，把它們放入OPEN。(2)對(duì)于那些先前曾在G中出現(xiàn)過(guò)的M成員，確定是否需要修改其指向父節(jié)點(diǎn)（即節(jié)點(diǎn)n）的指針(3)對(duì)于對(duì)那些先前曾在G中出現(xiàn)過(guò)的、并已經(jīng)擴(kuò)展了的M成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針7）按某種搜索策略對(duì)OPEN中的節(jié)點(diǎn)進(jìn)行排序。8）轉(zhuǎn)2）。第六頁(yè)，共五十一頁(yè)，編輯于2023年，星期三6TowerofHanoi問(wèn)題有編號(hào)為1、2、3的三個(gè)柱子和標(biāo)識(shí)為A、B的尺寸依次為小、大的有中心孔的圓盤；初始狀態(tài)下盤按A、B順序堆放在1號(hào)柱子上，目標(biāo)狀態(tài)下盤以同樣次序順序堆放在3號(hào)柱子上，盤子的搬移須遵守以下規(guī)則：每次只能搬一個(gè)盤子，且較大盤不能壓放在較小盤之上。123AB123AB第七頁(yè)，共五十一頁(yè)，編輯于2023年，星期三7狀態(tài)：以三元素組描述問(wèn)題狀態(tài)三個(gè)元素依次指示盤子A、B所在的柱子編號(hào)TowerofHanoi問(wèn)題狀態(tài)描述為：S=（1,1），G=（3,3）算子F：A(i,j)：把圓盤A從第i號(hào)柱子移到第j號(hào)柱子B(i,j)：把圓盤B從第i號(hào)柱子移到第j號(hào)柱子

狀態(tài)與算子第八頁(yè)，共五十一頁(yè)，編輯于2023年，星期三8全部可能的狀態(tài)：（1,1）（1,2）（1,3）（2,1）（2,2）（2,3）（3,1）（3,2）（3,3）（1,1）（1,2）（1,3）AB（2,1）（2,2）（2,3）（3,1）（2,3）（3,3）第九頁(yè)，共五十一頁(yè)，編輯于2023年，星期三9（1,1）（1,2）（1,3）AB（2,1）（2,2）（2,3）（3,1）（3,2）（3,3）求解路徑第十頁(yè)，共五十一頁(yè)，編輯于2023年，星期三10（1,1）AB（2,1）（2,3）（3,3）求解路徑第十一頁(yè)，共五十一頁(yè)，編輯于2023年，星期三1133212311A（2,3）B（1,3）A（1,2）二階TowerofHanoi塔狀態(tài)空間圖(局部)第十二頁(yè)，共五十一頁(yè)，編輯于2023年，星期三12

狀態(tài)空間可描述為一個(gè)有向圖節(jié)點(diǎn)指示狀態(tài)節(jié)點(diǎn)間的有向弧表示狀態(tài)變遷弧上的標(biāo)簽則指示導(dǎo)致狀態(tài)變遷的操作算子狀態(tài)用于記載問(wèn)題求解（即搜索）過(guò)程中某一時(shí)刻問(wèn)題現(xiàn)狀狀態(tài)空間圖33212311A（2,3）B（1,3）A（1,2）第十三頁(yè)，共五十一頁(yè)，編輯于2023年，星期三13搜索圖與搜索樹33212311A（2,3）B（1,3）A（1,2）通過(guò)搜索得到的圖為搜索圖。由搜索圖中的所有節(jié)點(diǎn)及反向指針?biāo)鶚?gòu)成的集合是一棵樹，為搜索樹。第十四頁(yè)，共五十一頁(yè)，編輯于2023年，星期三14TowerofHanoi問(wèn)題

有N個(gè)有孔的盤子，最初這些盤子都疊放在柱a上（如圖1），要求將這N個(gè)盤子借助柱b從柱a移到柱c（如圖2），移動(dòng)時(shí)有以下限制，如何移動(dòng)？每次只能移動(dòng)一個(gè)盤子；大盤不能放在小盤上。第十五頁(yè)，共五十一頁(yè)，編輯于2023年，星期三15重排九宮問(wèn)題

S02 8 3 1 4 7 6 5

在3*3的方格棋盤上放置分別標(biāo)語(yǔ)有數(shù)字的八張牌：1，2，3，4，5，6，7，8初始狀態(tài)為S0

目標(biāo)狀態(tài)為Sg。

可使用的操作算符：位于空格的左、下、右、上的牌移入空格。

S2

2 3 18 4 76 5 Sg1 2 3 8 47 6 5

S12 3

18 476 5

S3

12 3 8 4 76 5第十六頁(yè)，共五十一頁(yè)，編輯于2023年，星期三163．2盲目搜索1廣度優(yōu)先搜索2深度優(yōu)先搜索3有限深度優(yōu)先搜索4代價(jià)樹廣度優(yōu)先搜索5代價(jià)樹深度優(yōu)先搜索第十七頁(yè)，共五十一頁(yè)，編輯于2023年，星期三171廣度優(yōu)先搜索1）把初始節(jié)點(diǎn)S0放入OPEN。2）檢查OPEN是否為空，是，無(wú)解，退出。3）把OPEN第一個(gè)節(jié)點(diǎn)（并記該節(jié)點(diǎn)為n）取出放入CLOSED。4）考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)，是，得解，退出。5）若節(jié)點(diǎn)n不可擴(kuò)展，轉(zhuǎn)2）。6）擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN的尾部，并為每一個(gè)子節(jié)點(diǎn)都配一個(gè)指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)2）。第十八頁(yè)，共五十一頁(yè)，編輯于2023年，星期三18重排九宮問(wèn)題重排九宮問(wèn)題第十九頁(yè)，共五十一頁(yè)，編輯于2023年，星期三19第二十頁(yè)，共五十一頁(yè)，編輯于2023年，星期三20第二十一頁(yè)，共五十一頁(yè)，編輯于2023年，星期三21第二十二頁(yè)，共五十一頁(yè)，編輯于2023年，星期三22第二十三頁(yè)，共五十一頁(yè)，編輯于2023年，星期三232深度優(yōu)先搜索1）把初始節(jié)點(diǎn)S0放入OPEN。2）檢查OPEN是否為空，是，無(wú)解，退出。3）把OPEN第一個(gè)節(jié)點(diǎn)（并記該節(jié)點(diǎn)為n）取出放入CLOSED。4）考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)，是，得解，退出。5）若節(jié)點(diǎn)n不可擴(kuò)展，轉(zhuǎn)2）。6）擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN的首部，并為每一個(gè)子節(jié)點(diǎn)都配一個(gè)指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)2）。第二十四頁(yè)，共五十一頁(yè)，編輯于2023年，星期三24重排九宮問(wèn)題第二十五頁(yè)，共五十一頁(yè)，編輯于2023年，星期三25重排九宮問(wèn)題第二十六頁(yè)，共五十一頁(yè)，編輯于2023年，星期三26重排九宮問(wèn)題第二十七頁(yè)，共五十一頁(yè)，編輯于2023年，星期三27重排九宮問(wèn)題第二十八頁(yè)，共五十一頁(yè)，編輯于2023年，星期三28重排九宮問(wèn)題第二十九頁(yè)，共五十一頁(yè)，編輯于2023年，星期三29重排九宮問(wèn)題第三十頁(yè)，共五十一頁(yè)，編輯于2023年，星期三30重排九宮問(wèn)題第三十一頁(yè)，共五十一頁(yè)，編輯于2023年，星期三313有界深度優(yōu)先搜索搜索過(guò)程：1）把初始節(jié)點(diǎn)S0放入OPEN，置S0的深度d(S0)。2）檢查OPEN是否為空，是，無(wú)解，退出。3）把OPEN第一個(gè)節(jié)點(diǎn)（并記該節(jié)點(diǎn)為n）取出放入CLOSED。4）考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)，是，得解，退出。5）若節(jié)點(diǎn)n的深度d(節(jié)點(diǎn)n)=dm，轉(zhuǎn)2）。6）若節(jié)點(diǎn)n不可擴(kuò)展，轉(zhuǎn)2）。7）擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN的首部，并為每一個(gè)子節(jié)點(diǎn)都配一個(gè)指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)2）。見p269例6.6

第三十二頁(yè)，共五十一頁(yè)，編輯于2023年，星期三324代價(jià)樹廣度優(yōu)先搜索邊上標(biāo)有代價(jià)(或費(fèi)用)的樹為代價(jià)樹.在代價(jià)樹中,若有g(shù)(x)表示從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x的代價(jià),用c(x1,x2)表示從父節(jié)點(diǎn)x1到子節(jié)點(diǎn)x2的代價(jià),則有:g(x2)=g(x1)+c(x1,x2)第三十三頁(yè)，共五十一頁(yè)，編輯于2023年，星期三334代價(jià)樹廣度優(yōu)先搜索搜索過(guò)程：1）把初始節(jié)點(diǎn)S0放入OPEN，令g(S0)=0。2）檢查OPEN是否為空，是，無(wú)解，退出。3）把OPEN第一個(gè)節(jié)點(diǎn)（并記該節(jié)點(diǎn)為n）取出放入CLOSED。4）考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)，是，得解，退出。5）若節(jié)點(diǎn)n不可擴(kuò)展，轉(zhuǎn)2）。6）擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN，并為每一個(gè)子節(jié)點(diǎn)都配一個(gè)指向父節(jié)點(diǎn)的指針計(jì)算各子節(jié)點(diǎn)的代價(jià)，并按各節(jié)點(diǎn)的代價(jià)對(duì)OPEN表中的全部節(jié)點(diǎn)進(jìn)行排序（從小到大），然后轉(zhuǎn)2）。第三十四頁(yè)，共五十一頁(yè)，編輯于2023年，星期三34代價(jià)樹廣度優(yōu)先搜索第三十五頁(yè)，共五十一頁(yè)，編輯于2023年，星期三355代價(jià)樹深度優(yōu)先搜索搜索過(guò)程：1）把初始節(jié)點(diǎn)S0放入OPEN，令g(S0)=0。2）檢查OPEN是否為空，是，無(wú)解，退出。3）把OPEN第一個(gè)節(jié)點(diǎn)（并記該節(jié)點(diǎn)為n）取出放入CLOSED。4）考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)，是，得解，退出。5）若節(jié)點(diǎn)n不可擴(kuò)展，轉(zhuǎn)2）。6）擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)按邊代價(jià)從小到大進(jìn)行排序放入OPEN首部，并為每一個(gè)子節(jié)點(diǎn)都配一個(gè)指向父節(jié)點(diǎn)的指針計(jì)算各子節(jié)點(diǎn)的代價(jià)，然后轉(zhuǎn)2）。第三十六頁(yè)，共五十一頁(yè)，編輯于2023年，星期三361.寬度優(yōu)先、深度優(yōu)先搜索，其主要的差別是OPEN表中待擴(kuò)展節(jié)點(diǎn)的順序問(wèn)題。2.盲目搜索(弱方法)效率低，耗費(fèi)過(guò)多的計(jì)算空間與時(shí)間。3.若選擇最有希望的節(jié)點(diǎn)加以擴(kuò)展，則搜索效率將會(huì)大為提高。小結(jié)第三十七頁(yè)，共五十一頁(yè)，編輯于2023年，星期三373.3啟發(fā)式搜索啟發(fā)式搜索：?jiǎn)l(fā)式搜索是利用問(wèn)題本身的某些啟發(fā)信息，以制導(dǎo)搜索朝著最有希望的方向前進(jìn)。

啟發(fā)式搜索過(guò)程中，要對(duì)OPEN表進(jìn)行排序，這就需要有一種方法來(lái)計(jì)算待擴(kuò)展節(jié)點(diǎn)有希望通向目標(biāo)節(jié)點(diǎn)的不同程度，我們總是希望能找到最有希望通向目標(biāo)節(jié)點(diǎn)的待擴(kuò)展節(jié)點(diǎn)優(yōu)先擴(kuò)展。一種最常用的方法是定義一個(gè)評(píng)價(jià)函數(shù),:f(x)=g(x)+h(x)g(x)為從初始節(jié)點(diǎn)s0到節(jié)點(diǎn)x已經(jīng)實(shí)際付出的代價(jià)；

h(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)Sg的最短路徑的估計(jì),它體現(xiàn)了問(wèn)題的啟發(fā)性信息。h(x)稱為啟發(fā)函數(shù)。

第三十八頁(yè)，共五十一頁(yè)，編輯于2023年，星期三38

1局部擇優(yōu)搜索

●

局部擇優(yōu)搜索：當(dāng)一個(gè)節(jié)點(diǎn)被擴(kuò)展后，按f(x)對(duì)每個(gè)子節(jié)點(diǎn)計(jì)算估價(jià)值，并選擇最小者作為下一個(gè)要考查的節(jié)點(diǎn)。由于它每次都只是在子節(jié)點(diǎn)的范圍中選擇要考查的子節(jié)點(diǎn)，所以稱為局部擇優(yōu)搜索。深度優(yōu)先搜索、代價(jià)樹的深度優(yōu)先搜索以及局部擇優(yōu)搜索都是以子節(jié)點(diǎn)作為考察范圍的，這是它們的共同處。在局部擇優(yōu)搜索中，若令f(x)=g(x),則局部擇優(yōu)搜索就成為代價(jià)樹的深度優(yōu)先搜索；若令f(x)=d(x),這里d(x)表示節(jié)點(diǎn)x的深度,則局部擇優(yōu)搜索就成為深度優(yōu)先搜索。所以深度優(yōu)先搜索和代價(jià)樹的深度優(yōu)先搜索可看作局部擇優(yōu)搜索的兩個(gè)特例。第三十九頁(yè)，共五十一頁(yè)，編輯于2023年，星期三39

2全局擇優(yōu)搜索●

全局擇優(yōu)搜索：每次都是從OPEN表的全體節(jié)點(diǎn)中選擇一個(gè)估價(jià)值最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展。在全局擇優(yōu)搜索中，如果f(x)=g(x),則它就成為代價(jià)樹的廣度優(yōu)先搜索；若令f(x)=d(x)（這里d(x)表示節(jié)點(diǎn)x的深度）,則它就成為廣度優(yōu)先搜索。所以廣度優(yōu)先搜索和代價(jià)樹的廣度優(yōu)先搜索可看作全局擇優(yōu)搜索的兩個(gè)特例。第四十頁(yè)，共五十一頁(yè)，編輯于2023年，星期三40例用全局擇優(yōu)搜索求解重排九宮問(wèn)題，其初始狀態(tài)和目標(biāo)狀態(tài)如圖所示：

設(shè)估價(jià)函數(shù)為f(x)=d(x)+h(x)其中d(x)表示節(jié)點(diǎn)x的深度，h(x)表示節(jié)點(diǎn)x的格局與目標(biāo)節(jié)點(diǎn)格局不相同的牌數(shù)．第四十一頁(yè)，共五十一頁(yè)，編輯于2023年，星期三41搜索樹八數(shù)碼問(wèn)題

第四十二頁(yè)，共五十一頁(yè)，編輯于2023年，星期三42第四十三頁(yè)，共五十一頁(yè)，編輯于2023年，星期三433啟發(fā)式搜索算法A基本思想：定義一個(gè)評(píng)價(jià)函數(shù)f:

f（n）＝g（n）＋h（n）

其中n是被評(píng)價(jià)的節(jié)點(diǎn)。

g*(n)：表示從初始節(jié)點(diǎn)s到節(jié)點(diǎn)n的最短路徑的代價(jià)；

h*(n)：表示從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)g的最短路徑的代價(jià)；

f*(n)=g*(n)+h*(n)：表示從初始節(jié)點(diǎn)s經(jīng)過(guò)節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)g的最短路徑的代價(jià)。

而f（n）、g（n）和h（n）則分別表示是對(duì)f*（n）、g*（n）和h*（n）三個(gè)函數(shù)值的的估計(jì)值，是一種預(yù)測(cè)。

第四十四頁(yè)，共五十一頁(yè)，編輯于2023年，星期三44

利用評(píng)價(jià)函數(shù)f(n)＝g(n)＋h(n)來(lái)排列OPEN表節(jié)點(diǎn)順序的圖搜索算法稱為A算法。

A算法每次按照f(shuō)(n)值的大小對(duì)OPEN表中的元素進(jìn)行排序，f值小的節(jié)點(diǎn)放在前面，而f值大的節(jié)點(diǎn)則被放在OPEN表的后面，這樣每次擴(kuò)展節(jié)點(diǎn)時(shí)，都是選擇當(dāng)前f值最小的節(jié)點(diǎn)來(lái)優(yōu)先擴(kuò)展。第四十五頁(yè)，共五十一頁(yè)，編輯于2023年，星期三454最佳圖搜索算法A﹡（OptimalSearch）

在A算法中的f(x)=g(x)+h(x)中每一節(jié)點(diǎn)x都有h(x)≤h*(x)h(x)是的h*(x)下界則該A算法稱為A*算法。下面從理論上討論A*算法的幾個(gè)重要特性：(1)A*算法的可采納性

可采納性：對(duì)于一個(gè)可解狀態(tài)空間圖（即從S0到G存在路徑），如果搜索算法能找到一條最佳路徑，則稱該搜索算法是可采納的（即算法找到一條最佳路徑解后終止）。結(jié)論1：A*算法是可采納的。第四十六頁(yè)，共五十一頁(yè)，編輯于2023年，星期三46（2）A*算法的最優(yōu)性（即信息量的比較）A*算法的搜索效率在很大程度上取決于h(x)，在滿足h(x)≤h*(x)下，h(x)的值越大，表明攜帶啟發(fā)性信息越多。

結(jié)論2：設(shè)有兩個(gè)A*算法A1*和A2*：A1*：f1(x)=g1(x)+h1(x)A2*：f2(x)=g2(x)+h2(x)對(duì)所有的非目標(biāo)節(jié)點(diǎn)x均有：h2(x)≥h1(x)（A2*比A1*有更多的信息）則A1*擴(kuò)展節(jié)點(diǎn)數(shù)不會(huì)比A2*擴(kuò)展節(jié)點(diǎn)少。即A2*的擴(kuò)展節(jié)點(diǎn)集是A1*擴(kuò)展節(jié)點(diǎn)集的子集。（通過(guò)搜索樹深度應(yīng)用數(shù)學(xué)歸納法證明）。第四十七頁(yè)，共五十一頁(yè)，編輯于2023年，星期三47（3）A*算法的改進(jìn)(h(x)的單調(diào)性限制)單調(diào)性限制：①h(sg)=0②設(shè)xj是xi的任意子節(jié)點(diǎn)有：h(xi)≤h(xj)+c(xi,xj)

結(jié)論3：當(dāng)h滿足單調(diào)性限制，則A*算法擴(kuò)展的每個(gè)節(jié)點(diǎn)x都滿足：g(x)=g*(x)—保證每次擴(kuò)展的路徑是最優(yōu)路徑。且A*算法所擴(kuò)展的節(jié)點(diǎn)序列的f值是非遞減的。第四十八頁(yè)，共五十一頁(yè)，編輯于2023年，星期三48例題八數(shù)碼問(wèn)題:初始狀態(tài)和目標(biāo)狀態(tài)

試用A*算法求解該問(wèn)題.

第四十九頁(yè)，共五十一頁(yè)，編輯于2023年，星期三49

解：（1）估價(jià)函數(shù)f1(n)=d(n)+w(n)