2023-12-04 22:00:00-0400
搜索是指提前规划并形成一个通往目标状态路径的动作序列，是一个前向计算的过程。
假设智能体能够访问与世界相关的信息，那么可以执行以下4个阶段的问题求解过程
解
(solution)搜索问题的形式化定义如下
一个动作序列形成一条路径 (path)，路径的代价是路径上所有动作的代价之和；解是从初始状态到目标状态的一条路径，解的代价是解的路径的代价；最优解是代价最小的解。
状态空间可以用图 (graph) 表示，图中的节点表示状态，图中的有向边表示动作，图中的边的属性/权重表示动作的代价。
搜索算法的输入是搜索问题，输出是一个解或者报告无解。事实上我们并不希望解中有重复的状态，因此一般可以在状态空间图上叠加一层搜索树 (search tree)，搜索树中的节点表示状态，根节点表示初始状态，搜索树中的有向边表示动作，搜索树中的边的属性/权重表示动作的代价，搜索树中的每个节点都有一个父节点，表示上一步的状态。
使用搜索树可以对节点进行扩展 (expand)，即从一个节点出发，根据转移模型和动作代价函数，生成该节点的所有子节点1，即下一步的可能状态。每一步的搜索都是通过扩展当前搜索树的叶子节点来进行的；已扩展过的节点对应的状态称为已达 (reached) 状态，未扩展过的节点是搜索树的边界 (frontier)。
树搜索和图搜索的区别是图搜索在扩展节点时需要检查节点是否已达，如果已达则不扩展该节点，这样可以避免重复扩展节点，但是需要额外的内存空间来存储已达状态；树搜索不需要检查节点是否已达，因此不需要额外的内存空间，但是可能会重复扩展节点，导致无限循环。
最佳优先搜索是一种比较通用的搜索方法，其重点在于评估函数 (evaluation function) \(f(n)\)，评估函数是一个从节点到实数的映射，表示从初始状态到目标状态的代价估计，最佳优先搜索每次都扩展评估函数值最小的节点。
在每次迭代过程，选择边界上\(f(n)\)最小的节点进行扩展:
一个树搜索 (tree search) 算法的实现需要以下数据结构:
class Node: # 树搜索中的节点
def __init__(self, state, parent=None, action=None, action_cost=0):
self.state = state # 节点对应的状态
self.parent = parent # 父节点，即上一步的状态
self.children = [] # 子节点，即下一步的状态表
self.action = action # 从父节点到该节点的动作
self.action_cost = action_cost # 从父节点到该节点的动作代价
self.path_cost = parent.path_cost + action_cost if parent else None # 从初始状态到该节点的路径代价
self.depth = 0 # 节点的深度
def path(self):
node, path_back = self, []
while node:
path_back.append(node.state) # 将节点的状态加入路径中
node = node.parent # 回溯到父节点
return list(reversed(path_back))
def cloeset_child(self):
if len(self.children) == 0: return None
else: return min(self.children, key=lambda x: x.action_cost) # 返回子节点中代价最小的节点
class Frontier:
def __init__(self):
self.container = [] # 用于存储边界上的节点
self.value = []
self.reached = {} # 用于存储已达状态
def empty(self): return len(self.container) == 0 # 判断边界是否为空
def add(self, node, list_type='priority', value=None):
list_type = list_type.lower()
if list_type == 'priority': # 优先队列，可用于最佳优先搜索
index = 0
while self.value[index] < value:
index += 1
self.container.insert(index, node) # 将节点加入边界中，按照路径代价从小到大排序
self.value.insert(index, value) # 将节点的评估函数值加入边界中，按照评估函数值从小到大排序
elif list_type == 'fifo': self.container.append(node) # 将节点加入边界中；先进先出队列，可用于宽度优先搜索
elif list_type == 'lifo': self.container.insert(0, node) # 将节点加入边界中；后进先出队列，可用于深度优先搜索
else: raise Exception('Invalid type')
def top(self):
if self.empty(): raise Exception('Frontier is empty')
else: return self.container[0] # 返回边界上的第一个节点
def pop(self):
if self.empty(): raise Exception('Frontier is empty')
else:
res = self.container[0] # 从边界中取出节点
self.container = self.container[1:] # 弹出边界中的第一个节点
return res
def __contains__(self, node): return any(node.state == n.state for n in self.container) # 判断节点是否在边界上
def __reached__(self, node): return node.state in self.reached # 判断节点是否已达搜索算法使用了3种不同类型的队列(存储边界上的节点):
已达状态可以存储为一个查找表 (lookup table)，例如哈希表 (hash table)，每个键值对的键是状态，值是该状态对应的节点。
循环是冗余路径的一种特殊情况，冗余路径是指从初始状态到目标状态的路径中包含重复的状态。解决冗余路径的方法有3种:
宽度优先搜索 (亦称广度优先搜索) 是一种树搜索算法，其使用先进先出队列作为边界，每次从边界中取出最早加入边界的节点进行扩展；当BFS扩展深度为d的节点时，说明深度为d-1的节点都已经扩展过了，因此BFS能找到一个路径最短的解。
def BFS(root, goal_state):
frontier = Frontier() # 边界，使用先进先出队列
frontier.add(root, type='fifo') # 将初始状态加入边界中
while not frontier.empty():
node = frontier.pop() # 从边界中取出节点
if node.state == goal_state: return node.path() # 若节点是目标状态，则返回该节点的路径
for child in node.children: # 扩展节点的子节点
child.parent = node # 将子节点的父节点设为该节点
frontier.add(child, type='fifo') # 将子节点加入边界中
return None # 若边界为空，则返回无解BFS的问题是空间复杂度很高，因为它需要存储边界上的所有节点，对内存的要求很高；BFS没有考虑动作的代价，因此它不一定是代价最优解。时间复杂度和空间复杂度都是指数级别的，即\(O(b^d)\)，其中\(b\)是分支因子，\(d\)是解的深度，因此BFS只适用于解的深度较小的问题。
一致代价搜索使用优先队列，每次从边界中取出路径代价最小的节点进行扩展；具体来说，每次迭代时，遍历边界上的节点和已达节点中尚有未扩展子节点的节点，选择路径代价最小的节点进行扩展。
def UCS(root, goal_state):
frontier = Frontier() # 边界，使用优先队列
frontier.add(root, type='priority', value=root.path_cost) # 将初始状态加入边界中
while True:
if frontier.empty(): return None # 若边界为空，则返回无解
node,child = min(
[(node,child) for node in frontier.container for child in node.closest_child()],
key=lambda x: x[1].path_cost # 从边界中取出路径代价最小的节点
)
node.children.remove(child) # 将子节点从父节点的子节点表中删除
if len(node.children) == 0: frontier.container.remove(node) # 若父节点的子节点表为空，则将父节点从边界中删除
child.parent = node # 将子节点的父节点设为该节点
if child.state == goal_state: return child.path() # 若节点是目标状态，则返回该节点的路径
frontier.add(child, type='priority', value=child.path_cost) # 将子节点加入边界中UCS是完备的，因为它会扩展所有的节点；UCS是代价最优的，因为它得到的第一个解的代价至少与边界上其他节点的代价一样小；一直代价搜索的时间和空间复杂度不小于BFS，当代价相同时，UCS退化为BFS。
深度优先搜索优先扩展深度最深的节点，因此使用后进先出队列2，评价函数可以看作节点深度的负数，这样深度越深，代价越低；深度优先搜索不一定能找到最优解，因为它可能会陷入局部最优解，因此他在树搜索中完备，但在图搜索中并不完备；在有环时，深度优先搜索可能会陷入无限循环。
def DFS(root, goal_state):
frontier = Frontier() # 边界，使用后进先出队列
frontier.add(root, type='priority', value=-root.depth) # 将初始状态加入边界中
while not frontier.empty():
node = frontier.pop() # 从边界中取出节点
if node.state == goal_state: return node.path() # 若节点是目标状态，则返回该节点的路径
for child in node.children: # 扩展节点的子节点
child.parent = node # 将子节点的父节点设为该节点
child.depth = node.depth + 1 # 将子节点的深度设为父节点的深度加1
frontier.add(child, type='priority', value=-child.depth) # 将子节点加入边界中
return None # 若边界为空，则返回无解
def Backtracking(node, goal_state):
if node.state == goal_state: return node.path() # 若节点是目标状态，则返回该节点的路径
for child in node.children: # 扩展节点的子节点
child.parent = node # 将子节点的父节点设为该节点
res = Backtracking(child, goal_state) # 递归调用回溯方法
if res is not None: return res # 若子节点是目标状态，则返回该节点的路径
return None # 若节点的所有子节点都不是目标状态，则返回无解深度优先的优点是空间复杂度较低，仅为\(O(bd_m)\)，其中\(b\)是分支因子，\(d_m\)是最大深度；回溯方法的空间复杂度更低，仅为\(O(d_m)\)，因为它不需要存储边界上的节点，只需要存储当前节点和父节点即可。
深度受限搜索 (depth-limited search) 是深度优先搜索的变体，其在深度达到限制时停止扩展节点，好处是防止陷入循环；深度限制搜索是不完备的，因为最大深度可能不够大，导致无法找到解。
迭代加深搜索 (iterative deepening search) 是深度限制搜索的变体，其在深度达到限制时停止扩展节点，但是会逐渐增加深度限制，直到找到解为止；迭代加深搜索是完备的；通常，当搜索状态空间大于内存容量而且解的深度未知时，迭代加深搜索是首选的无信息搜索方法。
同时从初始状态和目标状态开始搜索，直到两个搜索树相遇；每次迭代时扩展两个边界中代价最小的节点；双向搜索是完备的；双向搜索过程可以使用不同的搜索策略，如果使用BFS或UCS且动作代价全都相同，那么双向搜索是代价最优的
| 指标 | BFS | UCS | DFS | DLS | IDS | Bi-directional |
|---|---|---|---|---|---|---|
| 完备性 | 是 | 是 | 否 | 否 | 是 | 是 |
| 代价最优性 | 是3 | 是 | 否 | 否 | 是4 | 是 5 |
启发式搜索函数\(h(n)\)是从当前节点状态到目标状态的最小代价的估计
贪心最佳优先搜索使用优先队列，每次从边界中取出启发式函数值最小的节点进行扩展。如使用当前位置距目标位置的直线距离作为启发式函数，那么贪心最佳优先搜索会优先扩展离目标位置最近的节点。
A*搜索的评价函数是\(f(n)=g(n)+h(n)\)，其中\(g(n)\)是从初始状态到节点\(n\)的路径代价，\(h(n)\)是从节点\(n\)到目标状态的最小代价的估计，\(f(n)\)是从初始状态到目标状态的最小代价的估计；A*搜索使用优先队列，每次从边界中取出评价函数值最小的节点进行扩展；A*搜索是完备的；代价最优性取决于启发式函数\(h(n)\)的质量。
可容许 (admissible)的启发函数是指对于任意的节点\(n\)，有\(h(n)\leq h^*(n)\)，其中\(h^*(n)\)是从节点\(n\)到目标状态的最小代价的实际值；可容许的启发式函数的估计值不会超过实际值，因此可容许的启发式函数是比较保守的估计函数；可容许的启发函数一定是最优的，假设最优路径的代价是\(C^*\)，但是\(f(n)\)返回的代价\(C>C^*\)，并且\(n\)是最优路径上的一个节点:
\[ \begin{aligned} f(n) &= g(n) + h(n)&\\ f(n)&>C^*& \text{假设估计值大于最优解代价}\\ f(n)&=g^*(n)+h(n)&\text{从初始状态到节点n的路径代价是最优的}\\ f(n)&\leq g^*(n)+h^*(n)&\text{可容许的启发式函数的估计值不会超过实际值}\\ f(n)&\leq C^*&\text{由上一步推出，与假设矛盾}\\ \end{aligned} \]
一致性 (consistency) 是指对于任意的节点\(n\)和\(n\)的子节点\(n^{\prime}\)，有\(h(n)\leq Cost(n, n^{\prime})+h(n^{\prime})\)，即从节点\(n\)到目标状态的最小代价的估计不会超过从节点\(n\)到子节点\(n^{\prime}\)的代价加上从子节点\(n^{\prime}\)到目标状态的最小代价的估计，并且\(h(goal)=0\)；一致性是可容许的启发式函数的充分条件，即一致的启发式函数一定是可容许的启发式函数，是比可容许的启发式函数更强的条件。
\[ \begin{aligned} f(n^{\prime}) &= g(n^{\prime}) + h(n^{\prime})&\\ &= g(n) + Cost(n, n^{\prime}) + h(n^{\prime})&\\ &\geq g(n) + h(n)\\ &= f(n) \end{aligned} \]
一致的启发式函数下一步的估计值不会比当前节点的估计值更小，因此任一状态的估计值都不会超过目标状态的估计值，即解的实际值，所以一致的启发式函数是可容许的启发式函数。一致性类似于三角不等式，即从初始状态到目标状态的最小代价的估计值不会超过从初始状态到当前节点的代价加上从当前节点到目标状态的最小代价的估计值。
\[ \begin{aligned} h(n^i) &\leq Cost(n^i, n^{i+1}) + h(n^{i+1})&\\ &\leq Cost(n^i, n^{i+1}) + Cost(n^{i+1}, n^{i+2}) + h(n^{i+2})&\\ &\leq \underbrace{Cost(n^i, n^{i+1}) + \dots + Cost(n^{i+k-1}, n^{i+k})}_{h^*(n^i)} + \underbrace{h(n^{i+k})}_{0}&\\ \end{aligned} \]
由可容许性和一致性的证明可以得知，可容许的A*搜索是代价最优的，因为算法总是返回代价最小的解，即每次扩展时开表中总是有代价最小节点满足\(f(n)\leq C^*\)，其中\(C^*\)是最优解的代价。
类似地图中的等高线，搜索等值线是指所有代价相同的节点的集合，如果等值线的值为\(400\)，那么对所有等值线内的节点\(f(n)=g(n)+h(n)\leq 400\)；等值线的作用是可视化搜索，因为A*搜索扩展的是\(f(n)\)最小的节点，因此搜索等值线可以帮助我们理解搜索的过程。
实际已有代价\(g(n)\)是单调递增的，而\(g(n+1)=g(n)+Cost(n, n+1)\)，因此如果\(f(n)\)是一致的，那么\(f(n+1)=g(n+1)+h(n+1)=g(n)+Cost(n, n+1)+h(n+1)\geq g(n)+h(n)=f(n)\)，即\(f(n)\)是单调递增6的，因此搜索等值线是单调递增的。
假设最优路径代价是\(C^*\)，那么我们扩展的所有节点 (必然扩展节点) 都满足\(f(n)\leq C^*\)，因此搜索等值线的值不会超过\(C^*\)，即搜索等值线\(C^*\)外的节点都不会被扩展，因此搜索等值线\(C^*\)是最优解的边界；换句话说，A*搜索实现了对边界外的节点的剪枝。
满意解 (satisficing solution) 是指代价低于某个阈值的解，即考虑那些非最优解的次优解；满意搜索 (satisficing search) 是指搜索满意解的搜索算法。
受等值线的启发，我们可以将满意搜索看成对等值线的值的扩大7；一般地，我们令\(f(n)=g(n)+wh(n)\)，其中\(w\)是一个大于1的常数，\(h(n)\)是启发式函数，\(f(n)\)是从初始状态到目标状态的最小代价的估计；当\(w=1\)时，满意搜索退化为A*搜索。
使用加权搜索可能会扩大搜索空间，但同时也可能会降低搜索时间，因为增加了搜索的广度和解的数量。
局部搜索 (local search) 是指不考虑从初始状态到目标状态的路径，而是考虑如何从初始状态到目标状态的状态；局部搜索的优点是不需要存储整个状态空间，因此可以处理非常大的状态空间；局部搜索的缺点是可能会陷入局部最优解，因此局部搜索不一定能找到最优解。
爬山搜索 (hill-climbing search) 是一种局部搜索算法，其从初始状态开始，每次都扩展当前状态的最优子节点，直到达到局部最优解。
模拟退火8 (simulated annealing) 与爬山算法类似，不同点在于不选择最优解，而是以一定概率随机移动，具体来说:
扩展节点的优劣对应\(\Delta E\)的正负，\(\Delta E\)是当前节点与扩展节点的评价函数值的差，\(\Delta E<0\)表示扩展节点是一个坏解，使用指数函数将概率控制在\((0, 1)\)之间；此外还有一个随时间降低的温度参数\(T\)，\(T\)越大，接受劣解的概率越大，\(T\)越小，接受劣解的概率越小9。这个概率可以用玻尔兹曼分布 (Boltzmann distribution) 表示:
\[ P(\Delta E) = e^{\frac{\Delta E}{T}} \quad \Delta E < 0, T > 0 \]
局部束搜索 (local beam search) 是一种局部搜索算法，其从\(k\)个随机生成的状态开始，每次都扩展当前状态的全部子节点，然后选择其中最优的\(k\)个节点作为下一次迭代的初始状态，直到达到局部最优解。
局部束搜索不是简单的并行算法，因为\(k\)个搜索过程可以共享信息，例如全局最优或避免重复搜索。
graph TD
A[初始化种群] --> B[计算适应度]
B --> C[判断是否满足终止条件]
C --> |是| D[返回解]
C --> |否| E[选择]
E --> F[交叉]
F --> G[变异]
G --> B假设搜索问题的评估函数是连续可微的，其输入是一个n维向量\(x = (x_1, x_2, \dots, x_n)\)，对应n个变量，输出是一个实数\(f: \mathbb{R}^n \rightarrow \mathbb{R}\)，表示目标函数的值，目标函数是指需要优化的函数，例如最小化函数值；记\(\nabla f(x)\)为目标函数在\(x\)处的梯度:
\[ \nabla f(x) = \left(\frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial x_2}, \dots, \frac{\partial f}{\partial x_n}\right) \]
梯度下降法 (gradient descent) 是一种局部搜索算法，其使用梯度 (gradient) 的信息来指导搜索方向，梯度是一个向量，指向函数值增加最快的方向，梯度下降法的思想是沿着梯度的反方向进行搜索，直到达到局部最优解。
\[ x \leftarrow x + \alpha \nabla f(x) \]
牛顿法 (Newton’s method) 是一种局部搜索算法，其使用梯度和海森矩阵 (Hessian matrix) 的信息来指导搜索方向，海森矩阵是一个方阵，其第\(i\)行第\(j\)列的元素是\(\frac{\partial^2 f}{\partial x_i \partial x_j}\)，牛顿法的思想是沿着海森矩阵的逆矩阵的方向进行搜索，直到达到局部最优解。
\[ x\leftarrow x - H_f^{-1} \nabla f(x) \]
约束优化 (constrained optimization) 是指优化问题中存在约束条件的优化问题，例如线性规划 (linear programming) 问题；线性规划问题是凸优化 (convex optimization) 问题的一种特殊情况，凸优化问题是指目标函数是凸函数 (convex function) 的优化问题，凸函数是指函数的二阶导数大于等于0的函数。