1. 简介
在本教程中，我们将介绍并比较两种搜索算法：Uniform-Cost Search (UCS) 和 **Best-First Search (BeFS)**。
这两个算法都用于在图中寻找从起点到目标状态的最优路径。但它们的核心思想和适用场景有明显差异。UCS 是一种完全定义的无信息搜索算法，而 BeFS 是一个通用框架，可以根据不同的评估函数模拟多种搜索策略。
2. 搜索问题概述
在搜索问题中，我们的目标是找到从起点状态到目标状态的最短动作序列。这里的“状态”可以是地图中的一个点、棋盘上的某种布局，甚至是程序的某个运行状态。
我们通常将状态表示为图中的节点，动作表示为边，边上的权重代表“成本”。搜索算法的任务就是在这张图中找到从起点到目标状态的成本最低路径。
需要注意的是：
- 多个节点可能代表同一个状态（例如循环路径）
- 图中可能存在多个目标状态，我们希望找到通往任意目标状态的最低成本路径
3. Uniform-Cost Search (UCS)
Uniform-Cost Search (UCS) 是一种用于寻找最低成本路径的算法。它与广度优先搜索（BFS）类似，但 UCS 更关注路径的总成本，而不是边的数量。
✅ 适用场景
- 图中边的权重不一致
- 需要找到从起点到目标的最低成本路径
❌ 不适合的场景
- 所有边成本相同 → BFS 更高效
- 需要启发式信息（例如距离目标的估计距离）→ UCS 不支持
3.1. UCS 的核心思想
UCS 的核心是使用一个优先队列（priority queue），按照从起点到当前节点的总成本（记作 g(n)）来排序队列中的节点。
关键点：
- 优先队列：节点按照
g(n)从小到大排序 - 更新机制：如果发现一条更优的路径到某个节点，就更新队列
- 目标检测时机：在节点被扩展后才判断是否为目标，以避免返回次优路径
3.2. 伪代码
algorithm UniformCostSearch(s, goal, successors, c):
g(s) <- 0
frontier <- a min-priority queue ordered by g, containing only s
expanded <- an empty set
while true:
if frontier is empty:
return failure
v <- pop the lowest-cost node from frontier
if goal(v) = true:
return v
expanded <- expanded + {v.state}
for w in successors(v):
if w.state not in expanded and no frontier node represents w.state:
g(w) <- g(v) + c(v, w)
Insert w in frontier
else if there is a frontier node u such that w.state = u.state
and g(v) + c(v, w) < g(u):
Remove u from frontier
Insert w in frontier
3.3. 示例演示
考虑如下图：
Start --1--> A --1--> Goal
\ ^
\ /
\--11----------/
- BFS 会直接从
Start -> Goal返回路径，成本为 11 - UCS 会先扩展
Start -> A，发现A -> Goal成本为 2，最终返回路径Start -> A -> Goal，总成本为 2
✅ UCS 返回了最优路径
4. UCS 的性质分析
4.1. 完备性（Completeness）
- 若图是有限的，则 UCS 是完备的
- 若图是无限的，但每条边的成本 > 0，且每个节点的邻居数量有限，UCS 也是完备的
⚠️ 注意：如果图中存在零成本边构成的无限路径，UCS 可能陷入死循环
4.2. 最优性（Optimality）
- 若所有边的成本 ≥ 0，UCS 是最优的
- 一旦某个节点被扩展，UCS 就已经找到了从起点到该状态的最优路径
4.3. 时间与空间复杂度
- 时间复杂度：
O(b^(1 + C*/ε))，其中：b是分支因子C*是最优路径的成本ε是最小边成本
- 空间复杂度：同上
在图搜索中，若节点数为 V，边数为 E，则复杂度为 O(V + E)
5. Best-First Search (BeFS)
Best-First Search (BeFS) 是一个通用的搜索框架，它通过一个评估函数 f(n) 来决定优先扩展哪个节点。
5.1. BeFS 的核心思想
- 使用优先队列维护 frontier
- 每次扩展
f(n)最小的节点 f(n)可以是任意函数，决定搜索策略
5.2. 伪代码
algorithm BestFirstSearch(s, goal, successors, c, f):
g(s) <- 0
frontier <- a min-priority queue ordered by f, containing only s
reached <- a dictionary of {state: node}, containing only s.state: s
while frontier is not empty:
v <- pop the min-f node from frontier
if goal(v) = true:
return v
for w in EXPAND(v):
if w.state not in reached or g(w) < g(reached[w.state]):
reached[w.state] <- w
Insert w into frontier
return failure
function EXPAND(v):
for w in successors(v):
g(w) <- g(v) + c(v, w)
yield w
5.3. BeFS 的灵活性
BeFS 是一个通用框架，可以通过定义不同的 f(n) 来模拟各种搜索策略：
f(n) 定义 |
搜索策略 |
|---|---|
f(n) = g(n) |
Uniform-Cost Search |
f(n) = depth(n) |
Breadth-First Search |
f(n) = -depth(n) |
Depth-First Search |
f(n) = h(n) |
Greedy Best-First Search |
f(n) = g(n) + h(n) |
A* Search |
5.4. BeFS 的优缺点
| 优点 | 缺点 |
|---|---|
| 灵活，可模拟多种搜索策略 | 性能可能不如专门实现的算法 |
| 易于扩展和切换搜索策略 | 需要额外函数调用开销 |
6. 讨论与对比
| 特性 | Uniform-Cost Search | Best-First Search |
|---|---|---|
| 是否通用 | ❌ 否 | ✅ 是 |
| 是否最优 | ✅ 是（边成本 ≥ 0） | ❌ 否（取决于 f(n)） |
| 是否完备 | ✅ 是（边成本 > 0） | ❌ 否（取决于 f(n)） |
| 实现复杂度 | 中等 | 高 |
| 执行效率 | 高 | 中等 |
| 是否适合启发式搜索 | ❌ 否 | ✅ 是 |
✅ 何时使用 UCS？
- 你只需要一个无信息的最优路径搜索算法
- 所有边的成本 ≥ 0
- 不需要切换搜索策略
✅ 何时使用 BeFS？
- 你需要一个灵活的框架，支持多种搜索策略
- 你打算使用启发式函数（如 A*）
- 你希望在运行时切换搜索策略
7. 总结
- UCS 是一种完全定义的无信息搜索算法，保证在非负边权图中找到最优路径
- BeFS 是一个通用框架，可以通过定义不同的
f(n)模拟多种搜索策略 - 虽然 UCS 可以看作是 BeFS 的一种特例，但UCS 的专用实现通常更高效
- 如果你需要灵活性和可扩展性，选择 BeFS；如果只需要一个最优路径算法，选择 UCS 更合适
✅ 记住：UCS 是 BeFS 的特例，但 BeFS 更灵活，UCS 更高效