时间戳

首页 > 解决方案 > 从点之间的距离计算图

graph - 从点之间的距离计算图

问题描述

我有一组地理点（纬度，经度），我想计算一个有向图，其中：

我能够计算任何一对节点之间路径的持续时间。现在，我正在执行以下操作：

  1. 计算每对节点之间的持续时间
  2. 对于每对节点X，Y ，如果没有节点Z ，则X和Y之间存在一条边，使得X -> Z的持续时间加上Z -> Y的持续时间与X ->的持续时间相同是。

我已经为节点的一个子集测试了这种方法，它似乎有效，但是由于我有大约 2000 个节点并且节点之间的持续时间的计算在计算上是昂贵的（因为它涉及计算最短路径），我想知道如果有更好的方法。

一些额外的（可能不相关的）信息：

任何帮助将不胜感激

标签： graphopenstreetmapgraph-theorygeoosrm

解决方案

我将从运行 Delaunay 三角剖分开始，这将使您了解路径结构“应该”是什么样的（理论上）。理论上，一旦你有了 delaunary 三角测量，就很容易找到最短路径。然而，在实践中，您使用的是道路网络而不是点对点距离，因此您必须挑战这些假设。

  1. 首先建立一个给定 Delaunay 三角剖分的方法。三角剖分的示例如下所示。假设 HJG 点位于市中心，其周围的点是围绕它的高速公路。以 65 英里/小时左右的速度限制说。这意味着从 ABCG 出发可能比 AHG 更快。

  2. 对于 Delaunay 三角剖分中的每条边。确定两个方向上边缘的持续时间。这将为您提供初始权重（如果您可以确定 AH 的最短路径实际上是 ABH，它也可能会影响三角测量）。如果没有办法绕过更快的路线。ABCG 比 AHG 示例快。那么你可能已经完成了。如果不是，你将不得不尝试收缩边缘，这取决于你的数据，可能需要做所有的路线，因为你不能确定一些模糊的路径可以让它更快。可悲的是，三角测量无法解释边缘之间的速度差异。

在此处输入图像描述

  1. 如果您可以设置它以告诉您它确实通过了哪个点，那么您可以避免在所有路径上运行它。IE：如果你可以说让它告诉你最快的路径 AF，并且它说它使用 AHGF，那么你可以合理地确定 AHG 和 HGF 是 AG 和 HF 之间的最短路径，你不需要运行那些. 但是，如果你发现AF实际上取的是ABCEF，那么显然两条路线之间的速度差异很大，你还应该检查到AG的最快路线，以确保它实际上是AHG。每当您找到更快的边缘时，请务必添加到三角测量中。您实际上可能能够添加多个边缘。基本上这里的想法是，如果速度无关紧要，三角测量可以让您了解什么应该是最快的路线。但是，您需要确认或拒绝该假设。基本上每个节点。通过 BFS 找到到所有点的最短路径。走最长的路并探索它。

  2. 为了帮助#3，它可能有助于图中边缘的顶点路径覆盖。创建从每个点到所有最远点的路径，直到覆盖所有点。IE：ABCD ABCE AHGF AHJKL AIK（也是方向相反的顺序）。然后您可以从 AD、AE、AF、AL 和 AK 运行最短路径。如果这些路径与预期路径匹配，那么您就完成了。如果没有，您将在上面#3 使用的方法中不断改进。但最坏的情况是，我不确定有没有办法比理论上所有最短路径都快得多，这种方法大约是 O(VE)。

  3. 理论上#4 需要从每个顶点开始。但是，如果连接路径作为最短路径有效，则可以跳过顶点，因此我可能会建议开始检查具有最少（未验证？）边数的顶点。尽管如此，您可能需要对所有对进行 100% 确保只有最短的边连接每个节点。

  4. 对于测试，我建议这样做：随机选择 2000 个点中的 10-200 个。在这 10-200 点上运行算法。然后在这些点上运行所有路径。如果他们不同意，请仔细查看他们不同意的原因。随时在您的答案和评论中添加任何“例外”案例。重复多次，看看有没有分歧。注意所有的分歧。如果没有分歧，请尝试在整个 2000 点集上运行。我强烈建议在第 2 步之后进行此测试。根据您的数据集，Delaunay 图有可能非常接近最优值。

推荐阅读