梅州网站设计,yahoo搜索引擎入口,合肥网络公司有哪些,wordpress 头条插件一、基础#xff1a;二叉树的遍历-图的遍历
提到搜索算法#xff0c;就不得不说两个最基础的思想#xff1a; BFS#xff08;Breadth First Search#xff09;广度优先搜索 DFS#xff08;Depth First Search#xff09;深度优先搜索
刚开始是在二叉树遍历中接触这…一、基础二叉树的遍历-图的遍历
提到搜索算法就不得不说两个最基础的思想 BFSBreadth First Search广度优先搜索 DFSDepth First Search深度优先搜索
刚开始是在二叉树遍历中接触这两个算法从中文名字上很好理解广度优先就是优先搜索横向结点深度优先就是优先纵向搜索根结点。用一个示意图Fg.1和Fg.2来表示
BFS输出0 1 2 3 4 5
DFS输出0 1 3 4 2 5从二叉树过渡到图有两个变化以有向图为例子每个节点的子节点不一定是两个节点间有方向性如Fg.3。
图的遍历要注意不要重复遍历节点。依然可以用BFS和DFS来做用一个数组来储存每个节点是否被遍历比如已经遍历置为true没有遍历的为false。BFS使用队列DFS使用栈详细的在这里不多说。
二、进阶最短路径Dijkstra算法
如果我们在考虑最优路径的问题图比Fg.3的有向图要复杂一些。 比如一个城市有很多镇每个镇之间有多条路径可以到达A镇到D镇没有直达路要从A走到D可能要经过B也可能经过C我们通常会选择最短的距离作为最优路径这就要求我们在图中引入权值且对于路径问题来说权值一定为正数如Fg.4。
Dijkstra可以算出起始点到任意点的最短距离。它其实是BFS的加权版引入了贪心算法的思想从起始位置开始遍历子节点每次都要选最短的路径走直到遍历到目标位置。从局部最优到全局最优。
Dijkstra需要维护一个从起点到终点到路径及距离权值表格可以用二维数组来存储。因为每个点都需要遍历到其他点的路径来更新表格所以算法复杂度O(n2)。
三、启发式的搜索最佳优先搜索 A*算法
现实中找路也许更加复杂。假设我是一个路痴其实我就是我不知道A镇到D镇要走哪个方向难道要一圈一圈扩大搜索范围来找吗这时候如果使用Dijkstra算法我需要从红色起点向周围扩展8个格子再分别考虑这8个格子周围的8个格子太慢了! 所以启发式搜索登场了。
如Fg.5所示我站在红色的起点但我不是茫然无措的我还知道终点在哪所谓启发就是我的搜索是有方向性的。在此介绍最佳优先搜索Greedy Best First Search和A*算法。
那么我到底要往哪里走最佳优先搜索和A*算法都引入了一个启发函数。 最佳优先算法 F H 最佳优先算法FH 最佳优先算法FH A ∗ 算法 F G H A*算法FGH A∗算法FGH 两种算法每次都是选取F最小的值。在这个等式中G是到起点的距离为确定值H是到目标点的距离为预测值。为了方便计算我们将这些值扩大10倍。 G比较好理解比如从起点向右走一格G值为10即1x10向斜上方走一格G值为14即 2 \sqrt{2} 2 x10。 H即当前位置到终点的距离有多种预测方法。在此我们展示Manhattan方法使用曼哈顿距离即忽略障碍物考虑起点到终点的最短位移只能往水平或竖直方向走再扩大10倍得到H预测值。起点周围的方格的H值如Fg.6所示。
以A*算法为例最后我们就可以计算出F值如Fg.7所示起点正右侧的格子FGH105060 它也是当前检索方块中F值最小的方块就加入到路径中如图Fg.8所示然后再去探索当前粉色位置周围的F值如果遇到障碍物则忽略障碍物格子。依次检索直到终点。
可以看到最佳优先算法和A* 算法都是对Dijkstra算法的优化引入启发函数使计算量大大减少当H值为0的时候最佳优先算法和A*就退化成了Dijkstra算法。
四、进一步优化考虑动态环境的D*算法
A*算法用启发的方式探路看上去已经很棒了。 还记得A*的公式吗 FGH G是当前节点到起点的确定距离H是当前节点到终点的预测距离 不过现实总是更复杂一些上面我们只是在图上放了几个固定的障碍物。那如果环境在变化比如走着走着障碍物移了动怎么办 对于A*来说即使障碍物只移动了很小的位移但从当前位置到终点的路径也需要重新规划。如图Fg.9和Fg.10所示障碍物黑色方块移动了1个单位位移要重新计算一遍F值规划路径。粉色标c的部分其实是相同的路径可否省略这部分计算呢
D* 算法在A* 的基础上在1994年提出。针对动态环境的路径规划增加了环境检测和更新影响路径这两个步骤。最重要的是为了省略Fg.9和Fg.10中粉色标c的计算D*决定从终点开始规划路径。
我们先大体看看A* 和D*的不同
A*D*起点开始搜索终点开始搜索启发式搜索环境变化需要重新规划路径增量式搜索环境变化可以利用先前已规划的信息FGH每次取F最小值kmin { k , h_new}每次取k最小值
详细看下D* 的公式 kmin { k , h_new} h_new表示当前位置到终点的确定距离和A* 的G有点像。 简单来理解D* 算法就是从终点向起点探索出一条最短路径。探索完后调用行进函数出发检测到环境变化障碍物移动或障碍物出现就要调用修正函数来修正这条最短路径。
那问题来了为什么类比A* 算法直接kh_new而还要取k和h_new的最小值为更新值呢我们再深入一点看下算法的实现 D*维护一个OpenList队列来存储搜索节点直到起始格子出队列就完成了一个路径搜索。 在算法的实现中每个小格子会有三个状态
OPENCLOSENEW
OPEN表示被搜索的格子即h_new值更新的格子 CLOSE表示已加入规划路径的格子即从OpenList中移除的格子 NEW表示未曾被搜索的格子h_new值初始化为正无穷。
试想当环境变化比如出现了障碍物h_new值被更新为值正无穷。此时将这个变化的格子被加入到OpenList重新规划路径因为OpenList是按照h_new排序后依次遍历更新周围节点的所以这个突然出现的障碍物节点就会排到最后才遍历。但我们希望马上就能遍历这个障碍物节点但周围节点所以需要k值这样使效率提高不少。 每次环境变化要修正路径时计算加入到OpenList的格子的k值变小才加入到修正的路径中否则停止搜索。 我们按照k值公式来举例子如图Fg.11和Fg.12 当前位置在粉红色格子Fg.11-Fg.12 正右侧有障碍物突然出现即B格子h_new的值被更新为正无穷这时候计算k值k值保持之前的k值不更新这个格子不会被加入OpenList中。 再举个例子当前位置在粉红色格子Fg.12-Fg.11 正右侧障碍物突然移开即B格子h_new的值被更新变小这时候计算k值就比原来的k值小即为h_new此时这个变化的格子B会被加入到OpenList中重新规划路径。 照这样继续搜索kh_new时停止更新这样其实Fg.9和Fg.10中标有c的部分就不会被更新减少了许多计算量。如此就完成了路径的修正。
小结以上算法是需要先验知识的即起点和终点并距离信息这些信息可以通过路径规划前的扫描建图来获取。A* 多用于静态环境路径规划D*多用于动态环境路径规划是目前比较优秀的最短路径搜索算法。
