状态空间表示法例题.ppt

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