删除几乎平行的 NetworkX 最短路径
Remove almost parallels NetworkX shortest path
我在位置 A 和 B 之间生成了一条路径，其中限制了我必须通过或靠近它们的位置，所以路线看起来像：A -> c1 -> c2 - > B，即使它不是最短的路径。
我用了for path in nx.all_shortest_paths(UG, source=l1_node_id, target=l2_node_id,weight = 'wgt'):
当'wgt'是这条路上edge/driving速度的距离。
我生成了一个列表列表，其中每个内部列表都是 node_id 例如：
l_list = [
[n11,n12,n13,n14....]
[n21,n22,n23,n24....]
..
]
在地图上，它看起来像：（标记是每条路线的起点，我还用不同的颜色给它们涂上了颜色）
我想把它改成一条路线，但正如你所看到的，有一些分裂，比如绿色和红色，一些常见的序列（我可以处理），第二个问题是蓝色的开始 route\end 的黑色的是不重要的。
我不能只删除红色路线，因为它应该是一个通用算法，我什至不知道它会在这条路线中再次发生在哪里。
我确实有每个标记的时间戳，但它只是说我已经接近这个区域。 （这是蜂窝天线的位置）
首先，您需要更简洁地定义什么是"almost parallel"，或者更正式地，您需要定义一个相似度函数。
选择 similarity/distance 函数
有很多方法可以定义相似度函数，这里是其中之一
重新取样
假设每个节点 n_i 有一个 x 和 y 坐标 (n_i_x,n_i_y)。
您可以对 x 轴上的点重新采样，以便在 1km.
处对新点进行采样
然后，对于每 2 条路线，您可以在 y 轴上求和差值。
使用此距离对路线进行聚类。
其他想法
- Earth mover distance
- Jaccard（~ 常见节点的百分比）
聚类
一旦你定义了一个similarity函数，你就可以使用基于距离的聚类算法，我推荐使用sklearn's agglomerative clustering。
聚类完成后，您剩下要做的就是从每个聚类中选择一条路线。
我在位置 A 和 B 之间生成了一条路径，其中限制了我必须通过或靠近它们的位置，所以路线看起来像：A -> c1 -> c2 - > B，即使它不是最短的路径。
我用了for path in nx.all_shortest_paths(UG, source=l1_node_id, target=l2_node_id,weight = 'wgt'):
当'wgt'是这条路上edge/driving速度的距离。
我生成了一个列表列表，其中每个内部列表都是 node_id 例如：
l_list = [
[n11,n12,n13,n14....]
[n21,n22,n23,n24....]
..
]
在地图上，它看起来像：（标记是每条路线的起点，我还用不同的颜色给它们涂上了颜色）
我想把它改成一条路线，但正如你所看到的，有一些分裂，比如绿色和红色，一些常见的序列（我可以处理），第二个问题是蓝色的开始 route\end 的黑色的是不重要的。
我不能只删除红色路线，因为它应该是一个通用算法，我什至不知道它会在这条路线中再次发生在哪里。
我确实有每个标记的时间戳，但它只是说我已经接近这个区域。 （这是蜂窝天线的位置）
首先，您需要更简洁地定义什么是"almost parallel"，或者更正式地，您需要定义一个相似度函数。
选择 similarity/distance 函数
有很多方法可以定义相似度函数，这里是其中之一
重新取样
假设每个节点 n_i 有一个 x 和 y 坐标 (n_i_x,n_i_y)。
您可以对 x 轴上的点重新采样，以便在 1km.
然后，对于每 2 条路线，您可以在 y 轴上求和差值。
使用此距离对路线进行聚类。
其他想法
- Earth mover distance
- Jaccard（~ 常见节点的百分比）
聚类
一旦你定义了一个similarity函数，你就可以使用基于距离的聚类算法，我推荐使用sklearn's agglomerative clustering。
聚类完成后，您剩下要做的就是从每个聚类中选择一条路线。