1、圖搜索狀態空間圖11 狀態空間及其搜索的表示 1）狀態空間的表示 狀態空間以SP指示，其可表示為一個二元組： SP = （S, O） S在問題求解（即搜索）過程中所有可達的合法狀態構成的集合； O操作算子的集合，操作算子的執行導致狀態的變遷。 狀態空間又可描述為一個有向圖： 節點：指示狀態， 節點間的有向弧：表示狀態變遷， 弧上的標簽：指示導致狀態變遷的操作算子。 狀態可通過定義某種數據結構來描述，用于記載問題求解（即搜索）過程中某一時刻問題現狀的快照。 21 狀態空間及其搜索的表示2）狀態空間表示的經典例傳教士和野人問題 N個傳教士帶領N個野人劃船渡河， 安全約束： 1）船上人數不得超過載重

2、限量，設為K個人， 2）為預防野人攻擊，任何時刻（包括兩岸、船上）野人數目不得超過傳教士。 特例：N=3，K=2； 變量m傳教士在左岸或船上的實際人數， 變量c野人在左岸或船上的實際人數， 變量b指示船是否在左岸（1、0）。 上述約束條件轉變為m + c 2, m c。 左岸狀態描述為一個三元組： （m, c, b） 考慮到在這個渡河問題中，左岸的狀態描述（m, c, b）可以決定右岸的狀態，所以整個問題狀態就可以左岸的狀態來描述，以簡化問題的表示。 設初始狀態下傳教士、野人和船都在左岸，目標狀態下這三者均在右岸，問題狀態以三元組（m,c,b）表示。 32）狀態空間表示的經典例傳教士和野人問題

3、 問題求解任務可描述為： （3，3，1） （0，0，0） 該簡單問題的狀態空間： 可能的狀態總數為442 = 32 ， 只有20個狀態是合法的（遵守安全約束）， 不合法狀態， （1，0，1）， （1，2，1）， （2，3，1） 不可達的合法狀態（4個）， （0，0，1）， （0，3，0）。 總共只有16個可達的合法狀態。 2類操作算子： L(m,c)指示從左岸到右岸的劃船操作， R(m,c)指示從右岸回到左岸的劃船操作， m和c取值的可能組合只有5個：10，20，11，01，02。 總共有10個操作算子。 42）狀態空間表示的經典例傳教士和野人問題 渡河問題狀態空間的有向圖： 參見圖2.151

4、 狀態空間及其搜索的表示3）狀態空間的搜索 狀態空間的搜索以SE指示，其可表示為1個五元組： SE = (S,O,E,I,G) E搜索引擎； I問題的初始狀態，I S; G問題的目標狀態集，G S。 基本思想通過搜索引擎尋找一個操作算子的調用序列，使問題從初始狀態變遷到目標狀態之一。 解答路徑初-目變遷過程中的產生的狀態序列或相應的操作算子調用序列。 搜索引擎可以設計為任意實現搜索算法的控制系統。 狀態空間的解答路徑有多條，由于一個狀態可以有多個可供選擇的操作算子： 渡河問題就有無數條解答路徑（因為劃船操作可逆），但只有4條是最短的，都包含11個操作算子的調用。 狀態空間一般都表示為或圖也稱一

5、般圖 操作算子的可選（渡河問題的初始狀態節點就有3個），在邏輯上稱為“或”關系，意指只要其中有一條路徑通往目標狀態，就能獲得成功解答。除了少數像渡河這樣的簡單問題外，描述狀態空間的一般圖都很大，無法直觀地畫出，只能將其視為隱含圖。 搜索圖在搜索解答路徑的過程中只畫出搜索時直接涉及到的節點和弧線，構成所謂的搜索圖。 61 狀態空間及其搜索的表示4）一般圖搜索例八數碼游戲 33九宮棋盤，放置數碼為1 - 8的8個棋牌，剩下一個空格，只能通過棋牌向空格的移動來改變棋盤的布局。 求解的問題給定初始布局（即初始狀態）和目標布局（即目標狀態），如何移動棋牌才能從初始布局到達目標布局（參見圖2.2）。 解答

6、路徑就是一個合法的走步序列。 用一般圖搜索方法解決該問題： 為問題狀態的表示建立數據結構：33的一個矩陣， * 矩陣元素S ij0,1,8；其中1i,j3， * 數字0指示空格， * 數字1 - 8指示相應棋牌。 1 0 3 1 2 3 圖2.2中的八數碼問題就可表示為： 7 2 4 8 0 4 6 8 5 7 6 5 74）一般圖搜索例八數碼游戲 制定操作算子集：* 直觀方法為每個棋牌制定一套可能的走步： 左、上、右、下四種移動， 這樣就需32個操作算子。* 簡易方法僅為空格制定這4種走步， 因為只有緊靠空格的棋牌才能移動。* 空格移動的唯一約束是不能移出棋盤。 八數碼問題的搜索圖： 參見圖2.3 棋盤布局（問題狀態）總共9!=362880個， 但搜索圖小得多。81 狀態空間及其搜索的表示5）狀態空間、搜索