状态空间表示
前言
本文隸屬于專欄《人工智能》，該專欄為筆者原創，引用請注明來源，不足和錯誤之處請在評論區幫忙指出，謝謝！
本專欄目錄結構和參考文獻請見人工智能
引子
人工智能的多個研究領域從求解現實問題的過程來看，都可抽象為一個“問題求解”過程，問題求解過程實際上就是一個搜索過程。
在搜索過程開始之前，必須先用某種方法或某幾種方法的混和來表示問題。
問題求解技術主要涉及兩個方面：
- 問題的表示
- 求解的方法
狀態空間表示法就是用來表示問題及其搜索過程的一種方法。
問題的狀態空間表示
狀態空間方法：基于解答空間的問題表示和求解方法，它是以狀態和算符為基礎來表示和求解問題的。
主要包括：
- 狀態
- 算符
- 狀態空間
典型的例子：下棋、迷宮、各種游戲等。
狀態（ State ）
狀態是問題求解過程中每一步問題狀況的數據結構，一般用一組數據表示：
式中每個元素為集合的分量，稱為狀態變量。
- 每一個分量給予確定的值時，得到一個具體的狀態。
- 任何一種類型的數據結構都可以用來描述狀態，只要它有利于問題求解。
- 在程序中用字符、數字、記錄、數組、結構、對象等表示狀態。
算符（ Operator ）
當對一個問題狀態使用某個可用操作時，它將引起該狀態中某些分量值的變化，從而使問題從一個具體狀態變為另一個具體狀態。
- 算符可理解為狀態集合上的一個函數，它描述了狀態之間的關系。
- 算符可以是某種操作、規則、行為、變換、函數、算子、過程等。
- 算符也稱為操作，問題的狀態也只能經定義在其上的這種操作而改變。
問題的狀態空間（ Statespace ）
用來描述一個問題的全部狀態以及這些狀態之間的相互關系。
狀態空間常用一個三元組表示：
( S, F, G )- S ：為問題的所有初始狀態的集合
- F ：算符的集合
- G ：為目標狀態的集合
狀態空間圖
狀態空間可用有向圖來描述，圖的節點表示問題的狀態，圖的弧表示狀態之間的關系。
初始狀態對應于實際問題的已知信息，是圖中的根結點。
在問題的狀態空間描述中，尋找從一種狀態轉換為另一種狀態的某個操作算子序列等價于在一個圖中尋找某一路徑。
如下圖所示為用有向圖描述的狀態空間。
該圖表示對狀態 S0 允許使用算符 O1 ， O2 及 O3 ，分別使 S0 轉換為 S1 ， S2 及 S3 。
這樣一步步利用操作算子轉換下去，如 S10 ∈ G ，則 O2 ， O6 ， O10 就是一個解。
實踐-八數碼問題
在 3 × 3 的棋盤，擺有八個棋子，每個棋子上標有 1 至 8 的某一數字。 棋盤上還有一個空格，與空格相鄰的棋子可以移到空格中。
如何將棋盤從某一初始狀態變成最后的目標狀態？
八數碼問題的狀態
| X8 | X0 | X4 |
| X7 | X6 | X5 |
用向量 S =( X0, X1, X2, X3, X4, X5, X6, X7, X8 ) 表示狀態 Xi 為變量， Xi 的值就是方格 Xi 內的數字，取值為{ 0, 1, 2 … 8 }，其中 0 表示空格。
于是，向量 S 就是該問題的狀態表達式。
則上圖中的狀態變化為：
- 初始狀態： S0=(028345671)
- 目標狀態： Sg=(012345678)
八數碼問題的算符
制定操作算符集：
- 直觀方法一為每個棋牌制定一套可能的走步：左、上、右、下四種移動。這樣就需 32 個操作算子。
- 簡易方法一僅為空格制定這 4 種走步，因為只有緊靠空格的棋牌才能移動。空格移動的唯一約束是不能移出棋盤。
八數碼問題的狀態空間圖
- 從初始棋局開始，試探由每一合法走步得到的各種新棋局，然后再走一步而得到的下一組棋局。這樣繼續下去，直至達到目標棋局為止。
- 把初始狀態可達到的各狀態所組成的空間設想為一幅由各種狀態對應的節點組成的圖。 這種圖稱為狀態空間圖。
- 圖中每個節點是它所代表的棋局。首先把適用的算符用于初始狀態，以產生新的狀態；算符可以看成狀態空間圖的邊。
- 狀態空間的圖示形式稱為狀態空間圖（有向圖）。 其中圖的節點表示狀態，圖的邊表示算符問題求解過程就是尋求圖的某一路徑的問題，實際上是一個搜索過程。
比如我們從下面這個初始棋局開始：
繪制的八數碼問題的狀態空間圖（部分）如下所示：
總結
- 上一篇： alitum designer 的PCB
- 下一篇： Database-Mysql-关于文件打