作业一
1.考虑一个实时的在线电话翻译系统,该系统实现英语与日语之间的实时在线翻译,讨论该系统的性能度
量,环境,执行器,感知器,并对该环境的属性进行分析。
【Answer】
性能度量:翻译的正确率
环境:电话线路
传感器:麦克风
执行器:音响
完全可观察的,单age nt,确定的(无噪音条件下),片段的,静态的,离散的。
2.考虑一个医疗诊断系统的age nt,讨论该age nt最合适的种类(简单age nt,基于模型的age nt, 基于目标的
age nt和基于效用的age nt)并解释你的结论。
【Answer】
utility-based age nt。
能够治愈病人的方法有很多种,系统必须衡量最优的方法来推荐给病人
3.先建立一个完整的搜索树,起点是S终点是G,如下图,节点旁的数字表示到达目标状态的距离,然后用
以下方法表示如何进行搜索。
(a)?深度优先;
(b).宽度优先;
(c).爬山法;
(d).最佳优先;
图一
【Answer]:建立树:
深度: 宽度:
爬山法: 优先搜索:
4.图二是一棵部分展开的搜索树,其中树的边记录了对应的单步代价,叶子节点标注了到达目标结点的启
发式函数的代价值,假定当前状态位于结点A。
(a)用下列的搜索方法来计算下一步需要展开的叶子节点。注意必须要有完整的计算过
程,同时必须对扩展该叶子节点之前的节点顺序进行记录:
1.贪婪最佳优先搜索
2.一致代价搜索
3.A*树搜索
(b)讨论以上三种算法的完备性和最优性。
【Answer]:
贪婪最佳优先:如果h(B)>5,首先访问叶子结点C,如果h(B)<=5,首先访问B,再访问C 一致代价搜
索:B,D,E,F,G,H,C
A*树搜索:如果h(B)>15,首先访问D
如果h(B)<=15,首先访问B,在E,G,D,H,F,C
图
5.给定一个启发式函数满足h(G)=0,其中G是目标状态,证明如果h是一致的,那么它是
可米纳的。
【Answer ]:
假设n为任意一个状态,G是任意一个目标状态。n,n 1,n2,?…,nm,G为从状态n到达状态G的一条最优路
径,我们已知
评估代价f(n)=g(n)+h(n)
真实代价f' (n)=g(n)+c(n,a1,n1)+c(n1,a2,n2)+….c(nm,am+1,G) 目标:证明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(nm,am+1,G)+h(G)
=f ' (n)