LPA-Star算法

LPA-Star算法_第1张图片
【由于专栏后几篇限制vip观看,我又把完整算法在公众号“武汉AI算法研习”进行了发布,可以查看全专栏文章。】

Lifelong Planning A* 是LPA-Star算法的英文全称,算是A-Star的升级版本,它可以适应图形中的变化而无需重新计算整个图形。

【相关定义】

succ(s):successors,节点s的后续节点(子代节点)集合,例如节点1,2,3…i按顺序均已被搜索过,那么除了1~i的其它结点均属于succ(i)。

pred(s):predecessors,类比上述,节点s的前代节点(父代节点),与succ(s)的意义刚好相反。

c(s,s’):两节点之间的代价函数,0

g * (s):节点s到起始点Start的实际最短距离。
g∗(s)={

你可能感兴趣的