状态空间表示法例题

要求：用尽可能少棋步能由初始状态到达目标状态。[例1]重排九宫问题83647■5初始状态123■84765目标状态12831647528314765283164752831647528364175283147652318476528314765283167548326417528364175832147652837146523184765231847652831476528143765283167542816375483264175236841758321476528371465123847652341876528314765281437652831675428163754283641752836741523184765283164752318675428315674目标状态初始状态2

一个老农携带一只狐狸、一头羊羔和一筐白菜，要从南岸过河到北岸。岸边有一条小船，只有老农自己能划船，而且除了老农以外，每次只能再带一样东西过河。在整个渡河过程中，无论什么情况，若老农不在场时，则不允许狐狸和羊羔单独相处，否则羊羔会遭殃；羊羔也不得与白菜放在一起，否则羊羔会吃白菜。请问，老农如何才能把它们全部安全摆渡到北岸？[例2]农夫过河问题31.自然语言描述1）老农携带羊羔过河，把狐狸和白菜留在南岸；2）老农到达北岸，把羊羔留在北岸，并独自回到南岸；3）老农携带狐狸过河，把白菜留在南岸；4）老农到达北岸，把狐狸留下，并带上羊羔回到南岸；5）老农把羊羔留在南岸，携带白菜过河；6）老农到达北岸，把白菜和狐狸留在北岸，独自回到南岸；7）老农最后携带羊羔过河，到达北岸。问题就此解决。42.状态和操作用符号表示：M：代表老农(farmer)F：代表狐狸(fox)L：代表羊羔(lamb)C：代表白菜(cabbage)S：表示在南岸N：表示在北岸S-N：表示从南到北N-S：表示从北到南5用（M，F，L，C）表示四个对象的一个状态,可有S和N两个值；改变状态的操作，可分别用1，0表示。表示对象“在船上”和“不在船上”两个值。如：初始状态：（S，S，S，S），终止状态：（N，N，N，N），中间状态：S-N（1，1，0，0）63.状态约束分析老农和其他三个对象不在同一岸（狐狸要吃羊羔，羊羔要吃白菜）

(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种可能状态。75.操作约束根据题意，在10种可能的安全状态里，只有4种是有可能的操作：1）老农独自过河（包括从南岸到北岸和从北岸到南岸，下同）2）老农携带狐狸过河3）老农携带羊羔过河4）老农携带白菜过河86.问题求解过程的表示

N-S（1,1,0,0）9解：设立柱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)10S0=（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）二阶梵塔问题状态表示11二阶梵塔状态空间图12M(盘符，i,j)盘符=A,Bi，j∈{1，2，3}二阶汉诺塔问题的状态空间图

13

假设有7个钱币，任一选手只能将已分好的一堆钱币分成两堆个数不等的钱币，两位选手轮流进行，直到每一堆都只有一个或两个钱币，不能再分为止，哪个遇到不能分的情况，则就为输。假设对方先走，我方是否有必胜策略？[附录