路径规划之Best-First Search算法

系列文章目录

路径规划之Dijkstra算法
路径规划之Best-First Search算法

---

---

前言

Best-First Search算法和Dijkstra算法类似，都属于BFS的扩展或改进

一、Best-First Search算法

1.1 起源

Best-First Search算法又称最佳优先搜索算法，属于BFS的扩展，最开始人们也尝试过使用DFS来实现路径规划，效果图如下

上图中可以看出，在实际情况中DFS处于不撞南墙不回头的状态，它找到的路径并不是机器人运行的最优路径；相比之下BFS虽然耗费时间长，代价大，但是可以找到机器人运行的最优路径。

虽然BFS能有效找到最优路径，但是它耗费的代价过大，时间过长，于是在BFS的基础上提出了最佳优先搜索（Best-First Search）。
Best-First Search和Dijkstra不同的地方在于每次选择新的遍历节点时，Dijkstra选择离起点代价最小的点，而Best-First Search选择离终点代价最小的节点。

1.2 过程

Best-First Search算法的核心就是遍历当前节点相邻的结点，选择其中到终点代价最小的结点作为下一次遍历的结点

该算法到终点的代价可以使用欧氏距离或者曼哈顿距离来计算，如图所示

三、简单使用

以下就是Best-First Search算法在一个比较简单的地图中进行路径规划的过程，但该算法在应用中非常容易陷入局部最优解，使用频率远低于Dijkstra算法