1024 特刊｜从 A* 到 MCTS：过程奖励分数为什么不能直接当最短路启发函数

搜索器拿到一个分数，第一件事应该是问它在估计什么。A* 的剩余代价、MCTS 的回报估计、PRM 对一步推理的评分，虽然都能排队，却不是同一种量。

10 月 6 日，OpenAI 公开一批数学研究结果及部分 Lean 形式化。这一事件对搜索工程的启示是：候选推导和经过检查的证明，需要保留不同身份。本文讨论的是如何使用评分，不把某个搜索模板写成已经解决数学难题的系统。

A* 的保证带着条件

A* 常写作 f(n)=g(n)+h(n)。g 是已付出的路径代价，h 是剩余代价估计。若要讨论最优性，就必须说明启发函数是否可采纳、是否一致，以及实现是否允许更优路径重新打开节点。不能只给公式后便宣称“搜索必然最优”。

PRM 的 0.9 常表达局部正确性的估计，未必与剩余 token、工具费用或最终任务成功率同单位。直接把它填到 h 里，既可能改变优化方向，也没有自动获得代价下界。

一个会返回次优解的最小反例

下面只用有限图和非负边权，不调用模型。两条路线的总代价分别为 4 和 7。当错误的启发函数把 A 节点抬得过高，而程序在首次弹出目标时返回，就会先拿到代价 7 的路线。

from heapq import heappop, heappush from itertools import count GRAPH = {"S": [("A", 2), ("B", 1)], "A": [("G", 2)], "B": [("G", 6)], "G": []} def search(heuristic): order = count() queue = [(heuristic["S"], next(order), 0, "S", ["S"])] best = {"S": 0} while queue: _, _, cost, node, path = heappop(queue) if cost != best[node]: continue if node == "G": return cost, path for child, edge_cost in GRAPH[node]: candidate = cost + edge_cost if candidate < best.get(child, float("inf")): best[child] = candidate heappush(queue, (candidate + heuristic[child], next(order), candidate, child, path + [child])) raise ValueError("goal unreachable") safe = search({"S": 0, "A": 0, "B": 0, "G": 0}) bad = search({"S": 0, "A": 100, "B": 0, "G": 0}) assert safe == (4, ["S", "A", "G"]) assert bad == (7, ["S", "B", "G"]) print("zero_heuristic:", safe) print("overestimated_heuristic:", bad)

反例并不是说所有学习评分都不可用。它说明：分数能提高探索效率，与分数能支撑最优性证明，是两项需要分别验证的主张。

MCTS 还要给未充分探索的分支机会

MCTS 常把经验回报 Q 和探索项 U 合起来选节点。高 Q 的分支可能只是样本少、碰巧成功；低访问次数的分支也可能值得继续采样。图里的 Q、N、U 是说明概念的人造数字，没有对应模型跑分。

如果引入 PRM，先明确它输出的是概率、logit、排序分数还是未校准奖励。还要决定路径聚合：逐步概率相乘容易偏好短链；取最小值容易被一个低分步骤支配；取平均值可能掩盖关键错误。这些都需要用有标签的验证集比较。

10 月 11 日提交的 Google Earth AI Agent 评估论文把基础模型、工具、领域技能和规划指导分开比较。借鉴这种拆分方法，搜索实验也应分别开关生成器、PRM、验证器和预算策略，避免把工具带来的改进全算给树搜索。

一个可审计的搜索日志至少应保留节点文本、父节点、累计成本、评分来源、剪枝理由和验证状态。最终答案正确，也不能倒推出每个中间步骤正确。本文验证了图搜索反例；没有训练 PRM，也没有运行真实语言模型的 MCTS。