人工智能:一种现代方法学习笔记(第三章)——启发式搜索

时间:2024-03-25 15:52:05

基本概念

人工智能:一种现代方法学习笔记(第三章)——启发式搜索
最佳优先搜索的评价函数f(n) 由启发函数(heuristic function)构成
h(n) = 结点n到目标结点的最小代价路径的代价估计值

人工智能:一种现代方法学习笔记(第三章)——启发式搜索

贪婪最佳优先搜索

使用启发式,f(n) = h(n)
距离目标最近,最快找到解
人工智能:一种现代方法学习笔记(第三章)——启发式搜索

人工智能:一种现代方法学习笔记(第三章)——启发式搜索
人工智能:一种现代方法学习笔记(第三章)——启发式搜索

A*搜索

人工智能:一种现代方法学习笔记(第三章)——启发式搜索
人工智能:一种现代方法学习笔记(第三章)——启发式搜索
人工智能:一种现代方法学习笔记(第三章)——启发式搜索
人工智能:一种现代方法学习笔记(第三章)——启发式搜索

从松弛问题出发设计可采纳的启发式

人工智能:一种现代方法学习笔记(第三章)——启发式搜索

减小了行动限制的问题称为松弛问题。松弛问题的状态空间图是原有状态空间的超图,因为减少限制导致图中边的增加。

从子问题出发设计可采纳的启发式——模式数据库

人工智能:一种现代方法学习笔记(第三章)——启发式搜索

子问题的最优解代价是完整问题的解代价的下界。存储每一个子问题代价的实例,作为启发式用。两个不想叫的子问题的代价之和是整个问题的下界(不相交的模式数据库)

从经验中学习启发式,线性回归方程等。

课后习题

3.1
人工智能:一种现代方法学习笔记(第三章)——启发式搜索

答:在制定目标时,我们决定我们对世界的哪些方面感兴趣,哪些方面可以被忽视或抽象化。然后,在问题描述中,我们决定如何操纵重要的方面(而忽略其他方面)。如果我们先制定问题,我们就不知道应该包括什么,也不知道遗漏了什么。也就是说,在目标制定、问题制定和问题解决之间有一个循环,直到一个人找到一个足够有用和有效的解决方案。

3.2
人工智能:一种现代方法学习笔记(第三章)——启发式搜索

答案A.我们将定义坐标系,使得迷宫的中心位于(0,0),迷宫本身是(1,1)到(1,1)的正方形。
初始状态:机器人在坐标(0,0),面向北。
目标测试:X>1或Y>1,其中(x,y)为当前位置。
行动:向前移动任何距离D;将方向机器人改变方向。
成本函数:移动的总距离。由于机器人的位置是连续的,所以状态空间是无限大的。

答案B.将记录机器人目前的交叉口的状态,以及它面临的方向。在每条走廊的尽头,离开迷宫,我们将有一个出口节点。我们假设某个节点对应于迷宫的中心。
初始状态:位于朝北迷宫中心。
目标测试:在出口节点。
行动:如果有一个交叉口,就移到前面的下一个十字路口;转向一个新的方向。
成本函数:总移动距离。有4N个状态,其中n是交叉口的数目。

答案C.
初始状态:在迷宫的中心。
目标测试:在退出节点处。
行动:移动到北、南、东或西的下一个交叉点。
成本函数:移动的总距离。
我们不再需要跟踪机器人的方位,因为它与预测我们的行动的结果无关,而且不是目标测试的一部分。执行该计划的电机系统需要跟踪机器人的当前取向,以知道何时旋转机器人。

答案D.
状态抽象:(i)忽略机器人离地面的高度,不管它是否从垂直方向倾斜。
(ii)机器人只能在四个方向上面对。
(iii)世界的其他部分被忽略:其他机器人在迷宫中的可能性,天气等。
动作抽象:(i)我们假设我们可以安全访问的所有位置:机器人无法卡住或损坏。
(ii)机器人可以无电源限制地移动。
(iii)简化的移动系统:向前移动一定距离,而不是控制每个单独的马达并观看传感器以检测碰撞。

3.6
人工智能:一种现代方法学习笔记(第三章)——启发式搜索
人工智能:一种现代方法学习笔记(第三章)——启发式搜索

状态:(V(a),V(b),V©);V(a),V(b),V©是各壶中水的体积;V(a)⋲Z,0<=V(a)<=12;V(b)⋲Z,0<=V(b)<=8;V©⋲Z,0<=V©<=3;

初始状态:V(a)=V(b)=V©=0

行动:这个任务环境中,每个状态可执行的行动共有12种。分别为:将a中的水倒入b中;将a中的水倒入c中;a中的水倒在地上;将a装满;将b中的水倒入a中;将b中的水倒入c中;b中的水倒在地上;将b装满;将c中的水倒入a中;将c中的水倒入b中;将c中的水倒在地上;将c装满。

转移模型:(V’(a),V’(b),V’©) = result(V(a),V(b),V©,action)
其中V(a),V(b),V©是执行动作前各壶中水的体积,action为执行的动作,V’(a), V’(b), V’©是执行动作后各壶中水的体积。
对于不同action,result函数计算公式如下:
1.将a中的水倒入b中。V’(a)=V(a)-min(8-V(b),V(a));V’(b)=V(b)+min(8-V(b),V(a));V’©=V©
2.将a中的水倒入c中。V’(a)=V(a)-min(3-V©,V(a));V’(b)=V(b);V’©=V©+min(3-V©,V(a))
3.a中的水倒在地上。V’(a)=0;V’(b)=V(b);V’©=V©
4.将a装满。V’(a)=12;V’(b)=V(b);V’©=V©
5.将b中的水倒入a中。V’(a)=V(a)+min(12-V(a),V(b));V’(b)=V(b)-min(12-V(a),V(b));V’©=V©
6.将b中的水倒入c中。V’(a)=V(a);V’(b)=V(b)-min(3-V©,V(b));V’©=V©+min(3-V©,V(b))
7.将b中的水倒在地上。V’(a)=V(a);V’(b)=0;V’©=V©
8.将b装满。V’(a)=V(a);V’(b)=8;V’©=V©
9.将c中的水倒入a中。V’(a)=V(a)+min(12-V(a),V©);V’(b)=V(b);V’©=V©-min(12-V(a),V©);
10.将c中的水倒入b中。V’(a)=V(a);V’(b)=V(b)+min(8-V(b),V©);V’©=V©-min(8-V(b),V©)
11.将c中的水倒在地上。V’(a)=V(a);V’(b)=V(b);V’©=0
12.将c装满。V’(a)=V(a);V’(b)=V(b);V’©=3

目标测试:V(a)=1 or V(b)=1 or V©=1

路径消耗:每一步耗散值为1,整个解路径的耗散值是路径中的步数。