图论 - 如何在一定成本内找到从给定节点可达的节点？
Graph Theory - How to find nodes reachable from a given node within certain cost?
我正在考虑以下问题（非常粗略的描述）：
假设我们有一个图，其中边被分配了一些非负成本、起始节点 s 和一些成本常量 C。找出：
- 一组节点
N，可从 s 到达，其中从起始节点 s 到 N 中任何节点的最短路径的成本不大于比 C.
- 对于上述集合中的每个
e - 最短路径的成本。
基本上Dijkstra有成本限制。
我的主要问题是：这个问题在图论中的正确术语是什么？
我一直在查看 "accessibility" 或 "reachability"，但这些似乎是错误的关键字。
最终我正在寻找一种算法，该算法可以在一个（不可修改的）但相当大（可能约 1 亿条边）的图上并行有效地回答许多此类查询。我想查看文献，但需要有关正确关键字的提示。
更新：我的实际问题如下
假设我们有一个大陆大小的道路网络（建模为有向图，在边和节点上具有一些属性，例如人行道或高速公路）。边成本是旅行时间。
我想回答用户查询，例如：从某个给定位置（图形节点）开始，1 小时内可以到达哪些节点？
我还想为许多用户（>10000，如果可能）并行快速回答这些查询（<200-300ms，如果可能）。
我认为至少应该有两个可能的优化：
- 一些合理大小的预计算，例如选定 "central" 个节点的预计算距离矩阵。
- 如果并行进行搜索，它们可能会从彼此的 "temporary results" 中获益。
我有一些自己的想法，但我想先查阅文献，以免重新发明轮子。
加权图中的最短路径距离为该图提供了度量结构 space。在公制 space 术语中，您试图找到以 s 为中心、半径为 c 的闭球。也许有一些研究将图形视为计算上易于处理的离散度量 spaces。偏心率的概念也可以发挥作用——节点的偏心率是从该点到任何其他点的最大距离。看起来您正在尝试找到具有 属性 的最大子图，子图中 s 的偏心率以 c 为界。
Dijkstra 的算法显然可以修改以提供您正在寻找的内容。如果在任何时候 Dijkstra 的算法会让您在访问节点集中包含一个顶点（最终距离已知的节点）但结果距离超过 c，则丢弃该节点而不是将其添加到列表中访问过的节点。这实际上将修剪从 s 可达的节点树。应该是相当有效的。
当我使用它时，我们曾经使用截止值调用 Dijkstra，其中截止值是我们感兴趣的最大成本。
例如此处使用的示例 arcgis algorithms。
由于您正在从预先计算的值和临时结果中寻找优化，我建议您查看类似 Floyd-Warshall 算法的算法，该算法用于查找所有对的最短路径。一旦计算一次，就可以从第一个结果快速完成从任何其他节点开始的操作，因此这将为您提供所需的所有临时结果。
不幸的是，该算法的时间复杂度为 O(V^3)，space 复杂度为 O(V^2)，因此它相当昂贵。鉴于您的示例问题听起来非常大，关于节点数量，您可能不希望 运行 对整个数据集使用该算法，除非您有大量内存要通过存储来使用预先计算的结果。
根据人们进行的搜索类型，您可以将道路网络分成更小的部分，然后 运行 在较小的数据集上使用 Floyd-Warshall 算法，这样您就不必始终存储整个结果。这仅在人们搜索小距离时才有效，例如您在 1 小时以外的地方的示例。如果人们在 1000 英里内搜索任何东西，将其分解成多个部分将无济于事，并且无法在您提供的时间限制内实时完成计算。尽可能高效地搜索像这样的大半径内的所有内容将花费大量时间来计算（可能远远超过您的时间限制）。
实际上，最好的解决方案将取决于人们如何使用它以及搜索的分散程度。
即使人们搜索 100 多英里以外的东西，高速公路也可能是最有效的路线，至少对于大部分行程而言，因此可能可以尝试对长距离进行一些优化通过忽略除行程起点和终点附近以外的较小道路，这将显着减少长距离的节点数量，使 Floyd-Warshall 消耗的计算时间和内存更加合理。不幸的是，这对您没有帮助，因为您仍然需要找到所有小于给定距离的节点。
如果您担心服务器的计算速度和压力，您可能需要限制您要接受的距离大小。
这些算法会起作用。第一个对于软环境来说很快，从一个地方到另一个地方的成本相当大。第二个不太容易受到影响。
设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)
实际上，我强烈建议将结果存储在某处。然后你可以渐进地改进它直到常数时间。
I've been looking at "accessibility" or "reachability" but these seem
to be wrong keywords.
是的，你是对的。这些是错误的关键字。
首先，让我更准确地重新定义问题。给定一个图 G(V,E)，一个节点 s 和 a 常量 c，我们要找到集合R = { (n, d) | s 和 n 之间的距离是 d <= c}.
这个问题是可达性问题的一般化版本，其中 c 是无穷大，考虑到大图要困难得多。
现在，作为预计算的一部分，要找到集合 R，您必须确定 s 之间的最短路径的长度和所有其他节点。这是伪装的所有对最短路径 (APSP) 问题。
所以第一步，即预计算，是在研究库中搜索适合您正在处理的图形类型的真正快速的 APSP 算法。算法及其实现决定了预计算运行时间。
第二步是尽可能多地从算法的结果中找到一种存储方式，并且尽可能高效，因为您在此处选择的数据结构和算法将决定 运行 时间询问。考虑到十亿个顶点，算法计算出的最短路径的数量将约为 10^18（从、到、距离）三元组。如果每个值的大小为 4 字节，那么如果我们将所有这些数据存储在分布式哈希 table 中（这需要额外的存储空间），您将需要大约 7 艾字节。在这种情况下，我们最多可以实现几毫秒的查询时间。
否则，如果您不能存储所有这些数据，您将不得不压缩数据 and/or 丢弃其中的一些数据。现在这是一个不同的问题。您可能希望将图划分为许多小直径的子图（直径必须通过实验确定），然后仅为子图中心的节点存储最短路径信息，并且在查询时您将不得不重新运行一个非常有效的SSSP（单源最短路径）的实现。还有许多其他优化技术可以轻松跨越一本书。无论您做什么，实现 <200 毫秒的查询时间都非常具有挑战性。
在 DRAM 和本地磁盘中缓存查询结果是个好主意。如果大部分查询相同，这会很有帮助。
关于用户数量，由于图形是静态的，您可以并行化所有查询。您可以利用高度并行的 CPU 和 GPU。 >10000 个并行查询并非微不足道，但您可以利用图表中接近的查询，并可能将多个略有不同的查询合并为一个，然后过滤出结果。
最后，您编写的用于处理查询本身的代码可以进行优化。深入了解编译器优化和计算机体系结构有助于大幅减少查询时间。
您正在处理的问题的正确术语属于“最短路径算法”系列。可达性问题（即 Warshal）处理“节点 A 和 B 之间是否有路径？”的问题。它有一个二进制答案，在这种情况下你不需要权重，你只需要寻找边缘。但是在您的情况下，您需要考虑在每种情况下从节点 A 到节点 B 所需的时间。
现在，没有“完全”适合这个问题的方法，因为可以使用 Dijktra、Floyd、BFS 或 DFS 的小改动来解决这个问题，但是由于图形的大小，你会增加复杂性这对于了解如何构建解决方案很重要。使用哪种算法取决于您的时间限制和可用硬件的具体组合。
您的问题有 2 种算法解决方案（我假设您已经将所有边存储在某处并且您可以以某种方式查询该数据库）：
在理想的（想象的）世界中，您会 运行 弗洛伊德算法，将生成的矩阵保存在 Redis 之类的东西中，仅此而已，您可以在不到 10 毫秒的时间内处理您的请求，如果客户端数量增加，您可以根据需要添加更多的 redis 服务器，因为图形不太可能经常更改（因为在您的特定问题中您有道路信息）。问题在于解决方案的 space 复杂性，最好的一点是所有内容都是预先计算的，这意味着您对请求的响应时间最短。
为了能够实现这个的一些变体，你需要很多 space，甚至是一个在磁盘上存储数据库的 redis 集群（是磁盘，而不是内存）和所有带有 SSD 的服务器都应该足够了，这个选项可以扩展那么当并发客户端数量增长并且时间响应非常快时。但是您是否可以使用此解决方案取决于图中的节点数：即使您需要使用每条边预先计算距离，您只需要 space 来存储 NxN 的矩阵，即 N 个节点数在你的图表中，如果这个矩阵适合 redis 那么你可以使用这个算法并预先计算所有节点之间的所有“距离”（在你的情况下这是成本 a.k.a “旅行时间”的总和）。稍后当您收到请求时，您需要查询结果矩阵以获取行程时间小于给定值的所有节点，将此矩阵存储在 redis 中时有一个额外的优化，可以让您完全获取节点编号使用排序集快速。
然后你有第二个解决方案，即修改 Dijktra、BFS 或 DFS 以 p运行e 基于成本的搜索，仅此而已。在这种情况下，由于 space 的高复杂性，您已经放弃了 Floyd，这意味着您的图在节点和边上都相当庞大。在这种情况下，使用任何算法的变体，解决方案几乎相同，不同之处在于您如何存储图形。可以修改所有 3 种算法以在您想要的时间内有效响应，但要支持超过 10k 的客户端，您用于存储图形的数据库会有所不同。在这里你还有另外两个选择：
- 使用标准 SQL/NoSQL 数据库：这个数据库应该以某种方式进行分片，因为它应该服务于您的代码服务器（复数，因为 C10K 问题）运行 在图上进行搜索。我建议你根据图形数据本身的大小继续在这个领域的研究，但是如果你设法将所有数据放在 Cassandra 集群或类似技术中，它可以优化到你想要的响应时间并且它缩放得很好。
- 您利用了图表实际上是“地图”这一事实，并且找到了一种对数据进行 运行 宁距离查询的方法：这可能需要您更改存储图表的方式添加纬度和经度之类的东西。因此，与其 运行 将算法针对完整图进行优化，这是荒谬的，您可以通过使用从给定节点给定一定分钟数的事实来优化整个过程，您可以将其转换为距离 D英里（大约，为了安全起见，您可以添加 10-20 英里之类的东西）然后您 运行 查询数据库以获取该距离 D 以内的所有节点，然后您 运行您针对该小图选择的算法。重要的是要注意，如果边缘的实际行进时间与行进的距离成正比（这并不总是正确的，这就是为什么它是一个近似值）。要在小范围内实现这一点，您可以使用 PostgreSQL + PostGIS，它允许您 运行 此类查询，但是您需要在这里做一些研究以尝试找到 scales/works 最好的解决方案给你。
希望对您有所帮助！
我正在考虑以下问题（非常粗略的描述）：
假设我们有一个图，其中边被分配了一些非负成本、起始节点 s 和一些成本常量 C。找出：
- 一组节点
N，可从s到达，其中从起始节点s到N中任何节点的最短路径的成本不大于比C. - 对于上述集合中的每个
e- 最短路径的成本。
基本上Dijkstra有成本限制。
我的主要问题是：这个问题在图论中的正确术语是什么？
我一直在查看 "accessibility" 或 "reachability"，但这些似乎是错误的关键字。
最终我正在寻找一种算法，该算法可以在一个（不可修改的）但相当大（可能约 1 亿条边）的图上并行有效地回答许多此类查询。我想查看文献，但需要有关正确关键字的提示。
更新：我的实际问题如下
假设我们有一个大陆大小的道路网络（建模为有向图，在边和节点上具有一些属性，例如人行道或高速公路）。边成本是旅行时间。
我想回答用户查询，例如：从某个给定位置（图形节点）开始，1 小时内可以到达哪些节点？
我还想为许多用户（>10000，如果可能）并行快速回答这些查询（<200-300ms，如果可能）。
我认为至少应该有两个可能的优化：
- 一些合理大小的预计算，例如选定 "central" 个节点的预计算距离矩阵。
- 如果并行进行搜索，它们可能会从彼此的 "temporary results" 中获益。
我有一些自己的想法，但我想先查阅文献，以免重新发明轮子。
加权图中的最短路径距离为该图提供了度量结构 space。在公制 space 术语中，您试图找到以 s 为中心、半径为 c 的闭球。也许有一些研究将图形视为计算上易于处理的离散度量 spaces。偏心率的概念也可以发挥作用——节点的偏心率是从该点到任何其他点的最大距离。看起来您正在尝试找到具有 属性 的最大子图，子图中 s 的偏心率以 c 为界。
Dijkstra 的算法显然可以修改以提供您正在寻找的内容。如果在任何时候 Dijkstra 的算法会让您在访问节点集中包含一个顶点（最终距离已知的节点）但结果距离超过 c，则丢弃该节点而不是将其添加到列表中访问过的节点。这实际上将修剪从 s 可达的节点树。应该是相当有效的。
当我使用它时，我们曾经使用截止值调用 Dijkstra，其中截止值是我们感兴趣的最大成本。
例如此处使用的示例 arcgis algorithms。
由于您正在从预先计算的值和临时结果中寻找优化，我建议您查看类似 Floyd-Warshall 算法的算法，该算法用于查找所有对的最短路径。一旦计算一次，就可以从第一个结果快速完成从任何其他节点开始的操作，因此这将为您提供所需的所有临时结果。
不幸的是，该算法的时间复杂度为 O(V^3)，space 复杂度为 O(V^2)，因此它相当昂贵。鉴于您的示例问题听起来非常大，关于节点数量，您可能不希望 运行 对整个数据集使用该算法，除非您有大量内存要通过存储来使用预先计算的结果。
根据人们进行的搜索类型，您可以将道路网络分成更小的部分，然后 运行 在较小的数据集上使用 Floyd-Warshall 算法，这样您就不必始终存储整个结果。这仅在人们搜索小距离时才有效，例如您在 1 小时以外的地方的示例。如果人们在 1000 英里内搜索任何东西，将其分解成多个部分将无济于事，并且无法在您提供的时间限制内实时完成计算。尽可能高效地搜索像这样的大半径内的所有内容将花费大量时间来计算（可能远远超过您的时间限制）。
实际上，最好的解决方案将取决于人们如何使用它以及搜索的分散程度。
即使人们搜索 100 多英里以外的东西，高速公路也可能是最有效的路线，至少对于大部分行程而言，因此可能可以尝试对长距离进行一些优化通过忽略除行程起点和终点附近以外的较小道路，这将显着减少长距离的节点数量，使 Floyd-Warshall 消耗的计算时间和内存更加合理。不幸的是，这对您没有帮助，因为您仍然需要找到所有小于给定距离的节点。
如果您担心服务器的计算速度和压力，您可能需要限制您要接受的距离大小。
这些算法会起作用。第一个对于软环境来说很快，从一个地方到另一个地方的成本相当大。第二个不太容易受到影响。
设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)
实际上，我强烈建议将结果存储在某处。然后你可以渐进地改进它直到常数时间。
I've been looking at "accessibility" or "reachability" but these seem to be wrong keywords.
是的，你是对的。这些是错误的关键字。
首先，让我更准确地重新定义问题。给定一个图 G(V,E)，一个节点 s 和 a 常量 c，我们要找到集合R = { (n, d) | s 和 n 之间的距离是 d <= c}.
这个问题是可达性问题的一般化版本，其中 c 是无穷大，考虑到大图要困难得多。
现在，作为预计算的一部分，要找到集合 R，您必须确定 s 之间的最短路径的长度和所有其他节点。这是伪装的所有对最短路径 (APSP) 问题。
所以第一步，即预计算，是在研究库中搜索适合您正在处理的图形类型的真正快速的 APSP 算法。算法及其实现决定了预计算运行时间。
第二步是尽可能多地从算法的结果中找到一种存储方式，并且尽可能高效，因为您在此处选择的数据结构和算法将决定 运行 时间询问。考虑到十亿个顶点，算法计算出的最短路径的数量将约为 10^18（从、到、距离）三元组。如果每个值的大小为 4 字节，那么如果我们将所有这些数据存储在分布式哈希 table 中（这需要额外的存储空间），您将需要大约 7 艾字节。在这种情况下，我们最多可以实现几毫秒的查询时间。
否则，如果您不能存储所有这些数据，您将不得不压缩数据 and/or 丢弃其中的一些数据。现在这是一个不同的问题。您可能希望将图划分为许多小直径的子图（直径必须通过实验确定），然后仅为子图中心的节点存储最短路径信息，并且在查询时您将不得不重新运行一个非常有效的SSSP（单源最短路径）的实现。还有许多其他优化技术可以轻松跨越一本书。无论您做什么，实现 <200 毫秒的查询时间都非常具有挑战性。
在 DRAM 和本地磁盘中缓存查询结果是个好主意。如果大部分查询相同，这会很有帮助。
关于用户数量，由于图形是静态的，您可以并行化所有查询。您可以利用高度并行的 CPU 和 GPU。 >10000 个并行查询并非微不足道，但您可以利用图表中接近的查询，并可能将多个略有不同的查询合并为一个，然后过滤出结果。
最后，您编写的用于处理查询本身的代码可以进行优化。深入了解编译器优化和计算机体系结构有助于大幅减少查询时间。
您正在处理的问题的正确术语属于“最短路径算法”系列。可达性问题（即 Warshal）处理“节点 A 和 B 之间是否有路径？”的问题。它有一个二进制答案，在这种情况下你不需要权重，你只需要寻找边缘。但是在您的情况下，您需要考虑在每种情况下从节点 A 到节点 B 所需的时间。
现在，没有“完全”适合这个问题的方法，因为可以使用 Dijktra、Floyd、BFS 或 DFS 的小改动来解决这个问题，但是由于图形的大小，你会增加复杂性这对于了解如何构建解决方案很重要。使用哪种算法取决于您的时间限制和可用硬件的具体组合。
您的问题有 2 种算法解决方案（我假设您已经将所有边存储在某处并且您可以以某种方式查询该数据库）：
在理想的（想象的）世界中，您会 运行 弗洛伊德算法，将生成的矩阵保存在 Redis 之类的东西中，仅此而已，您可以在不到 10 毫秒的时间内处理您的请求，如果客户端数量增加，您可以根据需要添加更多的 redis 服务器，因为图形不太可能经常更改（因为在您的特定问题中您有道路信息）。问题在于解决方案的 space 复杂性，最好的一点是所有内容都是预先计算的，这意味着您对请求的响应时间最短。 为了能够实现这个的一些变体，你需要很多 space，甚至是一个在磁盘上存储数据库的 redis 集群（是磁盘，而不是内存）和所有带有 SSD 的服务器都应该足够了，这个选项可以扩展那么当并发客户端数量增长并且时间响应非常快时。但是您是否可以使用此解决方案取决于图中的节点数：即使您需要使用每条边预先计算距离，您只需要 space 来存储 NxN 的矩阵，即 N 个节点数在你的图表中，如果这个矩阵适合 redis 那么你可以使用这个算法并预先计算所有节点之间的所有“距离”（在你的情况下这是成本 a.k.a “旅行时间”的总和）。稍后当您收到请求时，您需要查询结果矩阵以获取行程时间小于给定值的所有节点，将此矩阵存储在 redis 中时有一个额外的优化，可以让您完全获取节点编号使用排序集快速。
然后你有第二个解决方案，即修改 Dijktra、BFS 或 DFS 以 p运行e 基于成本的搜索，仅此而已。在这种情况下，由于 space 的高复杂性，您已经放弃了 Floyd，这意味着您的图在节点和边上都相当庞大。在这种情况下，使用任何算法的变体，解决方案几乎相同，不同之处在于您如何存储图形。可以修改所有 3 种算法以在您想要的时间内有效响应，但要支持超过 10k 的客户端，您用于存储图形的数据库会有所不同。在这里你还有另外两个选择：
- 使用标准 SQL/NoSQL 数据库：这个数据库应该以某种方式进行分片，因为它应该服务于您的代码服务器（复数，因为 C10K 问题）运行 在图上进行搜索。我建议你根据图形数据本身的大小继续在这个领域的研究，但是如果你设法将所有数据放在 Cassandra 集群或类似技术中，它可以优化到你想要的响应时间并且它缩放得很好。
- 您利用了图表实际上是“地图”这一事实，并且找到了一种对数据进行 运行 宁距离查询的方法：这可能需要您更改存储图表的方式添加纬度和经度之类的东西。因此，与其 运行 将算法针对完整图进行优化，这是荒谬的，您可以通过使用从给定节点给定一定分钟数的事实来优化整个过程，您可以将其转换为距离 D英里（大约，为了安全起见，您可以添加 10-20 英里之类的东西）然后您 运行 查询数据库以获取该距离 D 以内的所有节点，然后您 运行您针对该小图选择的算法。重要的是要注意，如果边缘的实际行进时间与行进的距离成正比（这并不总是正确的，这就是为什么它是一个近似值）。要在小范围内实现这一点，您可以使用 PostgreSQL + PostGIS，它允许您 运行 此类查询，但是您需要在这里做一些研究以尝试找到 scales/works 最好的解决方案给你。
希望对您有所帮助！