人工智能 现代方法 第三章读书笔记(持续更新）
占个位置
3.4无信息搜索策略
无信息搜索算法不提供有关某个状态与目标状态的接近程度的任何线索。
广度优先搜索(breadth-first search)
function Breadth-First-Search(problem)
returns 一个解节点或 failure
node ← Node(problem.Initial)
if problem.Is-Goal(node.State) then
return node
frontier ← 一个FIFO队列，其中一个元素为node
reached ←{problem.Initial}
while not Is-Empty(frontier)
do
node ← Pop(frontier)
for each child in Expand(problem,
node) do
s ← child.State
if problem.Is-Goal(s) then return
child
if s不在reached中 then
将s添加到reached
将child添加到frontier
return failure
优先队列（priority queue）首先弹出根据评价函数f 计算得到的代价最小的节点。它被用于最佳优先搜索。
FIFO 队列（FIFO queue），即先进先出队列（first-in-first-out queue），首先弹出最先添加到队列中的节点；它被用于广度优先搜索。
LIFO 队列（LIFO queue），即后进先出队列（last-in-first-out queue），也称为栈（stack），首先弹出最近添加的节点；它被用于深度优先搜索。
Dijkstra 算法或一致代价搜索
function Uniform-Cost-Search(problem)
returns 一个解节点或failure
return Best-First-Search(problem, Path-Cost)
function Best-First-Search(problem, f )
returns 一个解节点或 failure
node ← Node(State=problem.Initial)
frontier ← 一个以 f 排序的优先队列，其中一个元素为node
reached ←
一个查找表，其中一个条目的键为problem.Initial，值为node
while not Is-Empty(frontier)
do
node ← Pop(frontier)
if problem.Is-Goal(node.State) then return node
for each child in Expand(problem, node) do
s ← child.State
if s不在reached中 or child.Path-Cost reached[s].Path-Cost
then
reached[s] ← child
将child添加到frontier中
return failure
function Expand(problem, node) yields
节点
s ← node.State
for each action in problem.Actions(s)
do
s' ← problem.Result(s, action)
cost ← node.Path-Cost + problem.Action-Cost(s, action, s')
yield Node(State=s', Parent=node, Action=action,
Path-Cost=cost)
深度优先搜索（depth-first search）
function Depth-Limited-Search(problem, ℓ)
returns一个解节点或failure cutoff //当ℓ=∞
就是深度优先搜索
frontier ←
一个LIFO队列（栈），其中一个元素为Node(problem.Initial)
result ← failure
while not Is-Empty(frontier)
do
node ← Pop(frontier)
if problem.Is-Goal(node.State) then return
node
if Depth(node) ℓ then
result ← cutoff
else if not Is-Cycle(node)
do
for each child in Expand(problem,
node) do
将child添加到frontier
return result
function Iterative-Deepening-Search(problem)
returns 一个解节点或failure
for depth = 0 to ∞ do
result ← Depth-Limited-Search(problem, depth)
if result \(\neq\)
cutoff then return result
双向搜索
我们传入问题和评价函数的两个版本，一个是正向的（下标F），另一个是反向的（下标B）。当评价函数是路径代价时，找到的第一个解将是最优解，但是对于不同的评价函数，这一结论不一定是正确的。因此，我们会记录迄今为止找到的最优解，并且可能不得不多次更新最优解，直到Terminated
测试证明不可能再有
更好的解。
function BiBF-Search(problemF, fF, problemB, fB)
returns 一个解节点或 failure
node_F ← Node(problem_F.initial) // 初始状态节点
node_B ← Node(problem_B.initial) // 目标状态节点
frontier_F ← 按f_F排序的优先队列，其中一个元素为node_F
frontier_B ← 按 f_B排序的优先队列，其中一个元素为node_B
reached_F ←
一个查找表，其中一个条目的键是node_F.State且值是node_F
reached_B ←
一个查找表，其中一个条目的键是node_B.State且值是node_B
solution ← failure
while not Terminated(solution, frontier_F, frontier_B)
do
if f_F(Top(frontier_F)) f_B(Top(frontier_B))
then
solution ← Proceed(F, problem_F , frontier_F , reached_F, reached_B,
solution)
else solution ← Proceed(B, problem_B, frontier_B,
reached_B, reached_F, solution)
return solution
function Proceed(dir, problem, frontier, reached,
reached2, solution) returns一个解
/ / 在frontier上扩展节点，对照reached2中的另一个边界
/ / 变量dir是方向：要么是F（代表正向），要么是B（代表反向）
node ← Pop(frontier)
for each child in Expand(problem, node) do
s ← child.State
if s不在 reached 中 or Path-Cost(child)
Path-Cost(reached[s]) then
reached[s] ← child
//将child添加到frontier
if s不在reached2中 then
solution_2 ← Join-Nodes(dir, child, reached_2[s])
if Path-Cost(solution_2) Path-Cost(solution)
then
solution ← solution_2
return solution
Terminated测试怎么实现？
| 算法 | 采用队列和搜索 | 时间复杂度/空间复杂度 | 优点 /缺点 | 应用场景 |
|---|---|---|---|---|
| 广度优先搜索(breadth-first search) | 先进先出总能得到新节点 图搜索 | \(O(b^d)\)1 | 总能找到动作（深度）最少（浅）的解/需要很多内存和时间 | 所有动作的代价相同（把深度看作代价） |
| Dijkstra 算法或一致代价搜索 | 优先队列 图搜索 | \(O(b^{1+C^*/ \epsilon})\)2 | 一致代价搜索是完备的，也是代价最优的，因为它找到的第一个解的代价至少与边界上的任何其他节点的代价一样小。一致代价搜索会按照代价递增的顺序系统地考虑所有路径，而不会陷入一直沿单一无限路径探索的困境。 | 动作代价不同时（累加从根节点到当前节点的代价） |
| 深度优先搜索（depth-first search） | 树状搜索（不维护已达状态表） | \(O(b^m)\)/\(O(bm)\) | 内存小/不是最优解 且不完备容易陷入循环 | 节约内存 |
| 回溯搜索（backtracking search） | 树状搜索 | \(O(b^m)\)/\(O(m)\) | 节省大量资源，通过回溯，我们还可以为当前路径上的状态维护一个有效的集合数据结构，从而使检查循环的时间从\(O(m)\) 减少到\(O(1)\)。 | 回溯对许多具有大型状态描述的问题（例如机器人组装）的成功求解至关重要。 |
| 深度受限搜索（depth-limited search） | 树状搜索（不维护已达状态表）设置深度界限ℓ | \(O(b^ℓ)\)/\(O(bℓ)\) | 深度优先搜索的改进版本 | |
| 迭代加深搜索（iterative deepening search） | 存在解时\(O(b^d)\)/\(O(bd)\)不存在解时\(O(b^m)\) / \(O(bm)\) | 在搜索树顶端状态会被重复生成 | 解决了如何选择一个合适的的问题 | |
| 双向搜索（bidirectional search） | \(b^{d/2}+b^{d/2}\)要比\(b^d\)小得多 |
3.5 有信息（启发式）搜索策略
引入启发式函数（heuristic function) h(n) = 从节点n 的状态到目标状态的最小代价路径的代价估计值（它的来源后面的章节回讲）
贪心最佳优先搜索（greedy best-first search）
使用最优先搜索的方式 去评价函数f(n)=h(n)。例如寻径问题 我们用两地的直线距离\(h_{SLD}\)作为启发函数。对于这一特定问题，使用\(h_{SLD}\)的贪心最佳优先搜索无须扩展不在解路径上的节点就找到了解。但是，它找到的解并不是代价最优的。它保证了每一步最优但无法保证全局最优。其在有限空间是完备的，在无限空间是不完备的。最坏情况下时间复杂性和空间复杂性为O(|v|), 采用一个好的启发式函数，复杂性可以降低到O(bm)。
\(A^\ast\)搜索（\(A^\ast\) search）
\(A^\ast\) 搜索也是一种最佳优先搜索 评价函数取 f(n)= g(n)+h(n)。 g(n)是从初始状态到节点n的路径代价，h(n)是从节点n 到一个目标状态的最短路径的代价估计值。
\(A^\ast\) 搜索是完备的的 。它是否是代价最优则取决于启发式函数的性质。
可容许性（admissibility）一个可容许的启发式（admissible heuristic）函数永远不会高估到达某个目标的代价
一致性（consistency）\(h(n) \leq c(n,a,n^\prime)+h(n^\prime)\)
graph LR A((n))--"c(n,a,n')"--> B((n')) B -."h(n')".-> f A -."h(n)".-> f((G_n'))
一致的启发式函数都是可容许的（反过来不成立）。使用一致的启发函数 A*搜索的解总是最优的且第一次到达的状态就是最优解的路径。
搜索等值线 一种对搜索进行可视化的方法是在状态空间中绘制等值线（contour），就像在地形图中绘制等高线一样。
\(A^\ast\)之所以高效，是因为它会对那些对于寻找最优解没有帮助的搜索树节点进行剪枝（pruning）。对许多人工智能领域来说，剪枝（不必进行检查就可以排除不正确的答案）非常重要。需要注意的是\(A^\ast\)并不适用与所有搜索需求，它可能受困于过多的扩展节点数。
满意搜索：不可容许的启发式函数与加权\(A^\ast\) 搜索
虽然 \(A^\ast\)算法可以找到最优的解 但是代价需要扩展大量节点 ，如果我们退而求其次,接受一个来自不可容许（但更准确）的启发函数带来的次优的解,将花费更少的时间和空间的代价，这样的解我们也称之为满意的解。
我们采用一种称为加权\(A^\ast\)搜索（weighted \(A^\ast\) search）的方法，对启发式函数的值进行更重的加权，评价函数为\(f(n) = g(n) + W × h(n)\)，其中\(W\geq1\)。一般会找到一个介于\(W\times C^\ast\)与\(C^\ast\)之间的解。这种方法也被成为有界次优搜索（bounded suboptimal search），与之相反还存在无界代价搜索（unbounded-cost search），我们接受任何代价的解，只要能快速找到它。
内存受限搜索
束搜索（beam search）限定边界大小通过限定可扩展节点个数 或者只扩展 在最优f值一定范围内的节点数。
迭代加深\(A^\ast\)搜索（iterative-deepening \(A^\ast\) search，ID\(A^\ast\)） 每次迭代更新截断的f值，新的f截断值为超过上一次迭代截断值的节点中最小的f代价。换句话说，每次迭代都会彻底地搜索一个f 等值线，找到一个刚好超出该等值线的节点，并使用该节点的f 代价作为下一个等值线。
递归最佳优先搜索（recursive best-first search，RBFS）
使用$f_limit $变量跟踪从当前节点的任意祖先节点可得到的最优备选路径的f 值。如果当前节点超过了这个限制，那么递归将回到备选路径上。随着递归的展开，RBFS 将路径上每个节点的f 值替换为一个倒推值（backed-up value）——其子节点的最优f 值。通过这种方式，RBFS 可以记住被它遗忘的子树中最优叶节点的f 值，因此，在之后的某个时刻，RBFS 可以决定是否要重新扩展该子树。
function Recursive-Best-First-Search(problem)
returns 一个解或者failure
solution, fvalue ←
RBFS(problem, Node(problem.Initial), ∞)
return solution
function RBFS(problem, node, f_limit) returns
一个解或failure，以及一个新的 f代价限制
if problem.Is-Goal(node.State) then
return node
successors ← list(Expand(node))
if successors为空 then return
failure, ∞
for each s in successors
do //用前一次搜索中的值更新 f
s.f ← max(s.Path-Cost + h(s), node.f )
while true do
best ← successors 中 f 值最低的节点
if best. f >f_limit then return
failure, best. f
alternative ← successors中第二低的 f 值
result, best. f ← RBFS(problem, best, min(f_limit,
alternative))
if result\(\neq\)
failure then return result, best. f
有多少可用内存使用多少内存的算法 \(MA^\ast\)（memory-bounded \(A^\ast\)，内存受限的\(A^\ast\)）和\(SMA^\ast\)（simplified \(MA^\ast\)，简化的\(MA^\ast\)）。\(SMA^\ast\) 像\(A^\ast\)一样，但是当内存满时，它不在添加节点 除非它判断以后删除最老的最差叶节点。和RBFS 一样，SMA* 将被遗忘节点的值备份到其父节点。
双向启发式搜索
考虑启发函数的双向最佳优先搜索。正向搜索用\(f_F(n)=g_F(n)+h_F(n)\)作为评价函数，反向搜索用\(f_B(n)=g_B(n)+h_B(n)\)作为评价函数。他们拥有不同的评价函数。
解代价的下界
\[ lb(m,n)=max(g_F(m)+g_B(n),f_F(m),f_B(n)) \]
3.6 启发式函数
一种描述启发式函数质量的方法是有效分支因子（effective branching factor）\(b^\ast\)。如果针对一个特定问题，\(A^\ast\) 搜索所生成的总节点数是n，而解的深度是d，那么\(b^\ast\) 就是深度为d 的均衡树要包含n + 1 个节点所必需的分支因子。因此有
\[
n+1=1+b^\ast+(b^\ast)^2+...+(b^\ast)^d=\frac{1-(b^\ast)^{d+1}}{1-b^\ast}
\]
科尔夫和里德（Korf and Reid,
1998）提出了另一个刻画对于一个使用给定启发式函数h 的\(A^\ast\) 剪枝效果的概念:
相对于不使用启发函数的算法所用有效深度的减小量\(k_h\) ,即无信息搜索的代价为\(O(b^d)\) 使用启发函数后代价为\(O(b^{d-k_h})\) 。
对于同一个问题当一个启发函数\(h_1\) 在每个节点的值总是大于等于另一个启发函数\(h_2\) 时 我们说\(h_1\) 占优于 \(h_2\) 。
从松弛问题出发生成启发式函数
启发函数很重要 那么如何找到好的启发函数或者如何让计算机自动找到一个启发函数呢?我们可以通过求解一个原问题的松弛问题（relaxed problem）的最优代价解作为启发函数。所谓松弛问题就是减少动作限制的问题，它的状态空间比原问题多了一些边，可以简单的理解为是一个相对简化的问题。我们可以删除一两个条件构造松弛问题。
如果一个可容许的启发式函数集合\(h_1, …, h_m\) 可以求解同一个问题，但没有一个函数明显优于其他函数，那么我们应该选择哪个函数？事实证明，我们可以通过如下定义，得到最优的启发式函数：
\[
h(n)=max\left\{h_1(n),..,h_k(n)\right\}
\]
这种复合启发式函数将选择对于所讨论节点最准确的函数。因为\(h_i\) 都是可容许的，所以h
也是可容许的（如果\(h_i\)
都是一致的，则h 也是一致的）。此外，h
优于所有组成它的启发式函数。唯一的缺点是\(h(n)\)
的计算时间更长。如果考虑这一问题，另一种选择是在每次评价时随机选择一个启发式函数，或者使用机器学习算法来预测哪个启发式函数是最优的。这样做可能会导致启发式函数失去一致性（即使每个\(h_i\)
都是一致的），但在实践中，它通常能更快地求解问题。
从子问题出发生成启发式函数：模式数据库
模式数据库（pattern database）的思想是为每个可能的子问题存储准确的解代价。然后，通过在数据库中查找相应的子问题，为搜索过程中遇到的每个状态计算一个可容许的启发式函数\(h_{DB}\)。
子问题和松弛问题区别在于 子问题状态数小于原问题 ,而松弛问题状态数和原问题相同只是多了一些边。
当原问题可以被划分成若干个子问题且这些问题解不重叠 我们可以建立一个不相交模式数据库（disjoint pattern database）并且把其中每个子问题的解构成复合启发式函数。
使用地标生成启发式函数
为了减少搜索时间我们可以使用预计算（precomputation）技巧，比如 先花费时间计算各个顶点的最优路径存储下 以满足以后用户的搜索需求。
如果简单的进行每个顶点的预计算需要花费大量时间和储存是不太明智的。更好的方法是从顶点中选择一些（也许10 个或20 个）地标点（landmark point)L，然后计算存储各个顶点v到地标L的最优代价\(C^\ast(v,L)\)（以及地标到顶点的\(C^\ast(L,v)\) 对于无向图则不用），最后构造出
\[
h_L(n)= min C^\ast(n,L)+C^\ast(L,goal)
\]
\(h_L(n)\)是高效的，但不是可容许的。只要稍加注意，我们就可以提出一种既高效又可容许的启发式函数:
\[ h_{DH}(n)= max |C^\ast(n,L)-C^\ast(L,goal)| \]
这被称为差分启发式（differential
heuristic）函数（因为包含减法）。可以把它理解为在比目标还要远的某个位置设置一个地标点。如果目标恰好在从n
到该地标点的最优路径上，那么“考
虑从n 到L 的完整路径，然后减去这条路径的最后一部分，即从goal
到L，即可得到从n 到goal
的这段路径的准确代价”。如果目标稍微偏离到地标的最优路径，启发式函数将是不准确的，但仍然是可容许的。比目标近的地标是没有用的；例如，一个恰好位于n
和goal 正中间的地标将导致\(h_{DH} =
0\)，这是没有用的。
介绍几种选择地标点的方法。
- 贪心方法是随机选择第一个地标，然后找到离它最远的点，将其添加到地标集合中，接着在每次迭代中添加离最近地标最远的点。
- 如果通过用户过去的搜索请求日志，那么选择搜索中经常请求的地点作为地标。
- 对于差分启发式函数，地标分布在图的周界上更好。因此，一个比较好的技术是找到图的质心，围绕质心划分出k 个楔形（就像饼状图一样），并在每个楔形中选择离中心最远的顶点。
一些寻径算法通过在图中添加捷径（shortcut）——人工定义的对应于一条最优多行动路径的边——来节省更多的时间。
我们还可以人为考虑几个与问题有关的状态特征，然后把他们线性组合得到启发函数。
我们也可以期盼智能体从搜索过程中产生的搜索树序列（元级状态空间（metalevel state space））里学习优化搜索的方法 即元级学习（metalevel learning）
参考
Artificial Intelligence: A Modern Approach, Fourth Edition人工智能: 现代方法（第4 版）[ 美] 斯图尔特• 罗素（Stuart Russell） 著 彼得• 诺维格（Peter Norvig） 张博雅 陈坤 田超 顾卓尔 吴凡 赵申剑 译 张志华 审校 人 民 邮 电 出 版 社