人工智能作业一

作业一

1. 对于下列活动，分别给出任务环境的PEAS描述，并按照2.3.2节列出的性质进行分析:

(a) 在互联网购买AI旧书 Performance Environment Actuators Sensors Measure 购买的旧书性价比高，搜索快速（货比三家），付款的安全性，好的交互功能（与卖家或其他买家沟通） (b) 对着墙壁练网球 Performance Measure Environment Actuators 机械臂，球拍 Sensors 压力传感器，视觉传感器（判断球落点） 互联网，卖家，其他买家 购书平台（终端）， AI旧书价位比对计算机 系统 动作准确度，反应训练场地，其他训迅速，动作连贯性，练者，场地管理人力度控制的精确员 度，对球落点控制的精确度 (c) 在一次拍卖中对一个物体投标 Performance Measure Environment Actuators 计算器（统计、计算），机械臂（用于投标） Sensors 听觉传感器（感知其他竞投着报价），语音传感器（自己报价） 对物体价值评估的被投标物体，其他准确性，反应迅速，竞投者，拍卖现场 制定投标价格的合理性 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. 一致代价搜索

一致性代价搜索扩展的是路径消耗最小的结点。所以一致代价搜索接下

来扩展结点的顺序为BDEFGHC

3. 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) 证毕

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库人工智能作业一在线全文阅读。