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

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）目标状态为（1，1，1，1） 共有七种操作：从左岸到右岸三种，从右岸到左岸四种 操作符 条件 动作 p1 f=0，w=0，s和g相异 f=1，w=1 p2 f=0，s=0， f=1，s=1 p3 f=0，g=0，w和s相异 f=1，g=1 q0 f=1，s和g相异，w和s相异 f=0 q1 f=1，w＝1，s和g相异 f=0，w＝0 q2 f=1，s＝1， f=0，s＝0 q3 f=1，g＝1，w和s相异 f=0，g＝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,1)。翻动琴键的操作抽象为改变上述状态的算子，即F＝{a, b, c} a:把第一个琴键q0翻转一次 b:把第二个琴键q1翻转一次 c:把第三个琴键q2翻转一次问题的状态空间为{Q5},{Q0 Q7}, {a, b, c} 问题的状态空间图如下页所示：从状态空间图，我们可以找到Q5到Q7为3的两条路径，而找不到Q5到Q0为3的路径，因此，初始状态“关、开、关”连按三次琴键后只会出现“关、关、关”的状态。 11．代价树如图2-43所示。其中，F、I、 J、L是目标结点。 （1）不考虑代价，给出广度和深度优先有哪些信誉好的足球投注网站过程和解。 （2）考虑代价，分别给出分支界限法和瞎子爬山法有哪些信誉好的足球投注网站策略下的有哪些信誉好的足球投注网站过程和解。（参考启发式有哪些信誉好的足球投注网站的全局择优和局部择优算法） 不考虑代价，广度优先有哪些信誉好的足球投注网站过程：A－﹥ B－﹥ C－﹥ D－﹥E －﹥F，解为：A－﹥ C－﹥ F 深度优先有哪些信誉好的足球投注网站过程为：A－﹥ C－﹥ G－﹥M－﹥P－﹥O－﹥L 解为：A－﹥ C－﹥G－﹥L 分支界限法有哪些信誉好的足球投注网站过程：A－﹥ B－﹥ C－﹥G－﹥E－﹥L 解为：A－﹥ C－﹥G－﹥L 瞎子爬山法有哪些信誉好的足球投注网站过程：A－﹥ B－﹥ E－﹥J 解为：A－﹥ B－﹥E－﹥J .出图2-44与或树的解树，并用和代价法则求最佳解树。其中，端结点中，I、J、F、K、L是可解结点，其余结点是不可解结点。 ABDI，7 ABEJK，7 ACF 5 14. 博弈树如图2-46所示，分别用极小极大分析方法和(－(方法求N的最佳走步。 。 （0，0，0） （1，0，1） （0，0，1） （0，1，0） （1，1，0） （1，0，0） （0，1，0） （1，1，1） a c a b a c a b c b b c