启发式搜索（Heuristic Search）完全入门指南

关键词：人工智能、A*算法、启发函数、可采纳性、路径规划、8-puzzle、松弛问题、子问题、经验学习

---

1. 为什么需要启发式搜索？

搜索类型	是否用领域知识	典型算法	缺点
无信息（Uninformed）	否	BFS、DFS、UCS	盲目扩展，指数级爆炸（围棋分支因子≈250）
有信息（Informed）	是	Greedy、A*	利用“提示”大幅剪枝，多项式级即可求解

生活类比：
无信息 = 摸黑找钥匙；启发式 = 根据“叮当声”方向走。

---

2. 核心概念速查表

名词	记号	含义	例子
评价函数	f(s)	决定下一个扩展谁	f(s)=g(s)+h(s)
启发函数	h(s)	估计s到目标的最小代价	直线距离、错位方块数
实际代价	h*(s)	真实最小代价（未知）	最短路径长度
可采纳性	h≤h*	永不高估 → 保证A*最优	直线距离可采纳

ℎ𝑆𝐿𝐷 𝑠 =straight-line distance from node 𝑠to the goal

3. 从评价函数看三大算法

• Uniform-Cost：只关心已花代价，最优但慢
• Greedy：只关心“看起来”多近，快但可能掉坑
• A*：两者兼顾，只要h可采纳 → 既快又最优

---

4. 手把手案例

4.1 路径规划（深圳校园→创园）

算法	路径	总距离	是否最优
Greedy	1号门→2号门→教工餐厅→创园	1918 m	❌
A*	1号门→2号门→3号门→教工餐厅→创园	1851 m	✅

差异原因：Greedy被“局部最短直线”诱惑，A*用g(s)拉回正轨。

4.2 8-puzzle 启发函数

启发函数	值（下图起始状态）	可采纳？	直观解释
h₁（错位方块数）	6	✅	每张牌至少移动1次
h₂（曼哈顿距离和）	18	✅	每张牌最少横向+纵向步数
h₃（1-step moves）	18	✅	忽略碰撞的最少单步

起始状态：

7 2 4
5 6 8
3 1

目标：

1 2 3
4 5 6
7 8

---

5. 如何评判“好”启发？

可接受启发式函数：启发式函数 ( h(s) ) 永远不会高估从状态 ( s ) 到目标状态的最低（最优）代价。(预估值永远小于等于真实值)

1. 可采纳性（admissible）→ 保证A*最优
2. 占优性（dominance）→ h₁≥h₂ ⇒ h₁更高效 （信息更加丰富，剪支根据高效）
3. 有效分支因子 b*

   解深度d=20时：
   IDS 需 1.8×10⁵ 节点，A*+h₂ 仅 1.2×10³，b* 从2.0→1.28

例子：

我们来看这个练习：

---

🧩 给定状态（假设为标准 8-puzzle 某一状态）：

我们可以合理假设如下起始状态（常见于教材）：

7 2 4
5 6 8
3 1

（空位在右下角，目标状态为）

1 2 3
4 5 6
7 8

---

✅ 计算启发函数值：

1. hmis(s) = 错位方块数

将当前状态与目标状态对比，有多少个数字不在目标位置上？

• 位置 (0,0): 7 ≠ 1 → 错位
• (0,1): 2 = 2 → 正确
• (0,2): 4 ≠ 3 → 错位
• (1,0): 5 ≠ 4 → 错位
• (1,1): 6 = 5 → 错位
• (1,2): 8 ≠ 6 → 错位
• (2,0): 3 ≠ 7 → 错位
• (2,1): 1 ≠ 8 → 错位
• (2,2): 空位，不算

→ 共 7 个错位方块

✅ hmis(s) = 7

---

2. h1stp(s) = 单步移动数（忽略障碍，允许“穿透”）

即：每个数字到其目标位置的 曼哈顿距离（横向 + 纵向步数）

数字	当前位置	目标位置	曼哈顿距离
1	(2,1)	(0,0)
2	(0,1)	(0,1)	0
3	(2,0)	(0,2)
4	(0,2)	(1,0)
5	(1,0)	(1,1)
6	(1,1)	(1,2)
7	(0,0)	(2,0)
8	(1,2)	(2,1)

→ 总曼哈顿距离 = 3+0+4+3+1+1+2+2 = 16

✅ h1stp(s) = 16

---

📊 比较：哪个更好？

启发函数	值	特点
hmis(s)	7	粗略估计，只数错位
h1stp(s)	16	更精细，考虑距离

✅ 回答：

• h1stp(s) 更好。
• 原因：它更接近真实解代价，但仍 ≤ 实际最优解（可采纳），因此提供更多信息 → 剪枝更多 → 搜索更快。

🔍 所谓“更好”指：在保持可采纳性的前提下，值越大越好（更接近 h*(s)）。

---

✅ 最终答案总结：

问题	答案
hmis(s) = ?	7
h1stp(s) = ?	16
哪个更好？	h1stp(s)，因为它更大但仍可采纳，搜索效率更高。

---

✅ A* 核心思想一句话总结 评估函数：f(s)=g(s)(起点到状态s要支付的代价)+h（s）（s状态到终点所要支付的预计代价）

“宁可多算一步，也不走冤枉路。”

---

🎯 记忆口诀

“A 像打车，司机既看计价器（g），也看导航剩余公里（h），再挑一条最便宜路线走。”*

---

🔍 逐句拆解

原句	翻译	关键词
avoid expanding paths that are already expensive	别再把时间浪费在“明显已经很贵”的路线上	剪枝
expand the node s with minimal f(s)=g(s)+h(s)	每次挑“起点→s→终点”总代价估计最小的节点先扩展	最优优先
g(s)	已经付掉的代价（从起点到 s 的实际路径长）	过去
h(s)	还要付的代价估计（从 s 到终点的乐观猜测）	未来
f(s)	总账单预估 = 过去 + 未来	全程

---

✅ 三者的“判断函数”对比

算法	判断函数 f(s)	只看/兼顾	通俗解释
Uniform-Cost Search (UCS)	f(s) = g(s)	只看过去	“已经花的钱越少越优先” → 不知道终点还有多远，可能先绕远路。
Greedy Best-First	f(s) = h(s)	只看未来	“离终点看起来最近越优先” → 容易短视，可能冲进死胡同。
A*	f(s) = g(s) + h(s)	兼顾过去+未来	“总账单估计最少越优先” → 既省已花，又估剩余，方向最稳。

---

6. 三步生成可采纳启发

方法	思路	例子
① 松弛问题	删除部分约束 → 最优解必≤原问题	8-puzzle“可飞跃”→h₁
② 子问题	只解决部分目标 → 代价必≤全问题	只摆好1-2-3-4 方块
③ 经验学习	用机器学习拟合 h(s)=w₁x₁+w₂x₂+… 并剪枝超限值	神经网络/决策树

技巧：多启发取 max{h₁,h₂,…} 仍可采纳且更优。

---

7. 算法伪代码（Python 风格）

def a_star(start, goal_test):
    frontier = Heap()               # 优先队列，按 f=g+h 排序
    frontier.push(start, f=0)
    explored = set()
    g = defaultdict(lambda: inf)
    g[start] = 0

    while frontier:
        s = frontier.pop()
        if goal_test(s): return path(s)
        explored.add(s)
        for t in neighbors(s):
            tentative = g[s] + cost(s, t)
            if tentative < g[t]:
                g[t] = tentative
                f = g[t] + h(t)
                frontier.push_or_update(t, f)
    return None

---

8. 性能对比一览

指标	Greedy	A* (h可采纳)
完备	❌（可能循环）	✅
最优	❌	✅
时间	O(bᵐ)	O(bᵈ)（d=解深）
空间	O(bᵐ)	O(bᵈ)（内存瓶颈）

内存杀手 → 衍生 IDA*、Beam Search、Jump Point 等改进。

---

使用用例

问题描述

在这个机器人导航的例子中，目标是找到从起点（红色）到终点（绿色）的最优路径。机器人可以在网格上沿直线或对角线移动。启发函数 ( h_{SLD}(s) ) 表示从当前节点 ( n ) 到目标的直线距离。移动的代价如下：

• 水平或垂直移动的代价为 1。
• 对角线移动的代价为 ( \sqrt{2} )。

解决方法

1. Greedy Search（贪婪搜索）

贪婪搜索将使用启发函数 ( h_{SLD}(s) ) 来指导搜索过程，每次选择当前估计代价（即直线距离）最小的节点进行扩展。这种方法简单直接，但可能不会总是找到最优解，因为它只考虑了到目标的直接距离，而没有考虑实际的移动代价。

2. A* Search（A* 搜索）

A* 搜索结合了实际代价 ( g(s) )（从起点到当前节点的实际路径代价）和启发函数 ( h(s) )（当前节点到目标的估计代价）来计算每个节点的总估计代价 ( f(s) = g(s) + h(s) )。A* 搜索在每一步都选择 ( f(s) ) 最小的节点进行扩展，这样可以保证找到的路径是代价最小的最优路径。

实现步骤

1. 初始化：将起点加入开放列表（frontier），并设置其 ( g(s) ) 为 0，( h(s) ) 为起点到终点的直线距离。

2. 循环：当开放列表不为空时，执行以下步骤：

   • 从开放列表中选择 ( f(s) ) 最小的节点进行扩展。
   • 如果该节点是目标节点，则回溯找到路径并结束搜索。
   • 否则，将该节点的邻居节点加入开放列表，并更新它们的 ( g(s) ) 和 ( f(s) ) 值。

3. 剪枝：对于已经在开放列表中的邻居节点，如果通过当前节点到达它的 ( g(s) ) 更小，则更新其 ( g(s) ) 和 ( f(s) ) 值。

4. 结束：当找到目标节点时，回溯从目标节点到起点的路径，即为所求的最优路径。

结果

• Greedy Search 可能会选择一条看似直接但实际代价较高的路径。
• A Search* 将找到一条代价最小的路径，因为它综合考虑了实际代价和估计代价。

这个例子展示了如何使用启发式搜索方法来解决实际问题，特别是在需要在复杂环境中找到最优路径时。A* 搜索因其能够保证找到最优解而特别有用。

9. 实战练习

1. 在 在线可视化工具 里
   • 分别选 Greedy Best-First 与 A* 跑同一张地图，对比扩展节点数。
2. 写代码：用曼哈顿距离做启发，跑通 8-puzzle 随机实例，统计 b*。

---

10. 小结 & 思维导图

记住一句话：
“好的启发函数 = 领域知识 + 数学保证（h≤h）+ 经验调优”*

---

11. 延伸阅读

• Russell & Norvig 《人工智能：一种现代方法》第3章
• 代码仓库：Python-A*
• 论文：
  [1] A-STAR: A mobile ad hoc routing strategy for metropolis vehicular communications.
  [2] Path planning with modified A* algorithm for a mobile robot.

---