本部分介绍《Artificial Intelligence： A modern approach》的第三部分，通过搜索进行问题求解，包括非启发式搜索和启发式搜索。
第三章 通过搜索进行问题求解
基于目标的agent：问题求解Agent和规划Agent，本部分介绍问题求解Agent。
包括：问题和解的描述；通用的搜索算法（无信息的（uninformed）和有信息的（informed）），本章假设问题的解是有固定的顺序的行动。
1 问题求解agent
假设一个agent要最大化一个性能度量——目标形式化；给目标定下需要考虑哪些行动和状态——问题形式化。暂时考虑环境是确定的和可以观察的，任务环境是离散的。
基于这些假设，问题的解总是一个行动的固定序列。为了求解这个序列，就需要过程搜索算法。
1.1 定义问题和解
一个问题包括如下5个部分：
Agent的初始状态
表述Agent可能的行动
转移模型：已知现在状态和动作，得到后继状态
目标测试：确定给定的状态是不是目标状态
路径耗散：为每条路径赋一个耗散值（代价），是单步耗散的总和
上述五个部分组成一个数据结构，作为问题求解算法的一个输入，问题的解就是从初始状态到目标状态的一组行动序列，解的质量由路径耗散函数度量，所有解中路径耗散最小的解即为最优解。
1.2 问题的形式化
对现实问题进行合理的抽象化，既不能太具体，导致问题过于复杂；又不能太抽象，不具备现实参考价值
2 问题实例
书中给了几个案例，本笔记没有给出。
3 通过搜索求解
解是一个行动序列，可能的行动序列是搜索树中根节点的初始状态出发，连线表示动作，节点表示问题状态空间中的状态。父节点出发可以得到子节点，叶节点是所有待扩展的节点。数搜索是无限的，因为包括环路，所以添加一个探索集，用于标注已经探索过的节点集合——图搜索。
3.1 搜索算法基础
需要一个数据结构用于记录搜索树的构造过程，对于每个节点，定义的数据结构包括：
n.STATE：对应搜索空间中的状态
n.PARENT：产生该节点的父节点
n.ACTION：父节点生成该节点时的动作
n.PATH-COST：从初始状态到达该节点的路径消耗。
节点VS状态：节点时用来表示搜索数的数据结构，状态对应于现实世界中的一个匹配。如果同一个状态可以通过两种不同的路径生成，则两个不同的节点包含同样的世界状态。
3.2 问题求解算法的性能
完备性：问题有解时，能否保证找到解
最优性：搜索策略能否找到最优解
时间复杂度：找到解需要花费多长时间
空间复杂度：在执行过程中需要多少内存。
度量标准：d，分支因子，任何节点的最多后继数；d，目标节点所在的最浅深度；m，状态空间中任何路径的最大长度。$C^\star$代表最优解的代价，假设每个行动的代价至少为$\epsilon$
4 无信息的搜索策略
有信息（启发式）：知道一个非目标状态是否比其他状态 “更有希望”接近目标。
| 宽度优先 | 代价一致 | 深度优先 | 深度受限 | 迭代加深 | 双向搜索 | |
|---|---|---|---|---|---|---|
| 完备性 | 是 | 是 | 是 | 否 | 是 | 否 |
| 最优性 | 是 | 是 | 否 | 否 | 是 | 否 |
| 时间复杂度 | $O(b^d)$ | $O(b^{1+[C^\star/\epsilon]})$ | $O(b^m)$ | $O(b^l)$ | $O(b^d)$ | $O(b^{d/2})$ |
| 空间复杂度 | $O(b^d)$ | $O(b^{1+[C^\star/\epsilon]})$ | $O(bm)$ | $O(bl)$ | $O(bd)$ | $O(b^{d/2})$ |
| 算法描述 | 先扩展根节点，然后扩展他们的后继，下一层的任何节点扩展之前，本层深度的节点都已经扩展完。 | 不在扩展深度最浅的节点，而是扩展路径消耗最小的节点。 | 扩展数的当前边缘节点集中最深的节点 | 对深度优先算法设置界限l | 不断增大深度限制，直到找到目标 | 从初始状态和目标开始双向搜索，希望在中点相遇 |
| 其他 | FIFO 目标测试在节点被生成时 空间消耗巨大 | 目标测试在节点被选择扩展时 在单步耗散相同时，$O(b^{d+1})$ | LIFO 回溯算法：只产生一个后继，内存!$O(m)$ | 根据先验知识，选择一个状态空间的直径 两种失败方式：无解，在深度界限内无解 | 首选算法 深度每增加一次，之前前几层算的状态就被重复（影响不大） | 两个小圆的面积比一个大圆（半径之和）要大 从目标开始搜不易实现； 没有明确的目标 |
5 有信息（启发式）的搜索策略
即使用问题本身之外的特定知识辅助搜索。
考虑最佳优先搜索策略，节点是基于评价函数值被选择扩展的，评价函数$f(n)$是一种代价估计。最佳优先策略和一致代价搜索类似，不过根据f值而不是g值对优先级进行排队。一般最优优先搜索算法的f由启发函数构成，启发函数是在搜索算法中利用问题额外信息的常见形式。
$h(n)$可采纳：$f(n)$不会高估到达目标的代价，即$f(n)$永远不会超过经过节点n的解的实际代价；
$h(n)$一致：$h(n)<= c(n,a,n’)+h(n’)$,即$h(n)$单调增加
| 贪婪最佳优先 | $A^*$搜索 | 存储受限 | 学习促进搜索 | |
|---|---|---|---|---|
| 完备性 | 否 | 是（h(n)一致） | ||
| 最优性 | 否 | 是（h(n)可采纳） | ||
| 时间复杂度 | $O(b^m)$ | |||
| 空间复杂度 | $O(b^m)$ | |||
| 算法描述 | $f(n) = h(n) $ 只扩展离目标最近的点 | 缩小总评估代价 $f(n)=g(n)+h(n)$ 评价函数是经过节点n的最小代价解的估计代价，扩展评价函数最小的节点 | 迭代加升+ $A^*$ | 元状态空间 |
| 其他 | 可能导致死循环，下降的幅度取决于特定的问题和启发式函数的质量 | 从起始点发散，以f值增长的同心带状的方式添加节点 |
6 启发式函数
6.1 启发式函数的精确度对性能的影响
有效分支因子：总结点数为N，解的深度为d，那么$b^{*}$是深度为d的标准搜索树为了能够包括N+1个节点所必须的分支因子，即：
$N+1 = 1 + b^*+ （b^）^2+ （b^）^3+ （b^）^4+……（b^）^d$
6.2 从松弛问题的角度出发设计可采纳的启发式
减少了行动限制的问题称为松弛问题，松弛问题的状态空间图是原有状态空间图的超图。松弛问题增加了状态空间的边，原有问题中的任一最优解同样是松弛问题的最优解，但是松弛问题可能纯在更好的解，因为增加的边可能导致捷径。因此，松弛问题的最优解代价是原问题的可采纳的启发式。
对不同的启发式集合，通过选取其中的最大值，构成新的启发式比所以的成员都更有优势。
6.3 从子问题出发设计可采纳的启发式：模式数据库
模式数据库就是对每个可能的子问题实例存储解代价，对搜索中遇到的每个完备状态计算其可采纳的启发式。
6.4 从经验中学习启发式
直接构造函数用于估计$h(n)$。这个函数在不断的求解问题过程中学习，最终实现预测探索过程中所出现的其他状态的解代价。可以使用神经网络和决策树等技术实现。
如果在状态描述外还能刻画给定状态的特征，则可以采用归纳学习的方法，通过回归等方法计算启发式。