论文阅读 - Discovering Popular Routes from Trajectories - 路径规划 - 论文阅读 - 计算机科学

# Discovering Popular Routes from Trajectories

与先前工作区别：先前工作专注于局部的物体的运动模式，有助于帮助司机决定是否在某个路口转向，但是并没有解决给定终点发现一条热门路径的问题。比如说 $A-C-D$ 被发现是经常访问的路段，但是人们从 $A-C-D$ 出发却不一定会到达我们想要的 $B$ ，可能从 $A-C-E-F$ 走的可能性更大，所以只去统计每个路段上经过的轨迹数量并不能获得我们想要的结果

本文思想：利用原始的轨迹数据生成转移网络，来表示位置之间的移动行为，最后利用转移网络来找到热门路径。转移网络中的每个节点（也就是每个路口）被看作是转移节点，利用历史轨迹数据获得每个转移节点到其余节点到转移概率，热门路径的热门度就被定义为这条路径上所有转移节点的转移概率的乘积。

具体步骤：对于转移边，其定义为，对于任意的两个转移节点，如果有轨迹经过并且两个转移节点之间没有其他的转移节点经过

1、通过共现拓展算法挖掘出转移网络（我们这里并没有采用它的方法，使用了路网数据）

2、通过吸收马尔可夫链获得每个转移节点的转移概率

这里一个节点到下一个节点到转移概率不是两个节点之间的轨迹数除以 $n_i$ 所有的出边上经过的轨迹数，这里考虑了终点的影响，改进成了两个节点之间的经过终点 d 的轨迹函数除以 $n_i$ 的所有出边上经过终点 d 的轨迹函数，这样距离终点越近的转移结点的转移概率就会越高。

此时我们在转移网络上进行随机游走，假设在 t 步时，我们从起点到达了终点，那么从起点到终点的概率被定义为

相应的在 t 步内，从起点到终点的转移概率为

构造转移矩阵 $P$

假定这里有 x 个吸收态，y 个传递态，这时矩阵 P 可以被重新构造成如下形式

依据转移概率，我们就得到了从起点到终点的转移概率

这里假定 $n_1, n_2, ..., n_l$ 是转移态，构造转移矩阵

最后得到提取转移概率的伪码

计算上述伪码的时间复杂度

derive V 的时间复杂度 $O(t \times N^3)$
等式 5 的时间复杂度：首先遍历邻接矩阵 N*N，之后计算 prd，首先计算所有经过选中节点的轨迹，计算终点离这些选定轨迹的最短距离之和，假定经过的轨迹数目为 K，轨迹上的点为 L，那么最短距离之和为 KL，最后总的时间复杂度为 $O(N(t \times N^3 + LKN^2))$