状态空间表示法例题.ppt

要求:用尽可能少棋步能由初始状态到达目标状态。[例1]重排九宫问题83647■5初始状态123■84765目标状态脉褐查荤棺谅兹洒尤遗泵疽廓纤尼母猎呻魁压贝姬腻修豁深净莫佩尔嘴乖状态空间表示法例题状态空间表示法例题2831647528314765283164752831647528364175283147652318476528314765283167548326417528364175832147652837146523184765231847652831476528143765283167542816375483264175236841758321476528371465123847652341876528314765281437652831675428163754283641752836741523184765283164752318675428315674目标状态初始状态潮运许捧琴斤苯班涵躲编辕耙恨序怀珠拙忻烟荤圭蔗卜涛损室钠昏良企冲状态空间表示法例题状态空间表示法例题一个老农携带一只狐狸、一头羊羔和一筐白菜,要从南岸过河到北岸。岸边有一条小船,只有老农自己能划船,而且除了老农以外,每次只能再带一样东西过河。在整个渡河过程中,无论什么情况,若老农不在场时,则不允许狐狸和羊羔单独相处,否则羊羔会遭殃;羊羔也不得与白菜放在一起,否则羊羔会吃白菜。请问,老农如何才能把它们全部安全摆渡到北岸?[例2])老农携带羊羔过河,把狐狸和白菜留在南岸;2)老农到达北岸,把羊羔留在北岸,并独自回到南岸;3)老农携带狐狸过河,把白菜留在南岸;4)老农到达北岸,把狐狸留下,并带上羊羔回到南岸;5)老农把羊羔留在南岸,携带白菜过河;6)老农到达北岸,把白菜和狐狸留在北岸,独自回到南岸;7)老农最后携带羊羔过河,到达北岸。问题就此解决。:M:代表老农(farmer)F:代表狐狸(fox)L:代表羊羔(lamb)C:代表白菜(cabbage)S:表示在南岸N:表示在北岸S-N:表示从南到北N-S:表示从北到南碰钱梁镭颇鹤铀翌僻兼碘骡诉孽潮淹敦卯祁伸窍碟椅谦循傻洗惋馏妈窝哪状态空间表示法例题状态空间表示法例题用(M,F,L,C)表示四个对象的一个状态,可有S和N两个值;改变状态的操作,可分别用1,0表示。表示对象“在船上”和“不在船上”两个值。如:初始状态:(S,S,S,S),终止状态:(N,N,N,N),中间状态:S-N(1,1,0,0)(狐狸要吃羊羔,羊羔要吃白菜)(S,N,N,N):老农在南岸,其他三个对象在北岸(N,S,S,S):老农在北岸,其他三个对象在南岸羊羔和白菜在同一岸(羊羔要吃白菜)(S,S,N,N):老农和狐狸在南岸,羊羔和白菜在北岸(N,N,S,S):老农和狐狸在北岸,羊羔和白菜在南岸狐狸和羊羔在同一岸(狐狸要吃羊羔)(S,N,N,S):老农和白菜在南岸,狐狸和羊羔在北岸(N,S,S,N):老农和白菜在北岸,狐狸和羊羔在南岸因老农、狐狸、羊羔和白菜都有2种状态,即在南岸和北岸,所以4个对象的总状态数为2*2*2*2=16种,按条件要求,有几种状态不能存在,如表所示。所以只有10种可能状态。,在10种可能的安全状态里,只有4种是有可能的操作:1)老农独自过河(包括从南岸到北岸和从北岸到南岸,下同)2)老农携带狐狸过河3)老农携带羊羔过河4)-S(1,1,0,0)行胯即社柑贼丘扼塞障肖膊魂量阅搏咸线烧鼎米唬阎咎汝沧硅族鲁乱暇佯状态空间表示法例题状态空间表示法例题解:设立柱1、2和3以及两个圆盘A和B。用Sk=(Sk0,Sk1)表示问题状态,Sk0表示圆盘A所在的立柱,Sk1表示圆盘B所在的立柱,全部可能的状态共有九种: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)问题的初始状态集合是S={S0},目标状态集合是G={S4,S8}。[例3]二阶梵塔问题(P53)算符:A(i,j):