BFS、DFS、Dijkstra和A-Star算法的通用实现

BFS、DFS、Dijkstra和A-Star算法实现

事实证明,像BFS、DFS、Dijkstra和A-Star这样的著名算法本质上是同一算法的变种。

换句话说,可以实现一种通用的数据结构,可以在这些算法之间切换,而无需对其核心组件进行更改。虽然需要考虑一些限制,但探索这种方法是有趣的。

您可以在我的GitHub存储库中找到所有这些算法的工作代码。我建议在阅读本文的同时尝试使用代码,因为实际经验比纯理论理解更有助于学习。

图表示

让我们考虑一个具有25个节点的图,以5×5的网格排列,我们的目标是找到从左上角的节点0到右下角的节点24的路径:

每个提到的算法都能够实现这一目标,但它们都有自己的局限性:

  • BFS和DFS算法都适用于无权图,忽略边的权重。虽然它们可以找到任何路径,但不能保证最优路径。
  • Dijkstra算法和A-Star算法都适用于带权图,但不应在含有负权重的图上使用。由于其在路径搜索过程中引入了欧几里得坐标的优化,A-Star算法通常更快。

在本文中,我不涵盖基本概念,希望您已经熟悉它们。如果上述术语对您来说很困扰,您可能也应该学习一下基础知识。然而,玩弄这些代码示例仍然是令人兴奋的。

为了解决这些限制,让我们为每个节点分配虚拟坐标(X,Y):

最后,让我们给图中的每条边赋予一些权重:

在C++中,可以表示如下:

图中的边列表由一个数组的数组表示,其中索引对应于图中每条边的出口节点的编号。然后,每个元素包含一对值:

  1. 每条边的入口节点的编号。
  2. 边的权重。

使用这种简单的构造,我们可以遍历图中的每个节点,并获取关于其连接的所有必要信息:

现在,让我们在图中创建一些自定义连接,以观察我们的通用算法的工作效果。由于此处的代码不是主要关注点,我将提供相关方法的链接:

  • 生成节点列表
  • 创建自定义连接

另外,也可以使用更少的代码懒惰地生成此图中的所有连接和权重。然而,这种方法可能无法全面理解算法在遍历图时实际差异。

通用算法

通用寻路算法的核心是通用数据结构,我们将其称为“队列”,用于此项目。然而,它不是经典的先进先出(FIFO)数据结构。相反,它是一种通用结构,允许我们根据使用的算法改变排队机制。这个“队列”的界面很简单:

在我们深入了解“队列”的细节之前,让我们先检查遍历算法本身。

从本质上讲,它与典型的A-Star或Dijkstra算法非常相似。首先,我们需要初始化一组集合,使我们能够:

  • 维护一个未处理过的节点列表(白色),当前正在处理的节点列表(灰色)和已处理/已访问的节点列表(黑色)。
  • 跟踪从起始节点到集合中每个节点的最短路径的当前距离。
  • 存储一组先前-下一个节点对的列表,允许我们在之后重建最终路径。

main.cpp#L18:

接下来,我们需要初始化我们的数据结构。使用GitHub存储库中提供的代码,您只需取消注释必要的代码行即可。代码不设计根据参数选择数据结构,因为我希望您积极地进行实验以获得更好的理解(是的,我是个坚强的家伙:D)。

最后,算法本身。本质上,它是三个算法的组合,并带有一些额外的检查。我们初始化一个“customQueue”,并执行算法直到它变为空。在检查图中的每个相邻节点时,我们将每个可能需要在算法中遍历的节点入队。然后,我们调用 getFirst()方法,该方法仅提取应在算法中遍历的一个节点。

main.cpp#L48:

到目前为止,这个实现与书籍或互联网上的其他示例没有太大的区别。然而,关键在于这里 —— getFirst() 是一个方法,它的主要作用是确定节点遍历的确切顺序。

BFS队列

让我们更仔细地看一下我们队列数据结构的内部工作原理。BFS的队列接口是最简单的一个。bfsQueue.h#L11:

实际上,我们可以简单地将这里的自定义队列接口替换为STL(标准模板库)提供的标准C++队列。然而,这里的目标是通用性。现在,您只需要取消 main 方法中的一行注释并运行这个算法://bfsQueue customQueue; // UNCOMMENT TO USE BFS

结果是,BFS找到了路径 24<-19<-14<-9<-8<-7<-6<-1<-0。

如果我们考虑权重,这条路径的最终成本将是11。然而,请记住,BFS和DFS都不考虑权重。相反,它们遍历图中的所有节点,希望能够尽早或晚一些找到所需的节点

DFS队列

DFS看起来并没有太大的不同。我们只是用一个栈替换了STD队列。dfsStack.h#L11:

DFS找到了路径 24<-23<-22<-21<-20<-15<-10<-5<-0,成本为15(它不优先找到最佳成本)。有趣的是,它与BFS相比遍历的方向是相反的。

Dijkstra队列

现在,Dijkstra算法是图中最著名的贪婪搜索算法。尽管它有已知的限制(无法处理负路径、循环等),但它仍然很受欢迎并且足够高效。

重要的是要注意,此实现中的 getFirst() 方法使用贪婪方法选择要遍历的节点。dijkstraQueue.h#L17:

Dijkstra算法找到了最短和最优路径 24<-19<-18<-13<-12<-7<-6<-1<-0,成本为10。

A-Star

A-Star算法特别适用于在具有坐标的欧几里得空间中寻找路径的情况,例如地图。这就是为什么它在游戏中被广泛使用。它不仅基于最小权重利用了“盲目”贪婪搜索,还考虑了到目标的欧几里得距离。因此,在实际情况下,它通常比Dijkstra算法更高效(请参阅我的其他GitHub项目了解更多详细信息)。aStarQueue.h#L18:

结果是,我们获得了与Dijkstra算法相同的结果,因为它提供了最优的路径。

这个例子可能过于简单,无法展示这些算法在性能上的真正差异。如果您有兴趣探索这些算法的潜力,请参考我的其他项目,该项目高效地实现了这些算法,并采用更具视觉效果的方法与广泛的测试数据。

缺点

然而,Dijkstra和A-Star算法存在一个问题…以上实现在我们的通用数据结构中使用了一个向量(动态数组 [])。每次调用 getFirst(),在向量中查找所需的节点需要 O(N) 的时间。因此,假设主算法也需要 O(N*M) 的时间,其中 M 是平均邻居数量,那么整体复杂度可能接近立方。这将导致大型图上的性能严重下降。

虽然这个示例对于把握所有四种算法在根本上并无太大差异的总体思路非常有用,但魔鬼在于细节。使用通用数据结构高效地实现这四种算法是具有挑战性的。

为了获得最佳性能(通常是99%情况下的主要关注点),应该更多地将精力投入到优化上。例如,对于Dijkstra和A-Star算法,使用优先队列而不是数组是非常合理的。

谈到A-Star算法的优化,提到一些链接是非常有意义的,它们将打开一片深入的优化世界:A*优化和改进(Lucho Suaya)以及JPS+:比A*快100倍(Steve Rabin)。

最后的话

本文的目标是展示所有遍历算法之间的相关性。但是本文中使用的图形示例过于简单,无法展示这些算法在性能上的真正差异。因此,主要使用这些示例来获得概念性的理解,而不是用于实际生产目的。

如果您对探索这些算法的潜力感兴趣,请阅读我基于其他项目的下一篇文章,该项目有效地实现了这些算法,并采用了更具视觉效果的方法和各种测试数据。

敬请关注!