相关信息

本文的灵感来自于我最近在莫纳什大学 FIT3080 人工智能导论课程的课前预习。我将展示如何优雅地从图搜索算法推泛化出状态空间搜索。

引言

目标：展示经典单源最短路径算法 Dijkstra 如何抽象为"最佳优先搜索"框架，然后基于评估函数 $f(n)$ 演变为一系列状态空间搜索算法，包括 UCS、A*、加权 A*、贪婪搜索等。

背景场景：图最短路径 → 任意有限/可数状态空间 $S$ 上的成本最小化问题。

从 Dijkstra 算法到通用状态空间搜索的历程代表了计算机科学和人工智能中最优雅的泛化之一。最初作为在具有非负边权的图中寻找最短路径的具体算法，转变为能够解决大量优化问题的统一框架。

其核心教导我们一个基本教训：通过抽象掉图的具体结构，专注于搜索的基本组成部分——状态、动作、成本和目标——我们可以开发出不仅适用于道路网络或计算机网络，还能用于规划、调度、博弈、自动推理和无数其他领域的算法。

实现这种泛化的关键洞察是认识到 Dijkstra 算法本质上是最佳优先搜索的一个特例，其中"最佳"节点的扩展顺序仅由迄今产生的成本决定。通过修改这个评估函数以包含未来成本的估计（启发式），我们解锁了一系列在最优性、完备性和计算效率之间进行权衡的算法。

问题建模

状态空间搜索六元组

为了超越图进行泛化，我们需要一个描述搜索问题的形式化框架。状态空间搜索问题由六元组定义：

$$\mathcal{P} = \langle S,\,A,\,s_0,\,T,\,c,\,S_G\rangle$$

其中：

• $S$ 是有限或可数无限的状态集合
• $A(s) \subseteq A$ 是在状态 $s$ 中可用的动作集合
• $s_0 \in S$ 是初始状态
• $T: S \times A \to S$ 是转移函数，其中 $T(s,a)$ 给出在状态 $s$ 中应用动作 $a$ 得到的状态
• $c: S \times A \to \mathbb{R}^{\geq 0}$ 是成本函数，给出在状态 $s$ 中应用动作 $a$ 的非负成本
• $S_G \subseteq S$ 是目标状态集合

解决方案是将 $s_0$ 转换为某个 $s_g \in S_G$ 的动作序列 $a_1, a_2, ..., a_k$，总成本为 $\sum_{i=1}^{k} c(s_{i-1}, a_i)$，其中 $s_i = T(s_{i-1}, a_i)$。

图最短路径作为特例

经典图最短路径问题是一个特例，其中：

• $S = V$（图的顶点）
• $A(s) = \{(s,v) \mid (s,v) \in E\}$（从 $s$ 出发的边）
• $s_0$ 是源顶点
• $T(s,a) = v$，其中 $a = (s,v)$
• $c(s,a) = w(s,v)$（边权重）
• $S_G$ 是目标顶点（或目标集合）

这表明 Dijkstra 算法只是使用 $f(n) = g(n)$ 的最佳优先搜索，其中 $g(n)$ 是从起点到节点 $n$ 的成本。

超越图：状态空间示例

这种泛化的威力在考虑非图领域时变得明显：

拼图解决：对于 8 数码问题

• $S$：8 个块的所有可能配置
• $A(s)$：当前配置中可用的移动
• $c(s,a)$：每次移动为 1
• $S_G$：已解决的配置

路径规划：对于机器人导航

• $S$：可能的机器人配置 $(x,y,\theta)$
• $A(s)$：运动基元
• $c(s,a)$：时间/能量/距离
• $S_G$：目标配置

资源分配：

• $S$：资源到任务的分配
• $A(s)$：重新分配决策
• $c(s,a)$：重新分配成本
• $S_G$：完整、有效的分配

节点和三个成本函数

在状态空间搜索中，我们使用节点而不仅仅是状态。节点表示到状态的路径，包含搜索所需的额外信息。每个节点 $n$ 有三个相关的成本函数：

符号	含义	数学定义
$g(n)$	累积实际成本	从起始状态到节点 $n$ 状态的路径成本
$h(n)$	启发式估计	从节点 $n$ 状态到目标的估计最小剩余成本
$f(n)$	评估/排序键	算法选择的函数：$g$、$h$、$g+h$、$g+wh$ 等

理解 g(n)：迄今为止的路径

$g(n)$ 表示到达节点 $n$ 所代表状态已产生的实际成本。通过累加从初始状态沿路径的成本来计算：

$$g(n) = \sum_{i=1}^{k} c(s_{i-1}, a_i)$$

其中 $s_0, s_1, ..., s_k = s(n)$ 是从起点到节点 $n$ 的路径。

关键特性：

• $g(n)$ 是精确且已知的
• 初始节点的 $g(n_0) = 0$
• 对于非负成本，$g(n)$ 沿路径永不减少
• 在 Dijkstra/UCS 中，$f(n) = g(n)$——我们完全基于实际成本进行扩展

理解 h(n)：启发式估计

$h(n)$ 是一个启发式函数，估计从节点 $n$ 的状态到最近目标状态的成本。它表示帮助指导搜索的领域特定知识。

$$h(n) \approx \min_{s_g \in S_G} \text{cost}(s(n) \to s_g)$$

设计好的启发式：

• 可接受的：$h(n) \leq h^*(n)$，其中 $h^*(n)$ 是真实最优成本
• 一致的：$h(n) \leq c(n,a) + h(T(s(n),a))$ 对所有动作 $a$
• 信息丰富的：$h(n)$ 越接近 $h^*(n)$，指导效果越好

常见启发式模式：

• 距离度量：空间问题的欧几里得距离、曼哈顿距离、切比雪夫距离
• 松弛：解决问题的简化版本（例如，忽略障碍物）
• 模式数据库：子问题的预计算成本
• 地标启发式：通过中间"地标"状态的成本

理解 f(n)：评估函数

$f(n)$ 决定最佳优先搜索中节点的扩展顺序。$f(n)$ 的不同选择产生具有不同属性的不同算法：

$$f(n) = g(n) \text{ 和 } h(n) \text{ 的组合}$$

$f(n)$ 的作用：

• 平衡利用（使用已知成本 $g(n)$）与探索（使用估计 $h(n)$）
• 决定搜索策略：贪婪、最优或权衡
• 控制搜索空间的哪些部分被首先探索

常见 $f(n)$ 定义：

• $f(n) = g(n)$：Dijkstra/UCS——总是最优的
• $f(n) = h(n)$：贪婪最佳优先——快速但不是最优的
• $f(n) = g(n) + h(n)$：A*——使用可接受启发式时最优
• $f(n) = g(n) + w \cdot h(n)$：加权 A*——次优但更快

最佳优先搜索：统一算法

本质上，我们讨论的所有算法都是最佳优先搜索(BFS)的实例，它们按照 $f(n)$ 值的顺序扩展节点。以下是统一算法：

def best_first_search(problem, f):
    """使用评估函数 f 的最佳优先搜索"""
    
    # 使用起始节点初始化边界
    start_node = Node(state=problem.initial_state, 
                      g=0, 
                      parent=None)
    frontier = PriorityQueue(f)  # 按 f(n) 排序
    frontier.insert(start_node)
    
    # 跟踪到达的状态及其最佳 g 值
    reached = {problem.initial_state: 0}
    
    while not frontier.empty():
        # 提取具有最小 f 值的节点
        node = frontier.pop()
        
        # 检查是否已达到目标
        if node.state in problem.goal_states:
            return reconstruct_path(node)
        
        # 扩展节点
        for action in problem.actions(node.state):
            child_state = problem.transition(node.state, action)
            child_g = node.g + problem.cost(node.state, action)
            
            # 如果我们尚未到达此状态或找到更好的路径
            if (child_state not in reached or 
                child_g < reached[child_state]):
                
                reached[child_state] = child_g
                child_node = Node(state=child_state,
                                g=child_g,
                                parent=node)
                frontier.insert(child_node)
    
    return None  # 未找到解决方案

关键组件解释

1. 优先队列（边界）

• 存储要探索的节点，按 $f(n)$ 排序
• 不同的数据结构：二叉堆（$O(\log n)$）、斐波那契堆（$O(1)$ decrease-key）
• $f(n)$ 的选择决定搜索策略

2. 已到达/封闭集合

• 跟踪我们已经访问过的状态
• 防止无限循环和冗余工作
• 对于最优算法，我们存储每个状态的最佳 $g$ 值

3. 节点结构 每个节点包含：

• state：状态空间中的状态
• g：从起点开始的实际成本
• parent：指向父节点的指针（用于路径重建）
• 其他字段：动作、深度等

单调性条件

最优性的一个关键属性是单调性（也称为一致性）：

$$f(\text{parent}) \leq f(\text{child})$$

当这个条件成立时，我们第一次扩展节点时就找到了到达它的最优路径。这就是为什么：

• Dijkstra 算法（使用 $f=g$）对于非负权重是最优的
• 具有一致启发式的 A* 每个状态最多扩展一次
• 我们可以安全地剪枝先前扩展的状态

搜索树 vs 状态图

重要的是要理解最佳优先搜索构建的是搜索树，其中：

• 每个节点代表到状态的路径
• 多个节点可以表示相同的状态（具有不同的 $g$ 值）
• 树探索状态空间而不显式构建它

这与在显式表示的图上工作的图算法不同。在状态空间搜索中，我们通常：

• 即时生成邻居
• 永不构建完整的状态空间（通常是无限的）
• 使用启发式引导探索向有希望的区域

算法实例：不同评估函数的选择

通过改变评估函数 $f(n)$，我们获得具有不同属性的不同搜索算法。以下是综合比较：

• Dijkstra / UCS

  • $f(n)$ 定义：$g(n)$
  • 属性：完备 + 最优（边权 ≥ 0）
  • 复杂度：使用二叉堆为 $O((|V| + |E|)\log|V|)$
  • 关键特征：按从起点开始的实际成本顺序扩展节点

• A*

  • $f(n)$ 定义：$g(n) + h(n)$
  • 属性：完备 + 最优（如果 $h$ 可接受）
  • 复杂度：使用二叉堆为 $O((|V| + |E|)\log|V|)$
  • 关键特征：使用启发式引导向目标；使用可接受启发式时最优

• 加权 A*

  • $f(n)$ 定义：$g(n) + w \cdot h(n),\; w > 1$
  • 属性：完备，次优（≤ $w$ 倍最优）
  • 复杂度：使用二叉堆为 $O((|V| + |E|)\log|V|)$
  • 关键特征：通过牺牲最优性加速搜索；实时规划中常见

• 贪婪 BFS

  • $f(n)$ 定义：$h(n)$
  • 属性：完备（有限状态空间），非最优
  • 复杂度：$O(b^d)$
  • 关键特征：扩展最少节点；快速但无最优性保证

• $\varepsilon$-一致 A*

  • $f(n)$ 定义：$\max\{g(n)+h(n), (1+\varepsilon)g(n)\}$
  • 属性：完备，$(1+\varepsilon)$-最优
  • 复杂度：使用二叉堆为 $O((|V| + |E|)\log|V|)$
  • 关键特征：理论-实践折衷；限制次优性

Dijkstra / 一致成本搜索 (UCS)

何时使用：当您需要保证最优性且没有用于启发式的领域知识时。

行为：

• 按增加的路径成本从起点开始扩展节点
• 像水填充盆地——向所有方向均匀探索
• 对于非负边权是最优的
• 对于大型状态空间可能很慢

# Dijkstra/UCS 只是最佳优先搜索，使用：
f = lambda n: n.g

A* 搜索

何时使用：当您有好的可接受启发式且需要最优性时。

行为：

• 平衡实际成本（$g$）与估计剩余成本（$h$）
• 将搜索集中在有希望的区域
• 使用可接受启发式：比 UCS 扩展更少节点同时保持最优性
• 启发式搜索的"黄金标准"

关键洞察：$f(n) = g(n) + h(n)$ 估计通过节点 $n$ 的解决方案的总成本。通过扩展具有最小 $f(n)$ 的节点，A* 专注于最有希望的完整路径。

加权 A*

何时使用：当最优性可以为速度牺牲时。

行为：

• 对于 $w > 1$，过度加权启发式，使搜索更"贪婪"
• 更快地找到解决方案，但具有 $w$ 的次优性界限
• 当 $w \to \infty$ 时，行为接近贪婪 BFS
• 在实时应用中常见，其中：
  • 规划时间有限
  • 接近最优的解决方案是可接受的
  • 环境是动态的

贪婪最佳优先搜索

何时使用：当任何解决方案都可接受且速度至关重要时。

行为：

• 忽略迄今的路径成本；纯粹专注于启发式
• 在某些情况下可以非常快速地找到解决方案
• 可能找到非常长、昂贵的路径
• 无最优性保证

示例：在使用直线距离启发式的路线规划中：

• 贪婪 BFS 可能采取直接朝向目标的小路
• 错过附近会快得多的高速公路

Epsilon-一致 A*

何时使用：当您想要有界次优性且比加权 A* 更好的性能时。

行为：

• 保证在最优的 $(1+\varepsilon)$ 范围内的解决方案
• 对于相同的次优性界限通常比加权 A* 表现更好
• 使用更复杂的评估函数

可视化搜索行为

考虑在东北角有目标的 2D 网格中搜索：

起点 ->  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
          .  #  #  #  #  .  .  .  .  .  .  .  .  .  .
          .  .  .  .  #  .  .  .  .  .  .  .  .  .  .
          .  .  .  .  #  .  .  .  .  .  .  .  .  .  .
          .  .  .  .  #  .  .  .  .  .  .  .  .  .  .
          .  .  .  .  #  #  #  #  #  .  .  .  .  .  .
          .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
          .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
          .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
          .  .  .  .  .  .  .  .  .  .  .  .  .  .  G

• UCS：以以起点为中心的菱形模式扩展
• 贪婪 BFS：直接朝向目标成线扩展
• A*：专注于最优路径的椭圆扩展
• 加权 A*：更集中于朝向目标的椭圆

这种可视化有助于理解不同的 $f(n)$ 函数如何塑造搜索前沿。

关键抽象：从图到通用搜索

从图算法到状态空间搜索的泛化涉及几个关键的概念转变。理解这些抽象是掌握启发式搜索算法的关键。

节点 ≠ 状态：关键区别

在图算法中，我们通常处理顶点。在状态空间搜索中，我们使用节点，其中：

• 状态是世界的配置
• 节点代表到状态的路径，包括：
  • 状态本身
  • 到达它的成本（$g$ 值）
  • 用于路径重建的父指针
  • 其他元数据（深度、采取的动作等）

为什么这很重要：多个节点可以表示具有不同成本的相同状态：

路径 1: S → A → B → C  (成本: 10)
路径 2: S → D → E → C  (成本: 8)

两者都结束于状态 C，但代表不同的路径

这种区别允许我们：

• 找到最优路径（通过保持最佳 $g$ 值）
• 处理具有循环的状态空间
• 支持改进解决方案的随时算法

启发式的力量

启发式是使状态空间搜索对大型问题实用的关键。它们提供指导搜索的领域特定知识。

启发式从哪里来？

1. 问题松弛：移除约束以获得更简单的问题

   • 8 数码：允许块相互移动通过
   • 路线规划：忽略障碍物
   • 松弛问题的最优成本是有效的启发式

2. 模式数据库：预计算子问题的成本

   • 存储解决 8 数码中块子集的成本
   • 组合多个模式数据库以获得更好的估计

3. 地标：识别解决方案必须访问的中间状态

   • "必须通过检查点 A"
   • 求和到地标和从地标的成本

4. 距离度量：对于空间问题

   • 欧几里得距离：$\sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}$
   • 曼哈顿距离：$|x_2-x_1| + |y_2-y_1|$
   • 切比雪夫距离：$\max(|x_2-x_1|, |y_2-y_1|)$

启发式设计权衡：

• 太松：指导差，搜索行为像 UCS
• 太紧（高估）：可能错过最优解决方案
• 正好：紧的可接受启发式 → 最优且扩展少

已到达/封闭集合：管理访问过的状态

reached 集合（在某些实现中为 closed 列表）对于效率和正确性至关重要。

它存储什么：

• 对于每个状态：迄今找到的最佳 $g$ 值
• 允许我们检测何时找到了到状态的更好路径

何时更新：

• 当我们找到到已访问状态的更低成本路径时
• 这在最佳优先搜索中自然发生，检查：

  if child_state not in reached or child_g < reached[child_state]:
      # 找到了更好的路径！

对于非最优算法：

• 贪婪搜索可能仍希望避免重新访问状态
• 但这样做可能错过更短的路径
• 完备性与效率之间的权衡

搜索空间生成：即时扩展

与在显式图上工作的图算法不同，状态空间搜索通常：

• 按需生成邻居
• 永不构建完整的状态空间
• 可以处理无限或极大的状态空间

示例：国际象棋约有 $10^{46}$ 个合法位置

• 不可能显式存储
• 但 A* 可以使用好的启发式搜索将死

这种惰性方法使许多复杂问题变得可处理，而这些问题用显式表示是不可能的。

作为探索"波"的边界

将边界视为通过状态空间传播的波：

• 波的形状取决于 $f(n)$
• UCS：圆形波（向所有方向均匀）
• A*：朝向目标拉伸的椭圆波
• 贪婪：专注于目标的窄光束

这个波隐喻有助于理解：

• 为什么某些算法更快地找到解决方案
• 启发式如何集中搜索
• 探索与利用之间的关系

理论属性：理解保证

为了有效使用这些算法，我们需要理解它们的理论保证。什么时候我们可以信任算法会找到解决方案？什么时候它是最优的？

可接受 vs 一致启发式

两个关键属性决定启发式搜索算法的行为：

可接受启发式：永不高估到目标的真实成本

$$0 \leq h(n) \leq h^*(n) \quad \text{对于所有 } n$$

其中 $h^*(n)$ 是从状态 $n$ 到目标的真实最优成本。

一致启发式（也称为单调）：满足三角不等式

$$h(n) \leq c(n,a) + h(T(s(n),a)) \quad \text{对于所有 } n, a$$

关键关系：

• 一致 $\Rightarrow$ 可接受（但反之不成立）
• 一致启发式是"局部可接受的"
• 对于一致启发式：$f(n)$ 沿任何路径是非递减的

为什么一致性很重要

一致启发式给我们重要属性：

1. A* 的最优性：使用一致启发式，A* 是最优的
2. 效率：每个状态最多扩展一次
3. 单调性：$f$ 值沿路径永不减少
4. 剪枝：我们可以安全地忽略先前扩展的状态

示例：网格导航的曼哈顿距离是一致的：

• 移动一步将曼哈顿距离恰好改变 1
• 所以 $h(n) \leq 1 + h(\text{邻居})$ 成立

非一致但可接受的示例：到目标的直线距离

• 可接受（永不高估）
• 但如果存在障碍物可能违反一致性

完备性和最优性

算法	完备？	最优？	条件
UCS/Dijkstra	是（有限 $S$，$c \geq 0$）	是（$c \geq 0$）	非负成本
A*	是（有限 $S$，$c \geq 0$）	是	$h$ 可接受
A*	是（有限 $S$，$c \geq 0$）	是	$h$ 一致
加权 A*	是	否	在最优的 $w$ 范围内
贪婪 BFS	是（有限 $S$）	否	-

完备性：如果存在解决方案，算法会找到它吗？

• 对于具有非负成本的有限状态空间：我们的所有算法都是完备的
• 对于无限空间：取决于启发式和分支因子

最优性：算法会找到最低成本的解决方案吗？

• 只有 UCS 和 A*（使用可接受启发式）保证最优性
• 其他算法为了速度牺牲最优性

复杂度分析

最佳优先搜索的时间复杂度取决于：

1. 扩展的节点数量
2. 优先队列操作的成本

最坏情况复杂度（二叉堆）：

• UCS/A* 的 $O((|S| + |E|) \log |S|)$
• 与 Dijkstra 算法相同

但是——这种最坏情况在实践中很少重要！

• 好的启发式可以指数级减少扩展的节点
• 在最好的情况下，A* 只扩展最优路径上的节点

空间复杂度：

• 优先队列的 $O(|S|)$
• 对于大型问题可能令人望而却步
• 这导致了迭代深化变体的开发

A* 最优性证明

为什么使用可接受启发式的 A* 是最优的？这是直觉：

1. 假设 A* 首先找到次优解决方案
2. 设 $n$ 是最优路径上尚未扩展的节点
3. 由于 $h$ 是可接受的：$f(n) = g(n) + h(n) \leq \text{最优成本}$
4. 但次优解决方案的成本 $>$ 最优成本
5. 所以 $f(n) <$ 找到的解决方案的成本
6. 矛盾：A* 会先扩展 $n$

实际含义

对于算法选择：

• 需要保证最优性？使用具有可接受启发式的 A*
• 没有好启发式？使用 UCS/Dijkstra
• 速度比最优性更重要？使用加权 A* 或贪婪
• 有一致启发式？可以使用高效实现

对于启发式设计：

• 从可接受启发式开始（保证最优性）
• 如果可能，使它们一致（提高效率）
• 考虑多个启发式并取最大值
• 记住：更紧的界限 $\rightarrow$ 更少的扩展

理解这些理论基础有助于：

• 为您的问题选择正确的算法
• 设计有效的启发式
• 当算法行为不预期时进行调试
• 证明您开发的新算法的属性

进一步泛化：超越基本 A*

最佳优先搜索框架可以在许多方向扩展以处理更复杂的场景。以下是一些重要的泛化：

加权 / 随时 A*

问题：基本 A* 找到最优解决方案但可能很慢 解决方案：动态调整权重 $w$ 以快速找到好的解决方案，然后改进它们

def anytime_astar(problem, initial_weight=5.0, decay_rate=0.95):
    """具有递减权重的随时 A*"""
    weight = initial_weight
    best_solution = None
    best_cost = infinity
    
    while True:
        # 使用当前权重运行加权 A*
        solution = weighted_astar(problem, weight)
        
        if solution and solution.cost < best_cost:
            best_solution = solution
            best_cost = solution.cost
            yield best_solution  # 返回改进的解决方案
        
        # 为下一次迭代减少权重
        weight *= decay_rate
        
        if weight <= 1.0:
            break  # 达到最优 A*
    
    # 最终运行最优 A*
    final_solution = astar(problem)
    yield final_solution

应用：

• 需要快速初始解决方案的实时系统
• 解决方案质量可以随时间改进的问题
• 具有不明确时间限制的情况

多目标搜索

问题：现实问题通常有多个竞争目标

• 最快路线 vs 最安全路线 vs 最风景优美的路线
• 成本 vs 时间 vs 环境影响

解决方案：找到帕累托最优解决方案——在不恶化另一个目标的情况下无法改进一个目标的解决方案

方法：

1. 标量化：组合目标：$f(n) = w_1 \cdot g_1(n) + w_2 \cdot g_2(n) + ...$
2. 帕累托 A*：维护多个边界，每个帕累托点一个
3. 字典序排序：按优先顺序优化目标

def multi_objective_astar(problem, objectives):
    """具有帕累托边界的多目标 A*"""
    frontier = PriorityQueue()  # 可能需要多个队列
    pareto_frontier = {}  # 状态 -> 非支配成本向量集合
    
    while frontier:
        node = frontier.pop()
        
        if is_goal(node.state):
            add_to_pareto_set(pareto_solutions, node)
        
        for child in expand(node):
            if not is_dominated(child.costs, pareto_frontier):
                frontier.add(child)
                update_pareto_frontier(pareto_frontier, child)

概率和风险敏感搜索

问题：成本可能不确定或随机

• 有交通的旅行时间
• 动作成功概率
• 风险规避 vs 风险寻求行为

解决方案：修改评估函数以考虑不确定性

方法：

1. 期望效用：$f(n) = \mathbb{E}[g(n)] + \mathbb{E}[h(n)]$
2. 风险敏感：$f(n) = \mathbb{E}[g(n)] + \lambda \cdot \text{Var}[g(n)]$
3. 机会约束：找到以概率 $p$ 满足约束的解决方案
4. 鲁棒优化：最小化最坏情况成本

示例：在具有不确定旅行时间的路线规划中：

• 风险规避：偏好具有可预测时间的路线
• 风险中性：最小化期望时间
• 风险寻求：在快速路线上冒险

分层 A* (HA*)

问题：具有多级别结构的大型状态空间

• 跨城市 vs 街道的导航
• 具有高级和低级移动的游戏

解决方案：在多个抽象级别搜索

过程：

1. 抽象级别：使用粗粒度表示规划
2. 细化：在详细级别细化抽象计划
3. 回溯：如果细化失败，回溯到抽象级别

def hierarchical_astar(problem, abstraction_map):
    """具有多个抽象级别的分层 A*"""
    # 在最高级别规划
    abstract_plan = astar(abstract_problem)
    
    for abstract_step in abstract_plan:
        # 细化每个抽象步骤
        detailed_plan = astar(refined_problem(abstract_step))
        if not detailed_plan:
            # 细化失败，需要重新规划
            return hierarchical_astar(problem, next_abstraction())
    
    return combine_plans(detailed_plans)

双向搜索

问题：从起点到目标的搜索可能探索许多不相关的节点 解决方案：同时从起点和目标搜索

挑战：如何在中间相遇？

• 需要两个方向的一致启发式
• 必须处理前沿相交时的情况

最适合：

• 无向图
• 具有对称结构的问题
• 当两个方向都有好的启发式时

实时搜索

问题：必须在时间限制内做出决策

• 具有时间控制的游戏
• 具有传感器更新的机器人
• 交互式应用程序

解决方案：

1. 时间受限 A*：时间到期时返回找到的最佳解决方案
2. RTA*（实时 A*）：承诺第一步动作，然后重新规划
3. LRTA*（学习实时 A*）：在探索时学习启发式

def real_time_astar(problem, time_limit):
    """具有固定决策时间的实时 A*"""
    current_state = problem.initial_state
    
    while not is_goal(current_state):
        start_time = time.now()
        
        # 从当前状态搜索
        best_action = None
        best_value = infinity
        
        for action in problem.actions(current_state):
            # 有限前瞻
            value = lookahead_search(current_state, action, time_limit/len(actions))
            if value < best_value:
                best_value = value
                best_action = action
        
        # 执行最佳动作
        current_state = problem.transition(current_state, best_action)

内存受限搜索

问题：A* 对于大型问题可能使用过多内存 解决方案：限制内存使用的算法

方法：

1. SMA*（简化内存受限 A*）：内存满时丢弃最差节点
2. IDA*（迭代深化 A*）：使用深度优先和递增的 f 成本限制
3. RBFS（递归最佳优先搜索）：具有回溯的递归搜索

权衡：更少的内存使用，但可能重新扩展节点

这些泛化展示了最佳优先搜索框架的灵活性。通过修改评估函数、添加约束或更改搜索策略，我们可以适应各种现实世界的问题。

实验评估：指标和方法

我们如何知道哪种算法对我们的问题表现最佳？实验评估帮助我们理解搜索算法超越理论保证的实际性能。

关键性能指标

1. 扩展的节点

• 学术论文中最常见的指标
• 直接关系到计算复杂度
• 计算实际处理了多少状态
• 独立于实现细节

2. 运行时间

• 用户实际关心的
• 取决于：
  • 实现效率
  • 数据结构选择
  • 硬件
  • 常数因子

3. 解决方案质量

• 对于次优算法：离最优有多近？
• 次优性比率：$\frac{\text{找到的成本}}{\text{最优成本}}$
• 对于加权 A*、贪婪搜索等很重要

4. 内存使用

• 边界/封闭集的最大大小
• 对于大型问题至关重要
• 在算法之间差异显著

生成问题实例

随机问题：

• 具有各种拓扑的随机图
• 拼图的随机实例（8 数码、魔方）
• 随机调度/规划问题

真实世界基准：

• 来自 OpenStreetMap 的道路网络
• 游戏 AI 场景
• 工业规划问题
• 标准化测试集

结构化问题：

• 具有已知最优解的问题
• 强调特定方面的问题：
  • 死胡同
  • 多条路径
  • 对称性
  • 瓶颈

数据结构影响

优先队列实现的选择显著影响性能：

数据结构	插入	提取最小	减少键	最适合
二叉堆	$O(\log n)$	$O(\log n)$	$O(\log n)$	一般用途
斐波那契堆	$O(1)$ 摊销	$O(\log n)$ 摊销	$O(1)$ 摊销	大图
桶队列	$O(1)$	$O(1)$	$O(1)$	小整数成本
配对堆	$O(1)$	$O(\log n)$	$O(\log\log n)$ 摊销	实践中良好

实际建议：

• 二叉堆简单且通常足够好
• 斐波那契堆具有更好的渐近性但大的常数
• 对于特殊情况（小整数成本），桶队列表现出色

启发式质量分析

启发式误差分布：

• 平均误差：$\frac{1}{|S|}\sum_{s \in S} |h(s) - h^*(s)|$
• 最大误差：$\max_{s \in S} |h(s) - h^*(s)|$
• 与实际最优成本的相关性

有效分支因子：

$$b^* = \left(\frac{\text{扩展的节点}}{\text{解决方案深度}}\right)^{1/\text{解决方案深度}}$$

• 衡量搜索的集中程度
• 越接近 1 越好
• UCS：$b^*$ = 实际分支因子
• A*：$b^*$ 取决于启发式质量

可视化技术

搜索空间可视化：

• 扩展节点的 2D/3D 图
• 按 $g$、$h$ 或 $f$ 值着色
• 显示搜索进度的动画

性能分析：

• 运行时间 vs 问题大小
• 扩展的节点 vs 解决方案质量
• 随时间的内存使用

比较分析：

• 比较两个算法的散点图
• 加速比
• 多目标情况的帕累托前沿

统计分析

多次运行：

• 跨问题实例的平均性能
• 标准差和置信区间
• 统计显著性检验

扩展分析：

• 性能如何随问题大小变化？
• 多项式 vs 指数扩展
• 识别相变

基准套件

标准集合：

• DIMACS：图算法挑战
• IPC：国际规划竞赛
• TPTP：自动定理证明
• SSSP：单源最短路径实例

创建您自己的基准：

• 确保难度多样性
• 包括简单和困难的实例
• 记录属性和已知解决方案
• 使其公开可用

常见陷阱

1. 过拟合：针对特定测试用例优化
2. 实现偏差：比较优化与朴素实现
3. 硬件效应：不考虑缓存/内存层次结构
4. 采样不足：在太少实例上测试
5. 忽略常数：渐近分析并不能说明全部

工具和框架

搜索算法库：

• SearchLib (C++)
• AI4R (Ruby)
• SimpleAI (Python)
• 各种大学课程项目

可视化工具：

• 搜索树的 Graphviz
• 性能图的 Matplotlib/Seaborn
• 自定义基于 Web 的可视化器

基准测试框架：

• 具有时间工具的自定义脚本
• 统计分析包（R、pandas）
• 用于回归测试的持续集成

好的实验方法有助于：

• 为您的问题选择正确的算法
• 理解算法行为的原因
• 识别改进机会
• 公平地比较您的工作与其他工作

总结

我们探索了从 Dijkstra 算法到状态空间搜索统一框架的优雅泛化。关键洞察是：

Dijkstra = UCS = 使用 $f=g$ 的最佳优先 本质上，Dijkstra 算法只是最佳优先搜索，其中评估函数 $f(n)$ 只是从起点开始的累积成本 $g(n)$。

抽象的力量 通过从显式图移动到由六元组 $\langle S, A, s_0, T, c, S_G \rangle$ 定义的状态空间，我们可以将这些算法应用于 vastly 不同的问题领域：

• 道路网络中的路径查找
• 拼图解决（8 数码、魔方）
• 规划和调度
• 游戏和自动推理

启发式：领域知识在行动 启发式函数 $h(n)$ 的引入将统一搜索转变为引导探索：

• $f(n) = g(n)$：Dijkstra/UCS——最优但不集中
• $f(n) = g(n) + h(n)$：A*——具有集中搜索的最优
• $f(n) = g(n) + w \cdot h(n)$：加权 A*——更快，有界次优性
• $f(n) = h(n)$：贪婪搜索——快速但无最优性保证

理论基础很重要 理解可接受性和一致性等属性有助于我们：

• 在需要时保证最优性
• 设计有效的启发式
• 为特定问题选择适当的算法
• 证明新算法的正确性

超越基础 该框架扩展以处理：

• 多目标（帕累托最优）
• 不确定性和风险敏感性
• 实时约束
• 内存限制
• 分层分解

这种统一视图表明，看似不同的算法都是相同基本思想的实例——按某个评估函数的顺序探索状态。通过选择不同的评估函数，我们在最优性、完备性、速度和内存使用之间进行权衡，以满足我们的特定需求。

参考文献

1. Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson. Chapter 3: Solving Problems by Searching.