图搜索算法-A*算法及其变种详解
发布网友
共1个回答
热心网友
寻找图中从一个位置到另一个位置的路径是一个常见问题。我们需要找到的路径满足以下两个条件：
1）路径上经过的距离最短；
2）路径上花费的旅行时间最少。
从起始点到达终点，找到最短路径。
可以使用图搜索算法找到这个路径。
广度优先搜索（BFS）是最简单的图搜索算法。A* 图搜索算法由它发展而来。
输入：图搜索算法的输入是一个图，图是一个位置（顶点）与将位置相连接的线（边）的集合。
输出：图搜索算法找到的路径由图的节点和边组成。
图搜索算法可以分为三类：
1）广度优先搜索。广度优先搜索在所有方向上都进行平等地探索。
2）Dijkstra算法（统一代价搜索）。Dijkstra算法优先考虑探索哪些路径。
3）A*算法。A*算法是对Dijkstra算法的修改，该算法针对单个目标进行优化。
广度优先搜索的关键思想是：跟踪一个称为边界的扩展环。
边境如何扩张：
实现：
重复这些步骤，直到边界为空：
1.从边界中拾取并删除一个位置。
2.通过观察该位置的邻居来扩展边界。跳过墙壁（障碍）。将任何未到达的邻居添加到边界和到达集。
这个循环是图形搜索算法的精髓，包括A*。
但是如何找到最短的路径呢？循环实际上并没有构建路径；它只是告诉我们如何参观地图上的一切。
每个位置的came_from都指向我们来自的地方。这些就像“面包屑”。它们足以重建整个路径。
重建路径的代码很简单：沿着came_from的指向从目标向后移动到起点。
早退
利用广度优先搜索，我们找到了从一个位置到所有其他位置的路径。
广度优先搜索种，路径中的每一步具有相同的“成本”。
在某些寻路场景中，不同类型的移动会产生不同的成本。
在Dijkstra的算法中，我们使用与起始点的实际距离将优先级队列排序。
相反，在贪婪最佳优先搜索（Greedy Best First Search）中，我们使用到目标的估计距离将优先级队列排序。
因此，当没有太多障碍物，且路径没有那么好时，这种算法运行得比Dijkstra更快。
对复杂的图，找到又快又短的路径，可以使用A*算法。
Dijkstra的算法可以很好地找到最短路径，但它浪费时间去探索那些没有前景的方向。
A*算法使用当前位置下与起点的实际距离和以及到目标的估计距离。
比较算法：
Dijkstra的算法计算与起点的距离。
Greedy Best First Search估计到目标点的距离。
A*使用这两个距离的总和。
当Greedy Best First Search找到正确答案时，A*也会找到，探索同一领域。
A*是两全其美。
应该使用哪种算法在图上查找路径？
1.如果要查找从所有位置起始或到所有位置的路径，使用广度优先搜索或Dijkstra算法。
2.如果想找到通往一个位置或几个目标中最接近的位置的路径，使用Greedy Best First Search或A*。
关于最佳路径：
广度优先搜索和Dijkstra算法保证在给定输入图的情况下找到最短路径。
如果启发式距离从不大于真实距离，则保证A*找到最短路径。
性能：
最好的做法是消除图中不必要的位置。
减小图的大小有助于所有的图搜索算法。
之后，尽可能使用最简单的算法，更简单的队列运行得更快。
贪婪最佳优先搜索通常比Dijkstra的算法运行得更快，但不会产生最佳路径。
A*是满足大多数寻路需求的好选择。
图形搜索算法可以用于任何类型的图。
图上的移动成本变成在图边上的权重。
启发式距离不容易转化到不同的图中，必须为每种类型的图设计一个启发式距离。
