状态空间表示法例题.ppt

要求：用尽可能少棋步能由初始状态到达目标 状态。,例1 重排九宫问题,8 3 6 4 7 5,初始状态,1 2 3 8 4 7 6 5,目标状态,一个老农携带一只狐狸、一头羊羔和一筐白菜，要从南岸过河到北岸。岸边有一条小船，只有老农自己能划船，而且除了老农以外，每次只能再带一样东西过河。在整个渡河过程中，无论什么情况，若老农不在场时，则不允许狐狸和羊羔单独相处，否则羊羔会遭殃；羊羔也不得与白菜放在一起，否则羊羔会吃白菜。 请问，老农如何才能把它们全部安全摆渡到北岸？,例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,B i，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