狀態(tài)空間表示法

2.3精確性知識(shí)的表示12.3.1

知識(shí)的狀態(tài)空間表示法1.狀態(tài)與狀態(tài)空間的概念（1）狀態(tài)描述某類(lèi)不同系統(tǒng)（事物）間的差別而引入的一組最小變量q1,q2,...qn的有序集合。其矢量形式為2其矢量形式為3（2）狀態(tài)空間

表示該系統(tǒng)或問(wèn)題全部可能狀態(tài)的集合。

狀態(tài)空間可以用：初始狀態(tài)集合S，操作符集合F，目標(biāo)狀態(tài)集合G構(gòu)成的三元狀態(tài)（S，F(xiàn)，G）來(lái)表示

該三元狀態(tài)(S，F(xiàn)，G)表示系統(tǒng)從某個(gè)初始狀態(tài)開(kāi)始，每加一個(gè)算符，狀態(tài)發(fā)生一次轉(zhuǎn)變，直到到達(dá)目標(biāo)狀態(tài)G。4例如119413131275861321014假設(shè)初始狀態(tài)為：１２３４５６７８９101112131415

我們要求的目標(biāo)狀態(tài)為:5如何把初始狀抬轉(zhuǎn)換為目標(biāo)狀態(tài)——選擇移動(dòng)一個(gè)棋子。每移動(dòng)一次棋子，就會(huì)有一個(gè)新的狀態(tài)，所有可能的狀態(tài)一起，就構(gòu)成了該問(wèn)題的狀態(tài)空間。解決該問(wèn)題，就是嘗試各種不同的走步，直到尋找到達(dá)到目的狀態(tài)的路徑，到達(dá)目標(biāo)狀態(tài)為止。從初始狀態(tài)開(kāi)始，嘗試不同的走步，就構(gòu)成了一個(gè)有不同狀態(tài)組成的圖。61171943515138122610141171935151348122610141171945151338122610141171935151348122610141171943515131282610141179415151338122610141171943515138122610141171915351348122610141171495151338122610141171943515131286210141171945151338122610141171943513128152610147

從舊狀態(tài)產(chǎn)生新?tīng)顟B(tài)，需要注意不出現(xiàn)重復(fù)狀態(tài)，既要檢驗(yàn)是否已經(jīng)描述了該狀態(tài)——看產(chǎn)生的新?tīng)顟B(tài)是否與某個(gè)原已描述的狀態(tài)匹配，如果已產(chǎn)生了，則該狀態(tài)從新?tīng)顟B(tài)中刪除。

通過(guò)某種推理或搜索策略，我們總可以尋找到一條路經(jīng)，從初始狀態(tài)到達(dá)目標(biāo)狀態(tài)。

在智能控制中，也就是我們總可以找到一種控制策略，使得被控對(duì)象的行為（狀態(tài)）能夠按我們期望的方式變化（如果系統(tǒng)是可控的），最終達(dá)到控制目的。應(yīng)用狀態(tài)空間法，需要尋找減少狀態(tài)存儲(chǔ)代價(jià)（時(shí)間、空間）方法。8減少數(shù)據(jù)存儲(chǔ)的一種方法是，給出某種實(shí)現(xiàn)狀態(tài)轉(zhuǎn)換的走步策略，這樣，我們只要給出了初始狀態(tài)，策略（也就是操作符F)，就可以由初始狀態(tài)或前一個(gè)狀態(tài)推出下一個(gè)狀態(tài)，直到達(dá)到目標(biāo)狀態(tài)。而且這是使用比較多的方法。因此，要實(shí)現(xiàn)對(duì)某個(gè)問(wèn)題的狀態(tài)空間描述，需要：確定狀態(tài)描述方法，特別是初始狀態(tài)的描述；確定狀態(tài)間聯(lián)系的描述方法，較好的表示出不同狀態(tài)之間的聯(lián)系，確定操作符集合及其對(duì)狀態(tài)描述的作用；目標(biāo)狀態(tài)的描述。我們來(lái)看一個(gè)例子92

另一個(gè)狀態(tài)空間法描述的例子假設(shè)房間里有一個(gè)人，一個(gè)箱子和一筐蘋(píng)果。蘋(píng)果吊在天花板下方，人直接摘不到，需要站在箱子上才能摘到蘋(píng)果。如圖所示CA人箱B蘋(píng)果10

(1)狀態(tài)：選擇為（W，X，Y，Z）W——人所處在的水平面上的位置X——人所處的高度位置，在地面，X=0

在箱子上，X=1Y——箱子所在的水平面上的位置Z——是否摘到蘋(píng)果的狀態(tài)，=0，未摘到

=1，摘到11狀態(tài)為(W,0,Y,Z)表示人在水平位置W，處于地面，箱子在位置Y，沒(méi)摘到蘋(píng)果。在goto(U)操作下，變成新?tīng)顟B(tài)(U,0,Y,Z)——人走到U,還是摘不到蘋(píng)果，箱子在位置Y，摘不到蘋(píng)果。(2)句法規(guī)則人走動(dòng)規(guī)則——用goto(U)

描述的含義：人從原來(lái)水平位置走到新的水平位置U，例如12要推箱子，我們認(rèn)為人和箱子在水平面同一位置W，人在地面故X=0，在操作pushbox(V)的作用下，人將箱子移動(dòng)到位置V。當(dāng)然這時(shí)人和箱子還是在水平面同一位置，人站在地面上，故新?tīng)顟B(tài)為（V,0,V,Z）,Z表示現(xiàn)在還不關(guān)心Z的取值，當(dāng)然一般認(rèn)為現(xiàn)在Z=0。推箱子pushbox(V)它的作用是將箱子從原始水平位置推到新位置V。例如：13對(duì)于與前面提到的命題，箱子原來(lái)處于B，人走到B后，才能將箱子移動(dòng)到蘋(píng)果所處的位置C。將具體的實(shí)例數(shù)據(jù)帶入，得到由于還沒(méi)有摘到蘋(píng)果，應(yīng)該有Z=0，這里我們還可以不關(guān)心它。14爬到箱子上或從箱子上下來(lái)

用climbox

表示，如果原來(lái)在箱子上，該操作表示人從箱子上下來(lái)，否則表示人從地面爬到箱子上。需要注意這時(shí)人和箱子處于同一水平位置。例如人從箱子上下來(lái)的描述15grasp——摘取蘋(píng)果。（C，1，C,0）表示人、箱子的水平位置都處于C的位置，即蘋(píng)果所在的位置。人已站在箱子上面，可以摘到蘋(píng)果但還沒(méi)有摘。（C，1，C，1）則表示已摘到蘋(píng)果。16這樣，我們就有了狀態(tài)集合{(A,0,B,0),(B,0,B,0)，(C,0,C,0),(C,1,C,0),(C,1,C,1),(C,0,C,1)}操作集合F:{goto(),pushbox(),climbox,grasp}從初始狀態(tài)（A,0,B,0），每經(jīng)過(guò)一個(gè)操作，都轉(zhuǎn)換到下一個(gè)特定狀態(tài)——從前以狀態(tài)和操作符，可以確定下一個(gè)狀態(tài)，這樣就不必存儲(chǔ)每一個(gè)可能的狀態(tài)，可以節(jié)省存儲(chǔ)空間和搜索時(shí)間。17（A，0，B，0）（B，0，B，0）（C，1，C，0）goto（B）（C，0，C，0）pushbox（C）（C，1，C，1）climboxgrasp（C，0，C，1）climbox(3)該命題的狀態(tài)空間描述：如果人的初始位置不在A，他應(yīng)該從所在位置走到箱子所在位置……18這里我們用一個(gè)符號(hào)來(lái)表示人、箱子在平面生的位置，更一般的情況，使用平面坐標(biāo)（x,y）來(lái)表示平面上的位置。對(duì)于一個(gè)固定格式的狀態(tài)數(shù)據(jù)，用平面坐標(biāo)描述平面位置方法是相似的，只是在前面的數(shù)據(jù)結(jié)構(gòu)，將表示平面未知的符號(hào)用兩個(gè)坐標(biāo)值替換。例如（100，200，0，500，1000，0）人的位置坐標(biāo)箱子的位置坐標(biāo)是否在箱子上的狀態(tài)標(biāo)志是否拿到蘋(píng)果的狀態(tài)標(biāo)志19現(xiàn)假設(shè)有障礙物存在，我們的運(yùn)動(dòng)必須沿著特定的路徑進(jìn)行：AD,DE,EF,FB,BF,FG,GC,再爬上去蘋(píng)果。又該如何描述？CA人箱B蘋(píng)果DEGF如果需要尋找蘋(píng)果的位置，又該如何描述如果不知道障礙物的位置，需要尋找并避開(kāi)障礙，又該如何描述？203

狀態(tài)圖狀態(tài)圖表示方法，就是用圖論的方法來(lái)描述狀態(tài)空間的各個(gè)狀態(tài)以及它們之間的相互關(guān)系。在前面給出了一個(gè)圖，它也可以叫做狀態(tài)圖。但是這個(gè)圖太復(fù)雜。我們用節(jié)點(diǎn)來(lái)表示上圖中的各個(gè)實(shí)際狀態(tài)，就構(gòu)成狀態(tài)圖。狀態(tài)圖是由節(jié)點(diǎn)，有向弧線(xiàn)等構(gòu)成的圖。21實(shí)際上，就是將前面的圖中的狀態(tài)，用一個(gè)節(jié)點(diǎn)來(lái)表示2211719435151381226101411719351513481226101411719451513381226101411719351513481226101411719435151312826101411794151513381226101411719435151381226101411719153513481226101411714951513381226101411719435151312862101411719451513381226101411719435131281526101423狀態(tài)圖表示，主要是為了我們分析問(wèn)題的方便，在計(jì)算機(jī)內(nèi)部，我們還是用一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)表示。242.3.2問(wèn)題的歸約描述方法

所謂問(wèn)題的歸約描述方法，實(shí)際上就是把一個(gè)復(fù)雜問(wèn)題，分解為一組較簡(jiǎn)單的問(wèn)題來(lái)描述和解決的方法。只要解決了這些相對(duì)簡(jiǎn)單的問(wèn)題，就可以解決原來(lái)復(fù)雜的問(wèn)題。我們還是通過(guò)一個(gè)例子來(lái)討論。25132ABC1梵塔問(wèn)題這個(gè)問(wèn)題是：有3根柱子1，2，3和大小不同的三個(gè)圓盤(pán)A，B，C，每個(gè)圓盤(pán)的中心有一個(gè)孔，可以讓柱子穿過(guò)，從而他們可以堆疊在柱子上。最初，全部圓盤(pán)都堆在柱子1上，最大的圓盤(pán)C在最下面，最小的圓盤(pán)A在最上面?，F(xiàn)要求將所有圓盤(pán)都移到柱子3上，同時(shí)有限制條件為：每次只能移動(dòng)最上面的一個(gè)圓盤(pán)放到另一個(gè)柱子上，任何時(shí)候都不允許將大的圓盤(pán)對(duì)方到小的圓盤(pán)之上。26132ABC移動(dòng)AB到柱子2上，是一個(gè)移動(dòng)二圓盤(pán)問(wèn)題132ABCC=1,B=1,A=1（111）C=1,B=2,A=2（122）AB27132ABC移動(dòng)AB到柱子2上后C=1,B=2,A=2（122）132ABC移動(dòng)C到柱子3上是一個(gè)移動(dòng)一園盤(pán)問(wèn)題C=3,B=2,A=2（322）（122）(322)一園盤(pán)問(wèn)題，需要移動(dòng)一個(gè)圓盤(pán)28在此基礎(chǔ)上，將AB移動(dòng)到柱子3上——又是一個(gè)的二圓盤(pán)問(wèn)題。而二圓盤(pán)問(wèn)題，又可以分解為一圓盤(pán)問(wèn)題解決。先將A移動(dòng)到1(322)(321)然后將B移動(dòng)到3，放在C上面(321)(331)最后將A移動(dòng)到3，放在B上面(331)(333)這些符號(hào)的含義292問(wèn)題的歸約解決方法首先我們約定問(wèn)題的描述方法。我們用一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)表示三個(gè)圓盤(pán)在柱子上的位置。格式為：(CBA)含義為：每個(gè)位置的字母的取值，就表示對(duì)應(yīng)圓盤(pán)所在的柱子的編號(hào)。例如（123）表示圓盤(pán)C在柱子1上，圓盤(pán)B在柱子2上，圓盤(pán)A在柱子3上。這樣，A、B、C的取值只可能是1，2，3三個(gè)數(shù)之一。對(duì)于以上問(wèn)題，我們用歸約法描述，可以表示為30（331)→(333)（111)→(122)（122)→(322)（111)→(113)（322)→(333)（111)→(333)（113)→(123)（123)→(122)（322)→(321)（321)→(331)初始條件二圓盤(pán)問(wèn)題結(jié)束條件一圓盤(pán)問(wèn)題31（111）→(113)含義就是執(zhí)行操作，將A移動(dòng)到柱子3上。132ABC移動(dòng)A到柱子3上32（113）→(123)含義就是執(zhí)行操作，將柱子1上的圓盤(pán)B移動(dòng)到柱子2上。132ABC移動(dòng)B到柱子2上33（1）將三圓盤(pán)問(wèn)題分解為第二級(jí)的二圓盤(pán)問(wèn)題，其中包含一個(gè)一圓盤(pán)問(wèn)題。只要解決了第二級(jí)的三個(gè)問(wèn)題，原來(lái)的問(wèn)題就獲得了解決。

（2）二圓盤(pán)問(wèn)題就是將兩個(gè)圓盤(pán)按規(guī)定的堆放順序堆疊在某一個(gè)柱子上。

二圓盤(pán)問(wèn)題又可以再分解為第三級(jí)的一圓盤(pán)問(wèn)題——將一個(gè)圓盤(pán)從原來(lái)的柱子上移動(dòng)到另一個(gè)柱子上。這個(gè)問(wèn)題是簡(jiǎn)單的。

（3）只要解決了第三級(jí)的全部問(wèn)題，則第二級(jí)的問(wèn)題也就得到了解決。

（4）只要解決了第二級(jí)的全部問(wèn)題，最原始的問(wèn)題也就得到了解決。34而第三級(jí)問(wèn)題是容易解決的。這就是歸約法問(wèn)題描述的思想。問(wèn)題歸約法是應(yīng)用算符來(lái)把問(wèn)題描述變換為較簡(jiǎn)單的子問(wèn)題的描述。問(wèn)題的描述可以使用各種數(shù)據(jù)結(jié)構(gòu)，例如字符串、數(shù)組、矢量等。歸約法可以利用狀態(tài)空間的狀態(tài)描述概念。353與或圖表示和狀態(tài)空間法可以用狀態(tài)圖來(lái)表示相似，歸約法可以用與或圖來(lái)表示。用圖表示，也是用節(jié)點(diǎn)來(lái)表示問(wèn)題和子問(wèn)題。例如ANMH36（1）或節(jié)點(diǎn)每個(gè)節(jié)點(diǎn)代表