人工智能作业一.doc

作业一1. 对于下列活动，分别给出任务环境的PEAS描述，并按照2.3.2节列出的性质进行分析:(a) 在互联网购买AI旧书Performance MeasureEnvironmentActuatorsSensors购买的旧书性价比高，搜索快速（货比三家），付款的安全性，好的交互功能（与卖家或其他买家沟通）互联网，卖家，其他买家购书平台（终端），计算机AI旧书价位比对系统(b) 对着墙壁练网球Performance MeasureEnvironmentActuatorsSensors动作准确度，反应迅速，动作连贯性，力度控制的精确度，对球落点控制的精确度训练场地，其他训练者，场地管理人员机械臂，球拍压力传感器，视觉传感器（判断球落点）(c) 在一次拍卖中对一个物体投标Performance MeasureEnvironmentActuatorsSensors对物体价值评估的准确性，反应迅速，制定投标价格的合理性被投标物体，其他竞投者，拍卖现场计算器（统计、计算），机械臂（用于投标）听觉传感器（感知其他竞投着报价），语音传感器（自己报价）2. 先建立一个完整的搜索树，起点是S,终点是G,如下图,节点旁的数字表示到达目标状态的距离，然后用以下方法表示如何进行搜索。图一首先，我们画出图一对应的完整的搜索树(按节点字母从小到大顺序依次画出)：(a).深度优先:我们知道深度优先搜索是无信息搜索，按照编程的习惯，下图中深度优先搜索的顺序是按照节点的A-G的排序进行的(b).广度优先:我们知道一般的广度优先搜索也是无信息搜索，按照编程的习惯，下图中广度优先搜索的顺序同样是是按照节点的A-G的排序进行的(c).爬山法:对于爬山法我们需要了解的是，它是简单的循环过程，不断向最优方向移动。该算法不需要维护搜索树，当前的节点的数据结构只需要记录当前状态和目标函数值。此外，爬山法不会考虑与当前状态不相邻的状态。从S出发，与S邻近最佳的状态为B，依次往下，一旦找到目标状态则算法终止，这也就是为什么爬山法容易陷入局部最优。(d).最佳优先:最佳优先算法的结点是基于评价函数f(n)去扩展的，评估价值最低的结点首先选择进行扩展。最佳优先算法和一致代价搜索算法实现类似，不同的是最佳优先是根据f值而不是根据g值对优先级队列排队。3. 图二是一棵部分展开的搜索树，其中树的边记录了对应的单步代价，叶子节点标注了到达目标结点的启发式函数的代价值，假定当前状态位于结点A。图二(a) 用下列的搜索方法来计算下一步需要展开的叶子节点。注意必须要有完整的计算过程，同时必须对扩展该叶子节点之前的节点顺序进行记录：1. 贪婪最佳优先搜索：首先，贪婪最佳优先算法是试图扩展离目标最近的节点，它只用到启发信息，也就是f(n)=h(n)。如图，h(B)是未知的，但是根据三角不等式，我们可以知道7=h(B)=13。因此，先扩展C结点。2. 一致代价搜索一致性代价搜索扩展的是路径消耗最小的结点。所以一致代价搜索接下来扩展结点的顺序为BDEFGHC3. A*树搜索A*搜索对结点的评估结合了g(n)，即到达此结点已经花费的代价，和h(n)，从该结点到目标结点所花的代价:f(n)=g(n)+h(n)。由于都是从A结点开始扩展，所以对于下一步可扩展的结点的f(D)=18，f(C)=21, 10=f(B)=16。因此，当先扩展B结点，否则先扩展D结点。(b) 讨论以上三种算法的完备性和最优性。贪婪最佳优先搜索试图扩展离目标最近的结点，理由是这样可以很快找到解。贪婪最佳优先搜索于深度优先搜索类似，即使是有限状态空间，他也是不完备的，容易陷入死胡同或者导致死循环；一致代价搜索按结点的最优路径顺序扩展结点，这是对任何单步代价函数都是最优的算法，它不再扩展深度最浅的结点。一致代价搜索与宽度优先搜索类似，是完备的；A*搜索是完备的，此外，A*算法对于任何给定的一致的启发函数都是效率最优的。4. 给定一个启发式函数满足h(G)=0,其中G是目标状态，证明如果h是一致的，那么它是可采纳的。一致性（单调性）的定义：如果对于每个结点n和通过任意行动a生成的n的每个后继结点n，从结点n到达目标的估计代价不大于从n到n单步的代价与从n到达目标的估计代价之和：h(n)=c(n,a,n)+h(n)可采纳性的定义：f(n)=g(n)+h(n)可采纳行要求f(n)永远不会超过结点n的解的实际代价证明：真实代价:f(n)=g(n)+c(n,a1,n1)+ c(n1,a2,n2)+ c(n2,a3,n3)+ c(nm,a(m+1),G)评估代价: f(n)=g(n)+h(n)即证明 f(n)=f(n)根据一致性的定义，有f(n)=g(n)+h(n)= g(n)+ c(n,a1,n1)+h(n1) = g(n)+ c(n,a1,n1)+ c(n1,a2,n2)+h(n2) =. = g(n)+c(n,a1,n1)+ c(n1,a2,n2)+ c(n2,a3,n3)+ c(nm,a(m+1),G)+h(G) =f(n)证毕