从初始节点开始
我们需要确定 8 个相邻节点中
哪个是最有希望的候选节点
对于每个候选节点
我们考虑两件事情
首先
我们计算从开始节点到候选节点的成本
然后
我们估计从候选节点前往目的地的成本
计算前往候选节点的成本很容易
因为它已经与我们相邻
计算从候选节点到目的地的成本很困难
但是 通过简单计算
从候选节点到目的地的距离 我们通常可以做出很好的估计
我们使用变量 g 和 h 来表示每个成本
g 值为从开始节点前往候选节点的成本
h 值为从候选节点
前往目的地的估计成本或启发式成本
根据我们的具体情况
我们可以自定义成本估算方式
例如 交通堵塞会增加前往目的地的成本
所以交通繁忙的路径具有更高的成本
对于每个候选节点
我们通过添加 g 值和 h 值来计算总和
即 f 值
最佳候选节点是 f 值最小的节点
每当我们抵达新节点时
我们通过重复此过程来选择下一个候选节点
而且总是选择我们尚未访问过
且具有最小 f 值的节点
这就是 A * 算法
它建立了一条稳定前往目的地的路径