状态空间表示法例题.ppt

要求：用尽可能少棋步能由初始状态到达目标状态。,例1重排九宫问题,836475,初始状态,12384765,目标状态,一个老农携带一只狐狸、一头羊羔和一筐白菜，要从南岸过河到北岸。岸边有一条小船，只有老农自己能划船，而且除了老农以外，每次只能再带一样东西过河。在整个渡河过程中，无论什么情况，若老农不在场时，则不允许狐狸和羊羔单独相处，否则羊羔会遭殃；羊羔也不得与白菜放在一起，否则羊羔会吃白菜。请问，老农如何才能把它们全部安全摆渡到北岸？,例2农夫过河问题,1.自然语言描述,1）老农携带羊羔过河，把狐狸和白菜留在南岸；2）老农到达北岸，把羊羔留在北岸，并独自回到南岸；3）老农携带狐狸过河，把白菜留在南岸；4）老农到达北岸，把狐狸留下，并带上羊羔回到南岸；5）老农把羊羔留在南岸，携带白菜过河；6）老农到达北岸，把白菜和狐狸留在北岸，独自回到南岸；7）老农最后携带羊羔过河，到达北岸。问题就此解决。,2.状态和操作,用符号表示：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）,3.状态约束分析,因老农、狐狸、羊羔和白菜都有2种状态，即在南岸和北岸，所以4个对象的总状态数为2*2*2*2=16种，按条件要求，有几种状态不能存在，如表所示。所以只有10种可能状态。,5.操作约束,根据题意，在10种可能的安全状态里，只有4种是有可能的操作：1）老农独自过河（包括从南岸到北岸和从北岸到南岸，下同）2）老农携带狐狸过河3）老农携带羊羔过河4）老农携带白菜过河,6.问题求解过程的表示,N-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):表示把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）,二阶梵塔问题状态表示,二阶梵塔状态空间图,M(盘符，i,j)盘符=A,Bi，j1，2，3,二阶汉诺塔问题的状态空间图,假设有7个钱币，任一选手只能将已分好的一堆钱币分成两堆个数不等的钱币，两位选手轮流进行，直到每一堆都只有一个或两个钱币，不能再分为止，哪个遇到不能分的情况，则就为输。假设对方先走，我方是否有必胜策略？,附录分钱币问题,（7）,（6,1）,（5,2）,（4,3）,（5,1,1）,（4,2,1）,（3,2,2）,（3,3,1）,（4,1,1,1）,（3,2,1,1）,（2,2,2,1）,（3,1,1,1,1）,（2,2,1,1,1）,（2,1,1,1,1,1）,对方先走,我方胜,对方胜,对方胜,分钱币问题的搏弈图,