图论 - 如何找到从给定节点以特定代价可达的节点？

Question

图论 - 如何找到从给定节点以特定代价可达的节点？

graph-theory

23

我正在考虑以下问题（非常粗略的描述）：

假设我们有一个图，其中边被分配了一些非负成本，一个起始节点s和一些成本常数C。找出：

从起始节点s到任何节点N的最短路径成本不大于C的可达节点N集合。
对于集合中的每个e，上述最短路径的成本。

基本上是带有成本约束的Dijkstra算法。

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

我一直在研究“可访问性”或“可达性”，但这些似乎是错误的关键字。

最终，我在寻找一种算法，它可以在一个（不可改变的）但相当大的（潜在的~ 100百万条边）图上并行高效地回答许多这样的查询。我想检查文献，但需要关键字的提示。

更新：我的实际问题如下。

假设我们有一个大陆级别的道路网络（被建模为定向图，具有某些边缘和节点的属性，例如如果它是步行道或高速公路）。边缘成本是旅行时间。

我想回答用户查询，例如：从某个给定位置（图节点）开始，在1小时内可到达哪些节点？

我还希望为许多用户（> 10000，如果可能）并行地快速（＆lt;200-300ms，如果可能）回答这些查询。

我认为应该至少有两种优化：

一些预处理，例如选定“中心”节点的预计算距离矩阵。

如果并行进行搜索，则可以从彼此的“临时结果”中受益。

我自己有一些想法，但首先想检查文献以避免重复造轮子。

- lexicore

我已经进行了更多的搜索，有些惊讶。看起来你碰到了一个变体最短路径问题，这个问题并没有被研究得很多（尽管如果完全没有被研究过会令人惊讶）。在这个阶段，我不打算编辑我的算法答案（因为显然对Dijkstra算法进行某些修改是可行的），但如果节点数很大且距离c内的节点数很少，我怀疑某种广度优先搜索比适当修改后的Disjkstra算法更好。 - John Coleman

1

你所描述的应用程序具有一个有趣的特性——许多节点（甚至可能是大多数节点）可以在没有任何实际处理的情况下被丢弃。你不能在一个小时内从洛杉矶到旧金山。这可能允许在每个阶段对搜索空间进行一些激进的修剪——也许某种分支和界限方法可能会起作用。一个有点随意的想法——研究一下运筹学方法在城市规划中的应用。像确定城市中有多少地方距离消防站只有5分钟路程这样的事情显然非常重要，肯定已经有人研究过了。 - John Coleman

你有多少个节点？ - markiz

@markiz 估计需要10-50亿美元。想象一下大陆规模的道路和交通网络（包括铁路）。 - lexicore

请问您能否总结一下所有答案中对于您的情况最有效的部分？特别是与预计算和内存需求相关的权衡方面。谢谢！ - atineoSE

6个回答

4

我一直在研究"可达性"或"覆盖范围"，但似乎这些关键词是错误的。

是的，你说得对。这些是错误的关键词。

首先，让我更精确地重新定义问题。给定一个图G(V,E)，一个节点s和一个常数c，我们想要找到集合R = { (n, d) | s和n之间的距离d <= c}。

这个问题是可达性问题的一个广义版本，其中c是无穷大，在处理大型图形时更加困难。

现在作为预计算的一部分，为了找到集合R，您将必须确定s和所有其他节点之间最短路径的长度。这是All Pairs Shortest Path（APSP）问题的伪装。

因此，第一步，即预计算，是搜索研究库以查找适合您所处理的图形类型的非常快速的APSP算法。算法及其实现决定了预计算运行时间。

第二步是找到一种方式尽可能有效地存储算法结果中的尽可能多的数据，因为您选择的数据结构和算法将决定查询的运行时间。考虑十亿个顶点，算法计算的最短路径数量将约为10^18（来自，到，距离）三元组。如果每个值的大小为4字节，则如果我们将所有这些数据存储在分布式哈希表中，则需要约7艾字节的存储空间（需要额外的存储）。在这种情况下，我们可以实现最多几毫秒的查询时间。

否则，如果您无法存储所有这些数据，则必须压缩数据和/或丢弃其中一些数据。这是一个不同的问题。您可能希望将图形分成许多直径较小的子图（直径必须通过实验确定），然后仅为子图中心的节点存储最短路径信息，并在查询时重新运行非常有效的SSSP（单源最短路径）实现。还有许多其他优化技术可轻松涵盖一本书。无论您做什么，实现小于200毫秒的查询时间都是非常具有挑战性的。

将查询结果缓存到DRAM和本地磁盘中是一个好主意。如果大部分查询都相同，则可以大有裨益。

关于用户数量，由于图是静态的，因此您可以并行处理所有查询。您可以利用高度并行的CPU和GPU。并行处理超过10000个查询并不容易，但您可以利用在图中接近的查询并可能将多个略有不同的查询合并为一个，然后稍后过滤结果。

最后，您编写的用于处理查询的代码本身可以进行优化。深入了解编译器优化和计算机体系结构可以帮助大大缩短查询时间。

- Hadi Brais

3

在加权图中的最短路径距离使该图具有度量空间的结构。用度量空间术语来说，您正在尝试找到以s为中心，半径为c的闭球。也许有一些关于将图作为可计算的离散度量空间处理的研究。偏心率的概念也可以被引入其中——其中节点的偏心率是该点到任何其他点的最大距离。看起来您正在尝试找到最大子图，并且该子图中s的偏心率受到c的限制。

迪杰斯特拉算法显然可以被修改以提供您所寻找的内容。如果在任何时候迪杰斯特拉算法要求您将顶点包含在已访问节点的集合中(对于这些节点，最终距离已知)，但其结果距离超过c，请将该节点舍去而不是将其添加到已访问节点列表中。这将实际上修剪从s可达的节点树。应该是相当高效的。

- John Coleman

请看更新，我已添加实际问题以说明我的任务。我将从Dijkstra或Fredman/Tarjan开始（这很简单），但我认为它不够快。我相信我必须预计算。我也很惊讶我没找到更多信息，但我认为这是因为我缺少正确的关键词。 - lexicore

这似乎是有关联的：https://dev59.com/4H7aa4cB1Zd3GeqPmysy 它并不直接相关，但建议搜索查找节点邻域算法可能会很有成果。 - John Coleman

2

由于您正在寻求从预计算值和临时结果中进行优化，我建议您查看类似 Floyd-Warshall 算法的内容，该算法用于查找所有对之间的最短路径。一旦计算完成，从任何其他节点开始都可以快速地从第一个结果中进行，因此这将为您提供所需的所有临时结果。

不幸的是，该算法在时间复杂度方面为 O(V^3)，在空间复杂度方面为 O(V^2)，因此它相当昂贵。考虑到您的示例问题涉及节点数量相当大，您可能不想在整个数据集上运行该算法，除非您有大量内存要使用来存储此预计算结果。

根据人们进行的搜索类型，您可以将道路网络分成较小的部分，然后在较小的数据集上运行 Floyd-Warshall 算法，以便您不必始终存储整个结果。如果人们正在搜索小距离，例如您的 1 小时远的地方的例子，那么这只会起作用。如果人们正在搜索 1000 英里内的任何东西，将其分成几部分将无济于事，并且在您提供的时间限制内无法实时计算。无论您如何使其高效，搜索大半径的所有内容都需要花费相当长的时间来计算（可能比您的时间限制更长）。

从实际角度来看，最佳解决方案将取决于人们如何使用它以及搜索的分散程度。

即使人们正在搜索距离超过 100 英里的内容，高速公路很可能仍然是最有效的路线，至少对于大部分旅程而言，因此可能可以通过忽略除起点和终点附近的较小道路之外的较小道路来尝试优化长距离，这将显着减少节点数量，从而使 Floyd-Warshall 的计算时间和内存消耗更加合理。不幸的是，这对您没有帮助，因为您仍然需要找到所有小于给定距离的节点。

如果您担心计算速度和对服务器的压力，您可能需要限制要接受的距离的大小。

- DeadEli

1

当我在处理这个问题时，我们通常会使用带有截止值的Dijkstra算法，其中截止值是我们感兴趣的最大成本。

例如，如此处所示arcgis algorithms。

- tomsv

1

那些算法将有效。第一个适用于软环境，其中从一个地方到另一个地方的成本相当大。第二个算法则较不易受影响。

设G为有向图，v为起点，C为剩余成本。

//in case, there is no cycle of cost 0, but in metrical environment there won't be one
GLOBAL SET result = {};
def AchievableNodes(G,v,C):
    for each w: e = (v,w) in Edges:
        if c(e) < C:
            result.addIfNotInResult(w) 
            AchievableNodes(G, w, C-c(e))

AchievableNodes(G, root, C)
print(result)


GLOBAL ARRAY result[|V|] - initialized with 0s.
def AchievableNodes(G, v, C):
    for each w: e = (v,w) in Edges:
        if c(e) < C:
            if result[w] > result[v] + c(e):
                result[w] = result[v] + c(e)
                AchievableNodes(G, w, C-c(e))

AchievableNodes(G, v, C)
print(result)

实际上，我强烈建议将结果存储在某个地方。这样，您可以渐进地将其改进到常数时间。

- xenteros

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sergio Ayestarán · Accepted Answer

你正在处理的问题，正确的术语属于“最短路径算法”的范畴。可达性问题（即Warshal）涉及问题“节点A和B之间是否存在路径？”，它有一个二进制答案，你不需要权重，只需要找到边缘。但在你的情况下，你需要考虑从节点A到节点B的旅行时间。

现在，对于这个问题没有“完美”的解决方案，因为对Dijktra、Floyd、BFS或DFS的微小改变可以用来解决这个问题，但由于图的规模增加了复杂度，这很重要，必须理解如何构建解决方案。使用哪种算法取决于你特定的时间限制和可用硬件的组合。

有两种算法解决你的问题（我假设你已经在某个地方存储了所有的边缘，并且你可以以某种方式查询这个数据库）：

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

2. 然后，你有第二个解决方案，即修改Dijktra、BFS或DFS以根据成本修剪搜索。在这种情况下，由于空间复杂度较高，已经舍弃了Floyd，这意味着你的图形相当庞大，既包含节点又包含边缘。在这种情况下，使用任何算法的变体几乎是相同的解决方案，不同之处在于如何存储图表。所有三个算法都可以修改为能够高效响应你想要的时间，但是支持超过10k个客户端所使用的存储图形的数据库使得差异。在这里，你有另外两个选项：

使用标准 SQL/NoSQL 数据库：由于需要为运行图搜索的代码服务器（因为 C10K 问题而需要多个）提供服务，所以这个数据库应该以某种方式进行分片。我建议您根据数据图本身的大小在这个领域继续研究，但是如果您成功将所有数据放入 Cassandra 群集或类似技术中，则可以优化为所需的响应时间，并且它的扩展性非常好。
利用图形实际上是一个“地图”的事实，找到一种在数据上运行距离查询的方法：这可能需要您更改存储图形的方式，添加像纬度和经度之类的东西。因此，您不再对整个图形运行算法，这是荒谬的，您可以利用从给定节点开始的某个特定分钟数，将其转换为英里（近似值，您可以增加大约 10-20 英里以保险起见）的距离 D，并在数据库上运行查询以获取距离 D 的所有节点，然后您可以针对该小型图形运行所选算法。重要的是要注意，您使用此方法从数据库检索到的图形已经为您提供了解决方案的近似值，如果边缘上的实际旅行时间与旅行距离成比例（这并不总是正确的，这就是为什么它是一个近似值）。要在小规模实施此功能，可以使用 PostgreSQL + PostGIS，这使您能够运行此类查询，但您需要做一些研究以尝试找到最适合您的解决方案。

希望对您有所帮助！