1. 概述
搜索是计算机科学中的一个基础问题，因此也衍生出大量用于寻找最优解的算法。爬山算法（Hill Climbing） 和 最佳优先搜索（Best First Search, BeFS） 是两种常见的搜索算法。尽管它们在某些方面相似，但也有明显差异。
本文将分别介绍 Hill Climbing 和 BeFS 的基本原理，并从多个维度进行对比分析，帮助你根据实际场景选择合适的算法。
2. 爬山搜索（Hill Climbing）
爬山算法是一种简单的启发式搜索算法。其核心思想是：从一个随机初始状态出发，不断查看其邻近状态，若发现更优状态则移动过去，直到无法找到更优状态为止。
✅ 优点：
- 简单直观
- 内存消耗低
❌ 缺点：
- 容易陷入局部最优（local optima）
- 遇到平台（plateau）或山脊（ridge）时表现不佳
举个例子，爬山算法就像你在雾中爬山，只能看到脚下的路，每次只向上走一步，但可能只爬到了一个小山头就停下了。
以下是其伪代码实现：
algorithm HillClimbing(ss, f):
// INPUT
// ss = 一个任意的搜索空间
// f = 评估函数，值越大表示状态越优
// OUTPUT
// s = 一个局部最优状态
s <- 从 ss 中随机选取一个状态
while true:
N <- s 的所有邻接状态
if N 为空:
return s
for 每个 n in N:
if f(n) >= f(s):
s <- n
return s
3. 最佳优先搜索（Best First Search）
最佳优先搜索（BeFS）是一类启发式搜索算法的统称，A* 和 B* 等算法都属于这一类。它结合了广度优先搜索（BFS）和深度优先搜索（DFS）的优点，通过启发式函数评估节点的优先级，优先扩展最有希望到达目标的节点。
BeFS 通常维护两个列表：
- openList：待扩展的节点集合
- closedList：已扩展过的节点集合
每次从 openList 中选择启发值最小的节点进行扩展，直到找到目标节点为止。
以下是 BeFS 的伪代码：
algorithm BestFirstSearch(G, s, g):
// INPUT
// G = 图结构
// s = 起始节点
// g = 目标节点
// OUTPUT
// 返回从 s 到 g 的最优路径
openList <- { s }
closedList <- 空列表
path <- 空列表
while openList 不为空:
b <- openList 中启发函数值最小的节点
openList.remove(b)
closedList.add(b)
if b == g:
path.add(b)
return path
N <- b 的所有邻居节点
for n in N:
if n 未在 closedList 或 openList 中:
openList.add(n)
else if n 在 openList 中:
if 当前路径代价 <= 旧路径代价:
替换父节点
else if n 不在 closedList 中:
openList.add(n)
return path
4. 爬山算法 vs 最佳优先搜索对比
| 维度 | 爬山算法 | 最佳优先搜索 |
|---|---|---|
| ✅ 优点 | 内存占用低，实现简单 | 可从多个候选中选择最优路径 |
| ❌ 缺点 | 易陷入局部最优、平台、山脊 | 内存开销大，可能陷入循环 |
| 启发式 | 仅比较当前与邻接节点 | 使用全局启发函数排序候选节点 |
| 搜索策略 | 局部贪心 | 全局贪心 |
| 内存使用 | 极低（仅保存当前状态） | 较高（需保存 openList 和 closedList） |
| 适用场景 | 快速近似解，对精度要求不高 | 需要较优路径，如路径规划、图搜索 |
4.1 局部最优问题
- 爬山算法容易陷入局部最优，解决办法之一是多次运行算法，每次从不同起点开始（类似多起点爬山）。
- Best First Search 可能陷入循环，比如访问一个节点后又回到父节点。可通过优化启发函数或加入循环检测机制避免。
4.2 平台与山脊问题
- 平台（plateau）：周围节点与当前节点评估值相同，算法无法判断下一步方向。
- 山脊（ridge）：梯度变化方向受限，只能通过“之”字形路径前进，效率低下。
4.3 内存消耗对比
- 爬山算法只需保存当前状态和目标状态，内存极低。
- Best First Search 需要维护两个列表（openList 和 closedList），内存消耗较高。
4.4 搜索策略对比
- 爬山算法一旦找到比当前更优的邻接节点就立即移动。
- Best First Search会评估所有邻接节点，并通过启发函数选出最优节点进行扩展。
5. 总结
| 特性 | 爬山算法 | 最佳优先搜索 |
|---|---|---|
| 是否全局最优 | ❌（可能陷入局部最优） | ✅（取决于启发函数） |
| 内存占用 | ✅ 极低 | ❌ 较高 |
| 实现复杂度 | ✅ 简单 | ❌ 稍复杂 |
| 是否适合复杂搜索空间 | ❌（易陷入平台或山脊） | ✅（启发式排序更灵活） |
✅ 建议使用场景
- 爬山算法适用于对速度要求高、内存有限、且可接受局部最优解的场景，如快速优化问题。
- Best First Search 更适合需要在复杂图结构中找到较优路径的问题，比如路径规划、游戏 AI 等。
⚠️ 踩坑提醒
- 使用 Hill Climbing 时，记得多试几个起点，避免陷入局部最优。
- 使用 BeFS 时，务必选择一个合适的启发函数（如 A* 的 h(n)），否则效率可能大打折扣。
- 如果搜索空间存在循环路径，记得加入循环检测机制。
如你所见，两种算法各有优劣，关键在于根据具体问题选择合适的方法。希望这篇文章能帮你更清晰地理解它们的差异，并在实际项目中做出明智选择。