A_star

A*算法:a::star:

优先级计算：

$$f(x, y)=g(x, y)+h(x, y)$$

其中：

$f(x, y)$：点$(x, y)$的优先级，每次选择优先级最低的节点遍历；

$g(x,y)$：点$(x,y)$距离起点的代价；

$h(x, y)$：点$(x,y)$距离终点的代价；

算法描述：

• 初始化open_set（待遍历节点）、close_set（已遍历节点）；
• 将起点加入open_set，并设置优先级为0（最高优先级）；
• 如果open_set不为空 ==> 从open_set中选取优先级最高的节点n；
  • 如果节点n为终点 ==>
    • 从终点开始逐步找到parent节点；
    • 返回找到的结果路径，算法结束；
  • 如果节点n不是终点 ==>
    • 将节点n从open_set中删除，并加入close_set；
    • 遍历节点n所有的邻接节点 ==>
      • 如果邻接节点m在close_set中 ==> 跳过；
      • 如果邻接节点m不在open_set中 ==>
        • 设置节点m的parent为节点n；
        • 计算节点m的优先级；
        • 将节点m加入open_set；