人工智能概論知識表示(狀態(tài)空間表示法)

知識表示狀態(tài)空間表示法人工智能概論知識表示(狀態(tài)空間表示法)全文共14頁，當(dāng)前為第1頁。狀態(tài)空間表示法現(xiàn)實世界中的問題求解過程實際上可以看做是一個搜索或者推理的過程。推理過程實際上也是一個搜索過程，它要在知識庫中搜索和前提條件相匹配的規(guī)則，而后利用這些規(guī)則進行推理，所以任何問題求解的本質(zhì)都是一個搜索過程。為了進行有效的搜索，對所求解的問題要以適當(dāng)?shù)男问奖硎境鰜?，其表示的方法直接影響到搜索效率。狀態(tài)空間表示法就是用來表示問題及其搜索過程的一種方法。狀態(tài)空間表示法是人工智能中最基本的形式化方法，也是討論問題求解技術(shù)的基礎(chǔ)。人工智能概論知識表示(狀態(tài)空間表示法)全文共14頁，當(dāng)前為第2頁。１、問題狀態(tài)空間的構(gòu)成狀態(tài)空間表示法就是以“狀態(tài)空間”的形式對問題進行表示。狀態(tài)空間表示法的定義。（１）狀態(tài)狀態(tài)是描述問題求解過程中不同時刻狀況的數(shù)據(jù)結(jié)構(gòu)。一般用一組變量的有序集合表示：Ｑ＝（ｑ０，ｑ１，…，ｑｎ）其中每個元素ｑｉ（ｉ＝０，１，２，…，ｎ）為集合的分量，稱為狀態(tài)變量。當(dāng)給每一個分量以確定的值時，就得到了一個具體的狀態(tài)。人工智能概論知識表示(狀態(tài)空間表示法)全文共14頁，當(dāng)前為第3頁。１問題狀態(tài)空間的構(gòu)成（2）算符引起狀態(tài)中某些分量發(fā)生變化，從而使問題由一個狀態(tài)變?yōu)榱硪粋€狀態(tài)的操作稱為算符。算符可分為走步、過程、規(guī)則、數(shù)學(xué)算子、運算符號或邏輯符號等。例如：在產(chǎn)生式系統(tǒng)中，每一條產(chǎn)生式規(guī)則就是一個算符；在下棋程序中，一個算符就是一個走步；人工智能概論知識表示(狀態(tài)空間表示法)全文共14頁，當(dāng)前為第4頁。１問題狀態(tài)空間的構(gòu)成（３）狀態(tài)空間由表示一個問題的全部狀態(tài)及一切可用算符構(gòu)成的集合稱為該問題的狀態(tài)空間。它一般由三部分構(gòu)成：問題的所有可能初始狀態(tài)構(gòu)成的集合Ｓ；算符集合Ｆ；目標狀態(tài)集合Ｇ。用一個三元組表示如下：（Ｓ，Ｆ，Ｇ）狀態(tài)空間的圖示形式稱為狀態(tài)空間圖。其中，節(jié)點表示狀態(tài)；有向邊（?。┍硎舅惴Ｈ斯ぶ悄芨耪撝R表示(狀態(tài)空間表示法)全文共14頁，當(dāng)前為第5頁。１問題狀態(tài)空間的構(gòu)成（４）問題的解從問題的初始狀態(tài)集Ｓ出發(fā)，經(jīng)過一系列的算符運算，到達目標狀態(tài)。由初始狀態(tài)到目標狀態(tài)所用算符的序列就構(gòu)成了問題的一個解。人工智能概論知識表示(狀態(tài)空間表示法)全文共14頁，當(dāng)前為第6頁。２用狀態(tài)空間表示問題的步驟用狀態(tài)空間方法表示問題時的步驟如下：（１）定義狀態(tài)的描述形式。（２）用所定義的狀態(tài)描述形式把問題的所有可能的狀態(tài)都表示出來，并確定出問題的初始狀態(tài)集合描述和目標狀態(tài)集合描述。（３）定義一組算符，使得利用這組算符可把問題由一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài)。人工智能概論知識表示(狀態(tài)空間表示法)全文共14頁，當(dāng)前為第7頁。３利用狀態(tài)空間求解問題的過程問題的求解過程是一個不斷把算符作用于狀態(tài)的過程。首先，將適用的算符作用于初始狀態(tài)，以產(chǎn)生新的狀態(tài)；然后，再把一些適用的算符作用于新的狀態(tài)；這樣繼續(xù)下去，直到產(chǎn)生的狀態(tài)為目標狀態(tài)為止。這時，就得到了問題的一個解，這個解是從初始狀態(tài)到目標狀態(tài)所用算符構(gòu)成的序列。人工智能概論知識表示(狀態(tài)空間表示法)全文共14頁，當(dāng)前為第8頁。３利用狀態(tài)空間求解問題的過程說明：①可能有多個算符序列都可使問題從初始狀態(tài)變到目標狀態(tài)，這就得到了多個解。其中有的使用算符較少，有的較多，把使用算符最少的解稱為最優(yōu)解。這里只是從解中算符的個數(shù)來評價解的優(yōu)劣，評價解的優(yōu)劣主要是看使用算符時所付出的代價，只有總代價最小的解才是最優(yōu)解。②對任何一個狀態(tài)，可使用的算符可能不止一個，這樣由一個狀態(tài)所生成的后繼狀態(tài)就可能有多個。當(dāng)對這些后繼狀態(tài)使用算符生成更進一步的狀態(tài)時，首先應(yīng)對哪一個狀態(tài)進行操作呢？這屬于搜索策略的問題，不同的搜索策略其操作的順序是不相同的。人工智能概論知識表示(狀態(tài)空間表示法)全文共14頁，當(dāng)前為第9頁。３利用狀態(tài)空間求解問題的過程例1：二階Ｈａｎｏｉ塔問題。已知：３個柱子１、２、３和兩個盤子Ａ、Ｂ（Ａ比Ｂ?。３跏紶顟B(tài)：Ａ、Ｂ依次放在１柱上。目標狀態(tài)：Ａ、Ｂ依次放在柱子３上。條件：每次可移動一個盤子，盤子上方是空頂方可移動，而且任何時候都不允許大盤在小盤之上。人工智能概論知識表示(狀態(tài)空間表示法)全文共14頁，當(dāng)前為第10頁。３利用狀態(tài)空間求解問題的過程解：按照上面給出的步驟，將問題以狀態(tài)空間的形式表示出來。第一步：定義問題狀態(tài)的描述形式：設(shè)用Ｓｋ＝（ＳｋＡ，ＳｋＢ）表示問題的狀態(tài)，ＳｋＡ表示盤子Ａ所在的柱號，ＳｋＢ表示盤子Ｂ所在的柱號。第二步：用所定義的狀態(tài)描述形式把問題的所有可能的狀態(tài)都表示出來，并確定出問題的初始狀態(tài)集合描述和目標狀態(tài)集合描述。人工智能概論知識表示(狀態(tài)空間表示法)全文共14頁，當(dāng)前為第11頁。３利用狀態(tài)空間求解問題的過程本問題所有可能的狀態(tài)共有九種，如圖所示，各狀態(tài)的形式描述如下：問題的初始狀態(tài)集合為Ｓ＝｛Ｓ０｝，目標狀態(tài)集合為Ｇ＝｛Ｓ８｝。人工智能概論知識表示(狀態(tài)空間表示法)全文共14頁，當(dāng)前為第12頁。３利用狀態(tài)空間求解問題的過程第三步：定義一組算符Ｆ。算符Ａ（ｉ，ｊ）表示把盤子Ａ從第ｉ號柱子移到第ｊ號柱子上的操作；算符Ｂ（ｉ，ｊ）表示把盤子Ｂ從第ｉ號柱子移到第ｊ號柱子上的操作。這樣定義的算符組Ｆ中共有１２個算符，它們分別是Ａ（１，２）Ａ（１，３）Ａ（２，１）Ａ（２，３）Ａ（３，１）Ａ（３，２）Ｂ（１，２）Ｂ（１，３）Ｂ（２，１）Ｂ（２，３）Ｂ（３，１）Ｂ（３，２）至此，該問題的狀態(tài)空間（Ｓ，Ｆ，Ｇ）構(gòu)造完成。這就完成了對問題的狀態(tài)空間表示。人工智能概論知識表示(狀態(tài)空間表示法)全文共14頁，當(dāng)前為第13頁。３利用狀態(tài)空間求解問題的過程為了求解該問題，根據(jù)該狀態(tài)空間的９種可能狀態(tài)和12種算符，構(gòu)造它的狀態(tài)空間圖，如圖所示從初始節(jié)點（