c++ - 我可以使用提升图实现潜在场/深度优先避障方法吗？

Question

我在 Matlab 中实现了一个避障算法，它为图中的每个节点分配一个电位并尝试降低这个电位（路径规划的目标是全局最小值）。现在可能会出现局部最小值，因此（全球）规划需要一种方法来摆脱这些。我使用该策略来列出可以从已经访问过的节点访问的开放节点列表。我接下来访问潜力最小的开放节点。

我想在 C++ 中实现它，我想知道 Boost Graph 是否已经有这样的算法。如果没有 - 如果我必须自己编写算法并且我还必须创建自己的图形类，那么使用这个库有什么好处，因为图形太大而不能作为邻接列表/边列表存储在内存中。

任何建议表示赞赏！

Answer 1

boost::graph提供最短路径/成本最小化算法列表。您可能对以下内容感兴趣： Dijkstra Shortest path , A*。
算法可以很容易地定制。如果这不完全符合您的需求，请查看访问者概念。它允许您在某个预定义的事件点自定义您的算法。

最后，分布式 BGL处理巨大的图（可能有数百万个节点）。如果您的图表不适合内存，它将为您工作。

您可以在此处找到 Boost Graph Library 的良好概述。当然，不要犹豫，在 stackoverflow 上询问有关 BGL 的更具体的问题。

Answer 2

在我看来，boost::graph实现新算法真的很棒，因为它提供了各种数据持有者、适配器和常用的东西（显然可以用作新构建算法的一部分）。

由于访问者和其他智能模式的使用，最后一个也是可定制的。

实际上，boost::graph可能需要一些时间来适应，但在我看来，这真的很值得。