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。

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

相关推荐

LLM面试必问的8个核心问题：从Transformer到微调的深度解析

LLM面试8大核心问题：Transformer、Tokenization、Embedding与Function Calling底层原理

生产级Agent内核设计：14个关键决策与四大复利引擎

更多资讯

旋转吧大喵照片地图实现揭秘：JS 注入如何把官方地图变成你的摄影足迹墙

LSTM降雨径流预测Matlab实现：数据归一化与预测评估

POM海洋模型编译配置与物理参数调试实战指南

双稳随机共振MATLAB实战：微弱信号检测与参数调优指南

31岁晋升大厂最高职级22级：AI大模型浪潮下的工程师成长路径

Matlab朴素贝叶斯分类器代码实现与精度调优

今日更新

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？