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