位于道路网中某个顶点的用户想要到达某个地方。事实上用户的确切目的地可能与计划路径关系不大，因为确切的目的地并不会影响我们的初始方向。我们到达目的地有很多的条路径，其实绝大部分路径是重合的。许多目的地对于用户来说是等效的。我们提出了一种自动找到这些等价目的地的方法，并通过所得到的这些集群来简化路网。我们将这个问题模型化为有根，边缘加权的树中的聚类问题。我们计算出的聚类网络提供了一个常数等价度因子。通过我们这种方法可以简化节点和边，使得我们寻找最短路径的时候能够不被整个地图所干扰，能够高效的找出最短路径[1]。
预备知识
图1：基于最短路径由图得到生成树： A. 路网G，用户的位置在s点; B. 计算s点到其他点的最短路径，得到一棵生成树
问题定义
定义1: 对于一棵根为s的树T =(V,E)，对于任意的节点u和v我们计算它们之间的相似度∂(u,v) = w(Psx)/w(Psu). 其中x是u和v共同的最近父节点。我们可以理解为它们公共的路径部分越多，那么它们之间的相似度越大。（a和b是图中的节点。Pab指的是从a点b点的最短路径长度）
定义2: 对于节点u和v，如果∂(u,v)≥α并且∂(v,u)≥α，我们称他们α相似。我们将他们记为u⊕v。
定义3: 对于图G=(V,E)，如果对于任意的两个节点u和v都有u⊕v，我们称该图为相似图。
图3：分别对定理1和定理3进行解释
- 详细连接：对于节点c和它的父节点p，我们使用最短路径连接这两个节点。这种连接方法能够保存原有的拓扑结构不变，但是会产生很多内部分支。
- 直接连接：对于节点c和它的父节点p，我们直接连接他们。这种连接方法很简单直接，但是失去了原有的拓扑结构。
- 简化连接：对于详细连接，使用简化算法[2]去除节点度大于2的边。
图6：三种连接方法的结果
以下是实验结果
图7：(a)表示原始输入的地图，红色点代表起始点；(b)详细连接；(c)简化的连接。在(b)(c)中，相似度值α大于0.8.
图7：(a)输入地图；(b)使用参数0.5的详细连接
这篇文章提出了一个对于树节点的聚类方法，该算法能在线性的时间内完成。 还提出了详细连接，直接连接和简化连接这三种连接方法。这种方法可以帮组我们简化图中的节点和边，在我们查询最短路径的时候能够避免很多不重要的节点和边，可以帮组我们高效快速的找到最短路径。
参考文献：
[1] van Dijk T C, Haunert J H, Oehrlein J. Location‐dependent generalization of road networks based on equivalent destinations[C], Computer Graphics Forum. 2016, 35(3): 451-460.
[2] Dyken C, Dæhlen M, Sevaldrud T. Simultaneous curve simplification[J]. Journal of geographical systems, 2009, 11(3): 273-289.
评论关闭。