狀態(tài)空間表示法例題.ppt

要求：用盡可能少棋步能由初始狀態(tài)到達目標(biāo) 狀態(tài)。,例1 重排九宮問題,8 3 6 4 7 5,初始狀態(tài),1 2 3 8 4 7 6 5,目標(biāo)狀態(tài),一個老農(nóng)攜帶一只狐貍、一頭羊羔和一筐白菜，要從南岸過河到北岸。岸邊有一條小船，只有老農(nóng)自己能劃船，而且除了老農(nóng)以外，每次只能再帶一樣?xùn)|西過河。在整個渡河過程中，無論什么情況，若老農(nóng)不在場時，則不允許狐貍和羊羔單獨相處，否則羊羔會遭殃；羊羔也不得與白菜放在一起，否則羊羔會吃白菜。 請問，老農(nóng)如何才能把它們?nèi)堪踩珨[渡到北岸？,例2 農(nóng)夫過河問題,1.自然語言描述,1）老農(nóng)攜帶羊羔過河，把狐貍和白菜留在南岸； 2）老農(nóng)到達北岸，把羊羔留在北岸，并獨自回到南岸； 3）老農(nóng)攜帶狐貍過河，把白菜留在南岸； 4）老農(nóng)到達北岸，把狐貍留下，并帶上羊羔回到南岸； 5）老農(nóng)把羊羔留在南岸，攜帶白菜過河； 6）老農(nóng)到達北岸，把白菜和狐貍留在北岸，獨自回到南岸； 7）老農(nóng)最后攜帶羊羔過河，到達北岸。問題就此解決。,2.狀態(tài)和操作,用符號表示： M：代表老農(nóng)(farmer) F：代表狐貍(fox) L：代表羊羔(lamb) C：代表白菜(cabbage) S：表示在南岸 N：表示在北岸 S-N：表示從南到北 N-S ：表示從北到南,用（M，F(xiàn)，L，C）表示四個對象的一個狀態(tài),可有S和N兩個值； 改變狀態(tài)的操作，可分別用1，0表示。表示對象“在船上”和“不在船上”兩個值。 如：初始狀態(tài)：（S，S，S，S）， 終止?fàn)顟B(tài)：（N，N，N，N）， 中間狀態(tài)：S-N（1，1，0，0）,3.狀態(tài)約束分析,因老農(nóng)、狐貍、羊羔和白菜都有2種狀態(tài)，即在南岸和北岸，所以4個對象的總狀態(tài)數(shù)為2*2*2*2=16種，按條件要求，有幾種狀態(tài)不能存在，如表所示。所以只有10種可能狀態(tài)。,5.操作約束,根據(jù)題意，在10種可能的安全狀態(tài)里，只有4種 是有可能的操作： 1）老農(nóng)獨自過河（包括從南岸到北岸和從北岸到南岸，下同） 2）老農(nóng)攜帶狐貍過河 3）老農(nóng)攜帶羊羔過河 4）老農(nóng)攜帶白菜過河,6.問題求解過程的表示,N-S（1,1,0,0）,解：設(shè)立柱 1、2和3以及兩個圓盤A和B 。 用Sk=( Sk0, Sk1)表示問題狀態(tài)，Sk0表示圓盤A所在的立柱，Sk1表示圓盤B所在的立柱，全部可能的狀態(tài)共有九種： S0=( 1，1)， S1=( 1，2)， S2=( 1，3) S3=( 2，1)， S4=( 2，2)， S5=( 2，3) S6=( 3，1)， S7=( 3，2)， S8=( 3，3) 問題的初始狀態(tài)集合是S=S0，目標(biāo)狀態(tài)集合是G=S4，S8。,例3 二階梵塔問題(P53),算符: A( i,j):表示把A從第i號針移到第j號針上 B(i,j):表示把B從第i號針移到第j號針上 共12個算符: A(1,2), A(1,3), A(2,1) ,A(2,3), A(3,1),A(3,2) B(1,2), B(1,3), B(2,1), B(2,3), B(3,1), B(3,2),S0=（1，1）,S1=（1，2）,S2=（1，3）,S3=（2，1）,S4=（2，2）,S5=（2，3）,S6=（3，1）,S7=（3，2）,S8=（3，3）,二階梵塔問題狀態(tài)表示,二階梵塔狀態(tài)空間圖,M(盤符，i, j) 盤符=A,B i，j1，2，3,二階漢諾塔問題的狀態(tài)空間圖,假設(shè)有7個錢幣，任一選手只能將已分好的一堆錢幣分成兩堆個數(shù)不等的錢幣，兩位選手輪流進行，直到每一堆都只有一個或兩個錢幣，不能再分為止，哪個遇到不能分的情況，則就為輸。 假設(shè)對方先走，我方是否有必勝策略？,附錄 分錢幣問題,（7）,（6,1）,（5,2）,（4,3）,（5,1,1）,（4,2,1）,（3,2,2）,（3,3,1）,（4,1,1,1）,（3