人工智能作业一.doc

作业一
1. 对于下列活动，分别给出任务环境的PEAS描述，并按照2.3.2节列出的性质进行分析:
(a) 在互联网购买AI旧书
Performance Measure
Environment
Actuators
Sensors
购买的旧书性价比高，搜索快速（货比三家），付款的安全性，好的交互功能（与卖家或其他买家沟通）
互联网，卖家，其他买家
购书平台（终端），
计算机
AI旧书价位比对系统

(b) 对着墙壁练网球
Performance Measure
Environment
Actuators
Sensors
动作准确度，反应迅速，动作连贯性，力度控制的精确度，对球落点控制的精确度
训练场地，其他训练者，场地管理人员
机械臂，球拍
压力传感器，视觉传感器（判断球落点）

(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)
证毕