搜索算法
本文主要以一些概念对较为常见的搜索作简单介绍：
一、盲目搜索
对一个图进行搜索意味着按照某种特定的顺序依次访问其顶点。在所有搜索方式中，广度优先算法和深度优先搜索算法都十分重要，因为它们提供了一套系统地访问图数据结构的方法。我们着重讲解广度优先搜索算法。
Dijkstra算法(可自行设置障碍物）
二、启发式搜索算法
三、启发函数
f ( n ) = g ( n ) + h ( n ) f(n)=g(n)+h(n) f(n)=g(n)+h(n)
f(n)是节点n的综合优先级。当我们选择下一个要遍历的节点时，我们总会选取综合优先级最高（值最小）的节点。g(n) 是节点n距离起点的代价。h(n)是节点n距离终点的预计代价，这也就是A star算法的启发函数。
上面已经提到，启发函数会影响A star算法的行为。
在极端情况下，当启发函数h(n)始终为0，则将由g(n)决定节点的优先级，此时算法就退化成了Dijkstra算法。
如果h(n)始终小于等于节点n到终点的代价，则A star算法保证一定能够找到最短路径。但是当h(n)的值越小，算法将遍历越多的节点，也就导致算法越慢。
如果h(n)完全等于节点n到终点的代价，则A star算法将找到最佳路径，并且速度很快。可惜的是，并非所有场景下都能做到这一点。因为在没有达到终点之前，我们很难确切算出距离终点还有多远。
如果h(n)的值比节点n到终点的代价要大，则A star算法不能保证找到最短路径，不过此时会很快。在另外一个极端情况下，如果h(n)相较于g(n)大很多，则此时只有h(n)产生效果，这也就变成了贪婪最佳优先搜索。
由上面这些信息我们可以知道，通过调节启发函数我们可以控制算法的速度和精确度。因为在一些情况，我们可能未必需要最短路径，而是希望能够尽快找到一个路径即可。这也是A star算法比较灵活的地方。对于网格形式的图，有以下这些启发函数可以使用：
如果图形中只允许朝上下左右四个方向移动，则可以使用曼哈顿距离。
如果图形中允许朝八个方向移动，则可以使用对角距离。
如果图形中允许朝任何方向移动，则可以使用欧几里得距离。
总结
以下网页是五种不同搜索算法的搜索过程对比：
五种搜索算法（可进行添加多种障碍物）
下面对在有权图（紫）和无权图（黄）上利用搜索算法的特点做一个总结：
本文参考文章链接：
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/205722.html原文链接：https://javaforall.net
