人工智能：一种现代方法学习笔记（第三章）——启发式搜索
基本概念
最佳优先搜索的评价函数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，整个解路径的耗散值是路径中的步数。