图论 - 如何在一定成本内找到从给定节点可到达的节点？

Question

我正在考虑以下问题(非常粗略的描述):

假设我们有一个图表,其中边缘被分配了一些非负成本,一个起始节点s和一些成本常数C.找出:

• 一组节点N,从到达s那里的最短路径的从开始节点的成本s在任何节点N不大于C.
• 对于上面的每个e集合 - 最短路径的成本.

基本上Dijkstra有成本约束.

我的主要问题是:图论中这个问题的正确术语是什么？

我一直在关注"可访问性"或"可达性",但这些似乎是错误的关键字.

最后,我正在寻找一种算法,它可以在一个(不可修改的)但相当大的(可能约1亿个边缘)图形上并行地有效地回答许多这样的查询.我想查看文献,但需要提供正确的关键词提示.

更新:我的实际问题如下.

假设我们获得了一个大陆规模的道路网络(模拟为有向图,在边缘和节点上具有一些属性,如果它是行人路或高速公路).边缘成本是旅行时间.

我想回答用户查询,例如:从某个给定位置(图形节点)开始,哪些节点可在1小时内到达？

我也想非常快地(对于许多用户来说,如果可能的话,<200-300ms)(并且如果可能的话,> 200,如果可能)并行地回答这些查询.

我认为应该至少有两种可能的优化:

• 一些合理大小的预计算,例如预先计算的所选"中心"节点的距离矩阵.
• 如果搜索是并行进行的,则可以从彼此的"临时结果"中获益.

我自己有一些想法,但我首先要检查文献,以避免重新发明轮子.

Answer 1

您正在处理的问题的正确术语是“最短路径算法”系列。可达性问题（即 Warshal）处理的问题是“节点 A 和 B 之间是否存在路径？” 它有一个二元答案，在这种情况下你不需要权重，你只需要寻找边缘。但是在您的情况下，您需要考虑在每种情况下从节点 A 到节点 B 所需的时间。

现在，没有“完全”适合这个问题，因为 Dijktra's、Floyd's、BFS 或 DFS 上的一个小的变化可以用来解决这个问题，但是由于图的大小，你增加了复杂性，这是很重要的理解如何构建您的解决方案。使用哪种算法取决于您的时间限制和可用硬件的特定组合。

您的问题有 2 种算法解决方案（我假设您已经将所有边存储在某处，并且您可以以某种方式查询该数据库）：

1. 在理想（想象）的世界中，您将运行 Floyd 算法，将结果矩阵保存在 Redis 之类的东西中，就是这样，您可以在不到 10 毫秒的时间内处理您的请求，如果客户端数量增加，您可以添加更多 Redis 服务器作为需要，因为图表不太可能经常更改（因为在您的特定问题中您有道路信息）。问题在于解决方案的空间复杂性，最好的一点是一切都是预先计算的，这意味着您对请求的响应时间最短。为了能够实现这种变化，您需要大量空间，即使是一个将数据库存储在磁盘（是磁盘，不是内存）上的 redis 集群和所有带有 SSD 的服务器也应该足够了，当数量增加时，此选项可以很好地扩展并发客户端的数量增长，时间响应非常快。但是，您是否可以使用此解决方案取决于图中节点的数量：即使您需要使用每条边预先计算距离，您也只需要空间来存储 NxN 矩阵，即 N 是图中节点的数量，如果这个矩阵适合 redis，那么你可以使用这个算法并预先计算所有节点之间的所有“距离”（在你的情况下，这是成本的总和，也就是“旅行时间”）。稍后，当您收到请求时，您需要查询生成的矩阵以获取行程时间小于给定值的所有节点，将此矩阵存储在 redis 中时还有一个额外的优化可以让您完全获取节点编号快速使用排序集。即使您需要使用每条边预先计算距离，您也只需要空间来存储 NxN 矩阵，即 N 是图中节点的数量，如果该矩阵适合 redis，那么您可以使用此算法并预先计算所有“距离” （在您的情况下，这是所有节点之间的成本总和，即“旅行时间”）。稍后，当您收到请求时，您需要查询生成的矩阵以获取行程时间小于给定值的所有节点，将此矩阵存储在 redis 中时还有一个额外的优化可以让您完全获取节点编号快速使用排序集。即使您需要使用每条边预先计算距离，您也只需要空间来存储 NxN 矩阵，即 N 是图中节点的数量，如果该矩阵适合 redis，那么您可以使用此算法并预先计算所有“距离” （在您的情况下，这是所有节点之间的成本总和，即“旅行时间”）。稍后，当您收到请求时，您需要查询生成的矩阵以获取行程时间小于给定值的所有节点，将此矩阵存储在 redis 中时还有一个额外的优化可以让您完全获取节点编号快速使用排序集。（在您的情况下，这是所有节点之间的成本总和，即“旅行时间”）。稍后，当您收到请求时，您需要查询生成的矩阵以获取行程时间小于给定值的所有节点，将此矩阵存储在 redis 中时还有一个额外的优化可以让您完全获取节点编号快速使用排序集。（在您的情况下，这是所有节点之间的成本总和，即“旅行时间”）。稍后，当您收到请求时，您需要查询生成的矩阵以获取行程时间小于给定值的所有节点，将此矩阵存储在 redis 中时还有一个额外的优化可以让您完全获取节点编号快速使用排序集。

2. 然后您有第二个解决方案，即修改 Dijktra、BFS 或 DFS 以根据成本修剪搜索，仅此而已。在这种情况下，由于空间复杂度高，您已经放弃了 Floyd，这意味着您的图在节点和边上都相当大。在这种情况下，使用任何算法的变体的解决方案几乎相同，这使得不同的是您如何存储图形。可以修改所有 3 种算法以在您想要的时间内有效响应，但要支持超过 10k 客户端，用于存储图形的数据库会有所不同。在这里你还有另外两个选择：

• 使用标准 SQL/NoSQL 数据库：该数据库应该以某种方式进行分片，因为它应该为您的代码服务器（复数，因为 C10K 问题）运行图上的搜索。我建议您根据图形数据本身的大小继续在该领域进行研究，但是如果您设法将所有数据放入 Cassandra 集群或类似技术中，则可以针对您想要的响应时间进行优化，并且秤真的很好。
• 您可以利用图形实际上是“地图”这一事实，并找到一种对数据进行距离查询的方法：这可能需要您更改存储图形的方式以添加诸如纬度和经度之类的内容。因此，与其对全图运行算法，这是荒谬的，您可以通过使用以下事实来优化整个过程，即从给定节点给定一定的分钟数，您可以将其转换为以英里为单位的距离 D（大约，您为了安全起见，可以添加 10-20 英里之类的东西），然后在数据库上运行查询以获取该距离 D 内的所有节点，然后针对该小图运行您选择的算法。重要的是要注意，如果边缘的实际旅行时间与旅行的距离成正比（这并不总是正确的，这就是为什么它是近似值）。要以小规模实现这一点，您将使用 PostgreSQL + PostGIS，它允许您运行此类查询，但您需要在此处进行一些研究，以尝试找到最适合您的解决方案。

希望能帮助到你！