作业一。
1. 对于下列活动，分别给出任务环境的peas描述，并按照2.3.2节列出的性质进行分析：
a) 在互联网购买ai旧书。
b) 对着墙壁练网球。
c) 在一次拍卖中对一个物体投标。
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)证毕。
人工智能作业
人工智能 由自然探索于创新课程所想。管理学院李先同 201200272120 人工智能是一个大家看似并不陌生的字眼，我们平时所用的手机，电影中的科幻元素无不充斥着人工智能。由此人工智能变成为了一个人人都知道，却又都不甚了解的事物。通过这学期自然探索与创新课程的学习，我了解到了人工智能的发展简史，更对...
人工智能作业
2014 人工智能 作业 1 提交时间10 21 1 食草动物与食肉动物问题。3只食草动物与3只食肉动物在河一边，并有一条船。船能坐一至两只动物。船不能空载。目标是，把每只动物送到河对岸，并且留在某岸边或者船上的食肉动物数不能多于食草动物数。请将此问题转换成一个搜索问题 a.定义一个状态表示。b.给...
人工智能作业
1.何谓估价函数，在估价函数中，g n 和h n 各起什么作用？解 估价函数的任务是估计待搜索节点的重要程度，给它们排定次序。g n 是起始点到达n的实际路径代价，h n 就是n到目标点最短路径的启发函数。2.设有如下结构的移动将牌游戏 其中，b表示黑色将牌，w表是白色将牌，e表示空格。游戏的规定走...