第二章部分习题参考答案.docx

《第二章部分习题参考答案.docx》由会员分享，可在线阅读，更多相关《第二章部分习题参考答案.docx（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章部分习题参考答案: 6一个猎人要带着一只狼、一只羊、一捆草过河，但是人不在的时候，狼会吃羊、羊会吃草，猎人每次只能带一样东西过河。试用状态空间图求出他们能顺利过河的方案。 解：用四元组（f ，w ，s ，g ）表示状态，其中f 表示猎人，w 表示狼，s 表示羊，g 表示草，其中每个元素都可以为0或1，表示在左案，1表示在 右岸。四元组可表示的状态共有16种，其中合法状态为10种： （0，0，0，0）（0，0，0，1）（0，0，1，0）（0，1，0，0）（0，1，0，1） （1，0，1，0）（1，0，1，1）（1，1，0，1）（1，1，1，0）（1，1，1，1） 初始状态为（0，0，0，0

2、）目标状态为（1，1，1，1） 共有七种操作：从左岸到右岸三种，从右岸到左岸四种 操作符 条件 动作 p 1 f=0，w=0，s 和g 相异 f=1，w=1 p 2 f=0，s=0， f=1，s=1 p 3 f=0，g=0，w 和s 相异 f=1，g=1 q 0 f=1，s 和g 相异，w 和s 相异 f=0 q 1 f=1，w 1，s 和g 相异 f=0，w 0 q 2 f=1，s 1， f=0，s 0 q 3 f=1，g 1，w 和s 相异 f=0，g 0 (0,0,0,0)(1,0,1,0) p 2 q 2 (0,0,1,0)(1,1,1,0)p 1 q 1 (1,0,1,1) (0,0

3、,0,1)q 0 p 3 q 3(0,1,0,0) q 2p 2 (1,1,0,1)p 3 q 3 q 2 p 2 p 2 q 2 (0,1,0,1) (1,1,1,1) p 2 q 2 q 0 方案有两种：p2 q0 p3 q2 p2 q0 p2 p2 q0 p1 q2 p3 q0 p2 8.琴键翻动 （供参考）解：引入一个三元组(q0,q1,q2)来描述总状态，开状态为0，关状态为1，全部可能的状态为 ： Q0=(0,0,0) ; Q1=(0,0,1); Q2=(0,1,0) Q3=(0,1,1) ; Q4=(1,0,0); Q5=(1,0,1) Q6=(1,1,0) ; Q7=(1,1,

4、1)。 翻动琴键的操作抽象为改变上述状态的算子，即F a, b, c a:把第一个琴键q0翻转一次 b:把第二个琴键q1翻转一次 c:把第三个琴键q2翻转一次 问题的状态空间为 问题的状态空间图如下页所示：从状态空间图，我们可以找到Q5到Q7为3的两条路径，而找不到Q5到Q0为3的路径，因此，初始状态“关、开、关”连按三次琴键后只会出现“关、关、关”的状态。 6一个猎人要带着一只狼、一只羊、一捆草过河，但是人不在的时候，狼会吃羊、羊会吃草，猎人每次只能带一样东西过河。试用状态空间图求出他们能顺利过河的方案。 解：用四元组（f ，w ，s ，g ）表示状态，其中f 表示猎人，w 表示狼，s 表示

5、羊，g 表示草，其中每个元素都可以为0或1，表示在左案，1表示在 右岸。四元组可表示的状态共有16种，其中合法状态为10种： （0，0，0，0）（0，0，0，1）（0，0，1，0）（0，1，0，0）（0，1，0，1） （1，0，1，0）（1，0，1，1）（1，1，0，1）（1，1，1，0）（1，1，1，1） 初始状态为（0，0，0，0）目标状态为（1，1，1，1） 共有七种操作：从左岸到右岸三种，从右岸到左岸四种 操作符 条件 动作 p 1 f=0，w=0，s 和g 相异 f=1，w=1 p 2 f=0，s=0， f=1，s=1 p 3 f=0，g=0，w 和s 相异 f=1，g=1 q 0

6、f=1，s 和g 相异，w 和s 相异 f=0 q 1 f=1，w 1，s 和g 相异 f=0，w 0 q 2 f=1，s 1， f=0，s 0 q 3 f=1，g 1，w 和s 相异 f=0，g 0 (0,0,0,0)(1,0,1,0) p 2 q 2 (0,0,1,0)(1,1,1,0)p 1 q 1 (1,0,1,1) (0,0,0,1)q 0 p 3 q 3(0,1,0,0) q 2p 2 (1,1,0,1)p 3 q 3 q 2 p 2 p 2 q 2 (0,1,0,1) (1,1,1,1) p 2 q 2 q 0 方案有两种：p2 q0 p3 q2 p2 q0 p2 p2 q0 p

7、1 q2 p3 q0 p2 8.琴键翻动 （供参考）解：引入一个三元组(q0,q1,q2)来描述总状态，开状态为0，关状态为1，全部可能的状态为 ： Q0=(0,0,0) ; Q1=(0,0,1); Q2=(0,1,0) Q3=(0,1,1) ; Q4=(1,0,0); Q5=(1,0,1) Q6=(1,1,0) ; Q7=(1,1,1)。 翻动琴键的操作抽象为改变上述状态的算子，即F a, b, c a:把第一个琴键q0翻转一次 b:把第二个琴键q1翻转一次 c:把第三个琴键q2翻转一次 问题的状态空间为 问题的状态空间图如下页所示：从状态空间图，我们可以找到Q5到Q7为3的两条路径，而找不到Q5到Q0为3的路径，因此，初始状态“关、开、关”连按三次琴键后只会出现“关、关、关”的状态。