运动规划之搜索算法：前端规划、后端轨迹生成到状态求解( 三 ) _算法

1. 栅格地图 / 概率图1. Dijkstra2. BFS（Best-First-Search）3. A*4. hybrid A*5. D*6. RRT7. RRT*8. 蚁群算法9. Rectangular Symmetry Reduction (RSR)10. BUG11. Beam search12. Iterative Deepeningc13. Dynamic weighting14. Bidirectional search15. Dynamic A* and Lifelong Planning A *16. Jump Point Search17. Theta *2. 拓扑地图1. Dijkstra2. BFS（Best-First-Search）3.A*4. CH5. HH6. CRP

图搜索算法结构:::success

维护一个容器来存储所有待访问的节点
该容器以起始状态XS进行初始化
循环
根据某个预定义的评分函数从容器中移除一个节点
访问一个节点
扩展：获取该节点的所有邻居
发现所有的邻居
将它们（邻居）推入容器
扩展：获取该节点的所有邻居
结束循环 :::

通用搜索算法结构常用的图搜索有3大类的搜索结构，其它算法都是在这三个大的框架之下做改进。
深度优先搜索（Depth-First Search, DFS）：

原理：DFS是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
优点：实现简单，当目标明确时，搜索效率高。
缺点：不保证找到最短路径，有可能会导致搜索陷入无限循环。

广度优先搜索（Breadth-First Search, BFS）：

原理：BFS是一种广度优先的搜索算法，用于搜索树或图。这个算法从根节点开始，沿着树的宽度遍历树的节点，如果所有节点均被访问，则算法结束。
优点：可以找到最短路径，结果可靠。
缺点：空间复杂度高，当解空间大时，内存消耗大。

贪婪搜索（Greedy Search）：

原理：贪婪搜索是一种在每一步选择中都采取在当前看来最好的选择，希望通过一系列的最优选择，能够产生一个全局最优的解决方案。
优点：简单，易于实现，计算速度快。
缺点：不能保证找到全局最优解，只能保证找到局部最优解。
深度优先搜索（DFS）：DFS会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条路径。这种搜索策略可以看作是“先入后出” ，因此在实现DFS时通常使用栈（Stack）这种数据结构。DFS的优点是实现简单，当目标明确时，搜索效率高。然而，DFS的缺点是不保证找到最短路径，有可能会导致搜索陷入无限循环。
广度优先搜索（BFS）：相比之下，BFS会根据离起点的距离，按照从近到远的顺序对各节点进行搜索。这种搜索策略可以看作是“先入先出”，因此在实现BFS时通常使用队列（Queue）这种数据结构。BFS的优点是可以找到最短路径，结果可靠。然而， BFS的缺点是空间复杂度高，当解空间大时，内存消耗大。