狀態(tài)空間的概念和表示方法

狀態(tài)空間的概念和表示方法1狀態(tài)空間問(wèn)題舉例首先讓我們看下面兩個(gè)例子：八數(shù)碼問(wèn)題，也叫重排九宮問(wèn)題。在一個(gè)3×3的方格棋盤(pán)上放置著1，2，3，4，5，6，7，8八個(gè)數(shù)碼，每個(gè)數(shù)碼占一格，余下的一個(gè)是空格。這些數(shù)碼可在棋盤(pán)上移動(dòng)。移動(dòng)規(guī)則是：與空格相鄰的數(shù)碼方可移入空格。問(wèn)題的目標(biāo)是：對(duì)于指定的初始棋局通過(guò)移動(dòng)數(shù)碼塊，得到目標(biāo)棋局（如圖所示），要求給出數(shù)碼的移動(dòng)步驟。2狀態(tài)空間的基本概念和特點(diǎn)首先我們引入狀態(tài)空間的幾個(gè)基本概念。1.狀態(tài)狀態(tài)是描述問(wèn)題在求解過(guò)程中任意一確定時(shí)刻的狀況，它表征了問(wèn)題特征和結(jié)構(gòu)等。如，在八數(shù)碼問(wèn)題中，可以把棋局看成狀態(tài)。那么初始棋局就是初始狀態(tài)，目標(biāo)棋局為目標(biāo)狀態(tài)。在迷官問(wèn)題中，k在S，可以看作一種狀態(tài)，它是初始狀態(tài)k在S，也是一種狀態(tài)，k到了S，是目標(biāo)狀態(tài)。2.狀態(tài)轉(zhuǎn)換規(guī)則狀態(tài)轉(zhuǎn)換規(guī)則就是能使問(wèn)題由一種狀態(tài)改變?yōu)榱硪环N狀態(tài)的條件和操作。在八數(shù)碼問(wèn)題中，可以定義四條移動(dòng)規(guī)則：鄰接空格的數(shù)碼可以右移一格、左移一格、上移一格或下移格。利用這些規(guī)則可以使八數(shù)碼棋局從一個(gè)狀態(tài)轉(zhuǎn)換到另一個(gè)狀態(tài)。0g43.狀態(tài)空間狀態(tài)空間是指問(wèn)題的全部狀態(tài)及一切可用的狀態(tài)轉(zhuǎn)換規(guī)則所集合。如何用狀態(tài)空間表示法表示問(wèn)題呢？我們以八數(shù)碼問(wèn)題為例介紹這種表示方法。狀態(tài)：一個(gè)問(wèn)題的起始狀態(tài)稱(chēng)為初始狀態(tài)，要達(dá)到的最終目標(biāo)稱(chēng)為目標(biāo)狀態(tài)，八數(shù)碼問(wèn)題的初始狀態(tài)（S）為初始棋局，目標(biāo)狀態(tài)（S）為目標(biāo)棋局。如下圖所示。0g八數(shù)碼問(wèn)題的所有的狀態(tài)和狀態(tài)轉(zhuǎn)換規(guī)則構(gòu)成的集合就是八數(shù)碼問(wèn)題的狀態(tài)空間。將八數(shù)碼問(wèn)題用狀態(tài)空間表示出來(lái)就是八數(shù)碼問(wèn)題的狀態(tài)空間表示。一般人工智能問(wèn)題的狀態(tài)空間都非常大，最簡(jiǎn)單的八數(shù)碼問(wèn)題就會(huì)有362880（9!）種狀態(tài)。

4.狀態(tài)圖狀態(tài)空間也可以用圖的形式來(lái)表達(dá)出來(lái)，這種圖稱(chēng)為狀態(tài)空間圖，簡(jiǎn)稱(chēng)狀態(tài)圖。其中，節(jié)點(diǎn)表示狀態(tài)；有向邊（?。┍硎緺顟B(tài)轉(zhuǎn)換規(guī)則，八數(shù)碼問(wèn)題的狀態(tài)空間圖，圖中有S、S至S共34個(gè)節(jié)點(diǎn)，即八數(shù)碼問(wèn)題中的34個(gè)狀態(tài)。因?yàn)榘藬?shù)碼問(wèn)題的狀態(tài)數(shù)量非常大，在這里只兩出狀態(tài)圖的部分。0133

5.用Prolog語(yǔ)言描述狀態(tài)空間用狀態(tài)空間表示法表示問(wèn)題的一個(gè)優(yōu)點(diǎn)是此表示法易于計(jì)算機(jī)語(yǔ)言實(shí)現(xiàn)。在第三章中，我們學(xué)習(xí)了一種人工智能語(yǔ)言——Prolog語(yǔ)言。我們可不可以用Prolog來(lái)描述問(wèn)題的狀態(tài)空間呢？3狀態(tài)空間問(wèn)題求解的基本方法把所求解的問(wèn)題用狀態(tài)空間的形式表示出來(lái)以后，原來(lái)的問(wèn)題求解就轉(zhuǎn)化為對(duì)狀態(tài)空間問(wèn)題的求解，對(duì)狀態(tài)空間問(wèn)題的求解過(guò)程其實(shí)就是一個(gè)搜索過(guò)程。從初始狀態(tài)開(kāi)始，不斷地應(yīng)用規(guī)則，從一個(gè)狀態(tài)轉(zhuǎn)變?yōu)榱硪粋€(gè)狀態(tài)，最后達(dá)到目標(biāo)狀態(tài)為止，這種求解過(guò)程稱(chēng)為狀態(tài)空間法。要使用狀態(tài)空間法解決問(wèn)題，首先要用一定的數(shù)據(jù)結(jié)構(gòu)，比如字符串、數(shù)組、矩陣、樹(shù)、表、集合等，來(lái)描述狀態(tài)空間，在確定了一個(gè)合適的數(shù)據(jù)結(jié)構(gòu)后，一個(gè)狀態(tài)就對(duì)應(yīng)該結(jié)構(gòu)的一個(gè)確定的值，這種方法也叫做狀態(tài)描述。例如，八數(shù)碼問(wèn)題既可以通過(guò)矩陣，又可用數(shù)組來(lái)描述。對(duì)于狀態(tài)空間表示的問(wèn)題，其求解過(guò)程可以歸結(jié)為對(duì)狀態(tài)空間的搜索。搜索技術(shù)，特別是啟發(fā)式搜索技術(shù)在人工智能領(lǐng)域中，是問(wèn)題求解的主要方法之一，一直受到高度重視，一些著名的人工智能程序，如紐厄爾、肖和西蒙的“LogicTheorist”、通用問(wèn)題求解程序GPS，塞繆爾的跳棋程序“Checkers”，格林布萊特的國(guó)際象棋程序等都是采用搜索技術(shù)來(lái)解決問(wèn)題的程序。今天，搜索技術(shù)已廣泛應(yīng)用于自然語(yǔ)言理解、自動(dòng)程序設(shè)計(jì)、模式識(shí)別、機(jī)器人學(xué)、專(zhuān)家系統(tǒng)、數(shù)學(xué)定理自動(dòng)證明、博弈和信息檢索等眾多領(lǐng)域。在狀態(tài)空間法中，基于問(wèn)題解決效率方面的原因，通常，不是把問(wèn)題的全部狀態(tài)空間圖直接存入計(jì)算機(jī)，而是僅僅在計(jì)算機(jī)中存入關(guān)于該問(wèn)題的各種知識(shí)，再根據(jù)推理（或搜索）的需要，逐步生成問(wèn)題的狀態(tài)空間圖。在計(jì)算機(jī)中，根據(jù)有關(guān)知識(shí)逐步產(chǎn)生問(wèn)題的狀態(tài)空間圖，并檢索所產(chǎn)生的狀態(tài)空間是否也包含了目標(biāo)狀態(tài)，這一過(guò)程被稱(chēng)作搜索過(guò)程。決定搜索過(guò)程怎樣進(jìn)行，即搜索策略的選定主要取決于如何選取規(guī)則。選取規(guī)則有兩種基本方式：一種是不考慮問(wèn)題所具有的特定知識(shí)，系統(tǒng)根據(jù)事先確定的某