对于全局路径规划的设计，我们先要了解什么是图搜索，在此之前，要先知道什么是图：

可以看到，图有很多种，有无向图，有向图，节点之间还可以有不同的weight, 用于表述从节点与节点直接迁移的代价。
而图搜索算法则是把我们的搜索对象抽象成state space gragh 来处理。

基本的理论无外乎用树的理论对图进行搜索，当找到终点后在回溯这一分支，最后获得从起点到终点的路径，而可以优化的地方就是如何有效减少这些搜索，从而加速搜索，同时还要保证搜索结果的最优性。

伪代码的流程如下：
我们会不断地更新一个open list, 我们也可以称之为container容器。用于不断地从父节点更新子节点，更新完后，将父节点放到closed集合中，表示这个点已经被搜索过。

主要的最基础的四个路径搜索算法是BFS, DFS, Dja, A*

BFS 和 DFS的很大的一个区别就是深度优先搜索是队列搜索，先进去的先出来。 而广度优先搜索怎么堆栈，总是最后进去的先出来。

具体的说，DFS总是向最深的方向搜索，如果失败，则把这一支删除：


相比之下， BFS则是以广度作为搜索优先，总是搜索最浅的层级：


所以，这里可以看到，广度优先搜索会 比深度优先搜索范围更大，虽然可以绝对保证最优性结果，但是效率远不及深度优先，而深度优先的问题则在于无法保证最优。