一、回顾：无信息搜索

• 深度优先搜索(DFS)：优先展开最深的未展开节点，时间复杂度线性但不完备也不最优

• 广度优先搜索(BFS)：优先展开最浅的节点，完备且当所有步骤代价相同时最优，但空间复杂度指数级

• 迭代加深搜索：反复调用深度受限的DFS直到找到目标，完整且对单位步长最优

• 统一代价搜索(UCS)：展开路径成本最低的节点，对一般步长成本最优

二、启发式搜索概述

• 使用超出问题定义本身的特定知识

• 能比无信息策略更高效地找到解决方案

• 采用最佳优先搜索方法，基于评估函数选择展开节点

• 评估函数被视为从起点到终点的成本估计，优先展开评估值最低的节点

三、启发式函数（Search Heuristics）

• 估计从节点的状态到目标状态的最低路径成本

• 如果是目标节点，则

• 不包含在问题描述中

• 例子：曼哈顿距离；欧几里得距离

四、贪婪搜索(Greedy Search)

• 策略：优先展开看似最接近目标状态的节点

• 使用启发式函数估计每个状态到最近目标的距离

• 每一步都试图尽可能接近目标

• 在有限状态空间中也可能不完整（如果采用树搜索）
• 因为树搜索不会记录去过的节点，可以陷入无限循环

• 最坏情况：类似方向错误的DFS

• 时间和空间复杂度为，m为搜索空间最大深度

五、A*搜索

• 结合UCS和Greedy Search的优点

• ：到达节点的实际成本(后向成本)

• ：从节点到目标的估计成本(前向成本)

可采纳性(Admissibility)

启发式函数的可采纳性要求：

• 永远不会高估到达目标的成本（乐观估计确保不会错过最优解）

🌻

乐观决策

一致性(Consistency)

要求：

• 估计的启发式成本≤实际成本（可采纳性的要求）

• 启发式"弧"成本≤实际弧成本

类似于三角形两边之和大于第三边的关系

🌻

随着目标的靠近，越来越不乐观

满足一致性导致的结果是：

路径上的f值永远不减小

六、A*搜索的性质

树搜索

最优性证明

• 树搜索：当启发式函数可采纳时，A*最优
A* 树搜索算法的最优性证明





有一定的定向搜索能力；定向搜索的好坏取决于启发函数的好坏。只要满足可采纳性，A*就是最优的

构建可采纳的启发函数

构建可采纳（乐观）启发式函数的主要方法是通过问题松弛（Problem Relaxation）：

• 删除或简化原问题的一些约束条件

• 松弛问题的最优解成本必须≤原问题的最优解成本

• 松弛问题越接近原问题，启发式函数越精确但计算也越复杂

常见的松弛方法包括：

• 子目标忽略：假设子目标之间互不影响，分别计算到达每个子目标的成本

• 容量限制放宽：忽略资源容量约束，允许超载使用

• 路径约束简化：允许穿墙、对角移动等在实际中不可行的操作

构建启发式函数的一般原则：

• 尽可能接近实际成本但不超过

• 计算简单，避免过于复杂的估计

• 可以组合多个可采纳的启发式函数，取其最大值

启发式函数的质量直接影响A*搜索的效率。好的启发式函数应该既保持可采纳性，又能提供有意义的指导。

Example：8 Puzzle

1. 启发式函数的设计与可采纳性 (Admissibility)：
• 这些例子展示了如何为 8-Puzzle 问题设计不同的启发式函数。
• 强调了启发式函数需要是可采纳的 (admissible)，即它估计的代价不能超过实际到达目标的最小代价。 这对于保证 A* 算法的最优性至关重要。

2. 不同启发式函数的性能差异：
• 8 Puzzle I (Tiles Misplaced - 错位棋子数)：第一个例子使用的启发式函数是计算当前状态下有多少个棋子不在其目标位置。 这是一个相对简单且可采纳的启发式函数。 课件通过数据显示，即使是这样的简单启发式函数，也比无信息搜索（如 UCS）在扩展节点数方面有显著改进。
• 8 Puzzle II (Manhattan Distance - 曼哈顿距离)：第二个例子引入了一个更优良的启发式函数——所有棋子到其目标位置的曼哈顿距离之和。 曼哈顿距离是指棋子在水平和垂直方向上需要移动的总格数。这个启发式函数也是可采纳的，因为它相当于放宽了问题的限制（棋子可以无视其他棋子直接移动到目标位置）。 课件数据显示，使用曼哈顿距离的 A* 算法比使用“错位棋子数”的 A* 算法扩展了更少的节点，表明更精确的启发式函数能带来更好的搜索效率。

3. 启发式函数的质量与计算成本的权衡：
• 8 Puzzle III (Actual Cost as Heuristic - 使用实际代价作为启发式函数)：第三个例子提出了一个思考：如果使用到达目标的实际代价作为启发式函数会怎样？ 这样的启发式函数无疑是完美可采纳的，并且 A* 算法会只扩展最优路径上的节点，效率极高。 但问题在于，如果已经知道了到达目标的实际代价，那就相当于问题已经被解决了，计算这个“启发式函数”本身的成本就等同于解决整个问题。
• 这个例子说明了在设计启发式函数时存在的权衡 (trade-off)：启发式函数越接近真实的代价，A* 搜索扩展的节点就越少，搜索效率越高；但计算这个启发式函数本身的开销也可能越大。 理想的启发式函数应该在提供准确估计的同时，计算成本又不能过高。

总结来说，8-Puzzle 的这三个例子旨在阐释以下核心概念：

• 可采纳启发式函数的重要性：保证 A* 算法找到最优解。

• 启发式函数的“信息量”或“质量”：更接近真实代价的启发式函数能更有效地指导搜索，减少不必要的节点扩展。但同时获得启发函数的成本也就越高

• 启发式函数的设计策略：例如通过“松弛问题 (relaxed problems)”来构造可采纳的启发式函数（如曼哈顿距离）。

• 启发式函数的实用性：需要在估计的准确性和计算该估计的成本之间找到平衡。

 

不同启发函数比较

• Dominance: if
• 如果对于问题中的每一个节点 n，启发式函数 的值总是大于或等于另一个启发式函数 的值，那么我们说 支配 。
• 在A*搜索中，如果两个启发式函数都是可采纳的 (admissible)，那么支配性更强的启发式函数（值更大）通常会使得搜索扩展更少的节点，从而更有效率。
• 为什么？
• 因为可采纳的启发函数总是乐观的，也就是估计的成本小于等于实际成本
• 但是我们总是希望启发函数的估计能够尽可能接近实际成本

• Max of admissible heuristics is admissible:
• 这是一个非常重要的特性。如果你有两个（或多个）都是可采纳的启发式函数（例如 和 ），那么取它们在每个节点上的最大值构成的新启发式函数 也是可采纳的。
• 为什么这是有用的？ 因为我们总是希望启发式函数尽可能地接近真实成本。通过取多个可采纳启发式函数的最大值，我们得到的新启发式函数至少和其中任何一个一样好，甚至可能更好（更接近真实成本）。

• Bottom of lattice is the zero heuristic
• "Lattice"（格结构）在这里指的是基于支配关系的所有可能的启发式函数形成的一种层级结构。



• 格结构的最底部是零启发式 ( for all n)。这意味着启发式函数总是估计剩余代价为0。
• 如果在A*搜索中使用 ，那么评估函数 。这实际上就退化成了Uniform Cost Search (UCS)
• UCS是可采纳的/一致的，（因为它不依赖启发式估计），但它比使用良好启发式的搜索效率低，因为它没有目标导向的指引。

• Top of lattice is the exact heuristic
• 格结构的最顶部是精确启发式 ( for all n)，即启发式函数给出的估计总是等于到目标的最优实际代价。
• 这是理论上最好的启发式函数。如果能得到这样的启发式函数，A*搜索会直接沿着最优路径进行，不会扩展任何不必要的节点。
• 然而，在实际问题中，如果已经知道了精确的启发式（即 ），那通常意味着问题已经被解决了，所以计算这个启发式本身的代价可能非常高昂甚至不可行。

图搜索

• 图搜索：当启发式函数一致时，最优
• 一致性条件更强（包括可接纳性）
• 图搜索最优性条件更苛刻

搜索问题例题