新闻中心

路径估价不高估目标距离就一定沿边平稳吗:三张路径估价表的两类约束(实例26)

2026-11-07

给寻路节点一个到目标的估计值时,可以检查两种不同条件:估价没有超过真实最短距离,以及跨一条边时估价下降不超过这条边的成本。两者不能混为一谈。

先固定规则与数据

目标为五号房间,图中边长为正。第一种条件逐点比较h与真实距离;第二种条件对每个方向检查h(u)不大于边成本加h(v),并要求目标估价为零。

无向边[甲,乙,成本][[0, 1, 4], [1, 2, 4], [2, 3, 5], [3, 4, 7], [4, 5, 6], [1, 3, 8], [2, 4, 7], [3, 5, 2]]

逐项记录过程

估价表1[0, 0, 0, 0, 0, 0],逐点不过高True,沿边约束全部满足True;不满足的方向[起,终,左侧,右侧][]。

估价表2[14, 10, 7, 2, 6, 0],逐点不过高True,沿边约束全部满足True;不满足的方向[起,终,左侧,右侧][]。

估价表3[14, 0, 5, 2, 2, 0],逐点不过高True,沿边约束全部满足False;不满足的方向[起,终,左侧,右侧][[0, 1, 14, 4], [2, 1, 5, 4]]。

房间0到五号目标的真实最短距离14,三张表分别给出[0, 14, 14],每个数字都应逐点核对。

房间1到五号目标的真实最短距离10,三张表分别给出[0, 10, 0],每个数字都应逐点核对。

房间2到五号目标的真实最短距离7,三张表分别给出[0, 7, 5],每个数字都应逐点核对。

房间3到五号目标的真实最短距离2,三张表分别给出[0, 2, 2],每个数字都应逐点核对。

房间4到五号目标的真实最短距离6,三张表分别给出[0, 6, 2],每个数字都应逐点核对。

房间5到五号目标的真实最短距离0,三张表分别给出[0, 0, 0],每个数字都应逐点核对。

第三张表把零号估价保留为真实距离,却把相邻一号设成零,因此在零到一的边上下降过快。它没有高估任何节点,仍然不能满足更强的沿边约束。

独立复核的方法

沿整条路径把第二种不等式相加,中间估价会相互消去,从而给出起点估价不超过路径总长的结论。反过来,逐点都不过高仍可能在某条边上下降太快。

建议先按原始数据自己算一遍,保留中间状态后再与本例对照。发生分歧时,先寻找最早不同的步骤,检查边界是否包含、编号与坐标方向是否一致,以及状态是在事件之前还是之后更新。最终结果相同并不能替代对过程规则的理解,修改输入后也需要重新核算。

使用范围

本文只核对估价表的数学性质,不实现完整搜索器,也不据此承诺某种搜索一定访问更少节点。实际效率还依赖图结构、队列规则、是否允许重新打开节点等细节。