A*搜索算法示例中优先级数值的推导逻辑技术问询

示例图 #

算法执行过程 #

访问当前优先级最低的节点0，优先级为8.0
将节点1的距离更新为3，优先级更新为9.32455532033676
将节点2的距离更新为4，优先级更新为10.32455532033676
访问当前优先级最低的节点1，优先级为9.32455532033676
将节点3的距离更新为9，优先级更新为11.82842712474619
将节点4的距离更新为13，优先级更新为15.82842712474619
访问当前优先级最低的节点2，优先级为10.32455532033676
访问当前优先级最低的节点3，优先级为11.82842712474619
将节点5的距离更新为12，优先级更新为12.0
找到目标节点！

优先级数值推导逻辑 #

A*算法中，节点的优先级（即f值）是核心判断依据，计算公式为：
f(n) = g(n) + h(n)
其中：

• g(n)：从起点（节点0）到当前节点n的实际路径累计距离
• h(n)：从当前节点n到目标节点（节点5）的启发式估计距离（此示例采用欧几里得直线距离，即两点间直线距离）

各节点优先级计算拆解 #

1. 节点0

   • g(0)：起点到自身的实际距离为0
   • h(0)：节点0到目标节点5的直线距离为8.0
   • f(0) = 0 + 8.0 = 8.0，与示例中优先级一致

2. 节点1

   • g(1)：起点0到节点1的实际路径距离为3
   • h(1)：节点1到目标节点5的直线距离为√(2²+6²)=√40≈6.32455532033676
   • f(1) = 3 + 6.32455532033676 = 9.32455532033676，与示例数值一致

3. 节点2

   • g(2)：起点0到节点2的实际路径距离为4
   • h(2)：节点2到目标节点5的直线距离同样为√40≈6.32455532033676
   • f(2) = 4 + 6.32455532033676 = 10.32455532033676，与示例数值一致

4. 节点3

   • g(3)：起点0经节点1到节点3的实际路径距离为3+6=9
   • h(3)：节点3到目标节点5的直线距离为√(2²+2²)=√8≈2.82842712474619
   • f(3) = 9 + 2.82842712474619 = 11.82842712474619，与示例数值一致

5. 节点4

   • g(4)：起点0经节点1到节点4的实际路径距离为3+10=13
   • h(4)：节点4到目标节点5的直线距离同样为√8≈2.82842712474619
   • f(4) = 13 + 2.82842712474619 = 15.82842712474619，与示例数值一致

6. 节点5

   • g(5)：起点0经节点1、节点3到节点5的实际路径距离为3+6+3=12
   • h(5)：目标节点到自身的启发式距离为0
   • f(5) = 12 + 0 = 12.0，与示例数值一致

补充说明（原英文来源内容翻译） #

该示例的A*算法实现逻辑为：

• 始终优先访问f值（优先级）最低的节点，以此保证搜索路径的最优性
• 启发式函数选用欧几里得距离，适用于允许任意方向移动的网格场景，能有效预估节点到终点的最短路径距离
• 当节点被访问时，会更新其相邻节点的实际路径距离（g值）与优先级（f值），若新计算的f值更优则覆盖原有值

内容的提问来源于stack exchange，提问作者Danny