状态空间表示法例题.ppt

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