GPS导航算法
GPS Navigation Algorithm
我有数千个来自车辆的输入 GPS 值，我想将其映射到道路图上节点给出的特定值。拍摄下图。每个节点 (A-F) 都有关于连接到它的前一条边的信息（以及 latitude/longitude）。我想将其中一些信息与我输入的 GPS 坐标中的每个 GPS 点相匹配。
路线图
到目前为止我可以这样做，但也有一些边缘情况。以图像为例，当我们到达节点 B 时，我们认为我们可能在路径 BCD 或路径 BEF 上。直到节点之间的距离足够远，我们才知道输入采用了哪条路线。这是因为道路不仅仅是一条二维线。它们有宽度，车辆可能在路边。很难确定它在哪条路上，因为我们不知道道路的宽度。因此，当我们到达节点 B 时，车辆可能位于 BC 或 BE 之间。直到后来沿着每条路径我们才知道我们在哪里。
也就是说，我们可以遍历每条路线，直到我们只有一个选择，因此我们知道我们在这条路上。我们可以在正确的路线上回填之前所有节点的数据。但是，我在为此算法提出问题时遇到了问题。
我如何在代码中处理这个问题？我考虑过在每个交叉路口进行 DFS，并找出哪条路径的边数最多，其中包含来自车辆的输入点。有没有更好的方法？
我会首先将 gps 输入映射到节点，但在映射操作期间，每个节点都应将 count++ 传播到父节点（如果可能存在循环，则检测循环）。您最多只能传播到 (但没有）交点。比你可以沿着这条路走，在十字路口取最大的价值，然后走那条路。
你最终会得到类似（例如）的结果：
0 -> 0 -> 4 -> 3 -> 1
|
---> 2 -> 1 -> 0
在第二个节点中，您将选择 'upper' 方向。重要的是你只传播到 parent->numberOfNeighbours > 1 的位置，因为你总是必须到达十字路口，所以不需要进一步传播。
如果我对问题的理解是正确的，那么一旦你到达节点 B，你就会对前方的道路产生一些不确定性。然而，在到达节点 C 或 E 后，前进的路径现在是已知的，直到下一个出度大于 1 的节点。
然后，我认为您只需跟踪您的路径直到一个十字路口并列出与该十字路口相邻的所有节点（类似于 BFS）。检查此可能节点列表，一旦到达一个节点，将其添加到当前路径。此时你会知道你所在的道路，并且可以预测前进的路径直到下一个十字路口，重复直到你的目的地。
我有数千个来自车辆的输入 GPS 值，我想将其映射到道路图上节点给出的特定值。拍摄下图。每个节点 (A-F) 都有关于连接到它的前一条边的信息（以及 latitude/longitude）。我想将其中一些信息与我输入的 GPS 坐标中的每个 GPS 点相匹配。
路线图
到目前为止我可以这样做，但也有一些边缘情况。以图像为例，当我们到达节点 B 时，我们认为我们可能在路径 BCD 或路径 BEF 上。直到节点之间的距离足够远，我们才知道输入采用了哪条路线。这是因为道路不仅仅是一条二维线。它们有宽度，车辆可能在路边。很难确定它在哪条路上，因为我们不知道道路的宽度。因此，当我们到达节点 B 时，车辆可能位于 BC 或 BE 之间。直到后来沿着每条路径我们才知道我们在哪里。
也就是说，我们可以遍历每条路线，直到我们只有一个选择，因此我们知道我们在这条路上。我们可以在正确的路线上回填之前所有节点的数据。但是，我在为此算法提出问题时遇到了问题。
我如何在代码中处理这个问题？我考虑过在每个交叉路口进行 DFS，并找出哪条路径的边数最多，其中包含来自车辆的输入点。有没有更好的方法？
我会首先将 gps 输入映射到节点，但在映射操作期间，每个节点都应将 count++ 传播到父节点（如果可能存在循环，则检测循环）。您最多只能传播到 (但没有）交点。比你可以沿着这条路走，在十字路口取最大的价值，然后走那条路。
你最终会得到类似（例如）的结果：
0 -> 0 -> 4 -> 3 -> 1
|
---> 2 -> 1 -> 0
在第二个节点中，您将选择 'upper' 方向。重要的是你只传播到 parent->numberOfNeighbours > 1 的位置，因为你总是必须到达十字路口，所以不需要进一步传播。
如果我对问题的理解是正确的，那么一旦你到达节点 B，你就会对前方的道路产生一些不确定性。然而，在到达节点 C 或 E 后，前进的路径现在是已知的，直到下一个出度大于 1 的节点。
然后，我认为您只需跟踪您的路径直到一个十字路口并列出与该十字路口相邻的所有节点（类似于 BFS）。检查此可能节点列表，一旦到达一个节点，将其添加到当前路径。此时你会知道你所在的道路，并且可以预测前进的路径直到下一个十字路口，重复直到你的目的地。