1.一种路径推荐方法,其特征在于,包括:
依据获取的历史轨迹数据,构建在目的地点确定的情况下所对应的有向图;所述有向图中包含的任意两个相邻节点之间所对应的线段有其对应的转向概率值;
依据最大概率寻路算法,从所述有向图中选取出从起始节点达到所述目的地点概率值最大的一条路径作为推荐路径。
2.根据权利要求1所述的方法,其特征在于,所述依据获取的历史轨迹数据,构建在目的地点确定的情况下所对应的有向图包括:依据获取的历史轨迹数据,建立在目的地点确定的情况下所对应的路网图;所述路网图由各个节点连接组成,一个节点对应表示一个路口;
根据如下公式,计算出所述路网图中任意两个相邻节点之间的转向概率值,从而将所述路网图转化为有向图;
其中,ni表示所述路网图中的一个节点,nj表示与所述ni相邻的一个节点,Prd(ni→nj)表示从节点ni转向节点nj的转向概率值,func(traj,d)=exp(-dists(traj,d))用来度量一条轨迹traj到达目的地点d的概率值,dists(traj,d)表示所述轨迹traj通过节点ni后的轨迹部分到目的地点d的最短距离。
3.根据权利要求2所述的方法,其特征在于,所述依据最大概率寻路算法,从所述有向图中选取出从起始节点达到所述目的地点概率值最大的一条路径作为推荐路径包括:S20:依据选定的初始节点,从所述有向图中选取出与所述初始节点相邻的目标节点,并将所述起始节点与各个所述目标节点之间的路径作为子路径存储于集合A中;
S21:从所述集合A中包含的所有所述子路径中选取出概率值最大的一条子路径作为目标子路径,并判断所述目标子路径中的目标节点是否为目的地点;若是,则执行S22;若否,则执行S23;
S22:将所述目标子路径作为推荐路径;
S23:将所述目标子路径包含的目标节点作为第一节点;
S24:从所述有向图中选取出与所述第一节点相邻并且满足限定条件的目标节点;并将从所述起始节点开始经过所述第一节点达到所述目标节点的子路径替换从所述起始节点达到所述第一节点子路径,存储于集合A中,并返回所述S21。
4.根据权利要求3所述的方法,其特征在于,在所述S21中包括:
将第一子路径中包含的各条线段的转向概率值相乘,得出所述第一子路径的概率值;
所述第一子路径为所述集合A中包含的所有所述子路径中的任意一条子路径。
5.根据权利要求1-4任意一项所述的方法,其特征在于,还包括:
依据Top-k算法,从所述有向图中选取出与所述推荐路径满足差异条件的k条备选路径。
6.一种路径推荐装置,其特征在于,包括构建单元和选取单元,
所述构建单元,用于依据获取的历史轨迹数据,构建在目的地点确定的情况下所对应的有向图;所述有向图中包含的任意两个相邻节点之间所对应的线段有其对应的转向概率值;
所述选取单元,用于依据最大概率寻路算法,从所述有向图中选取出从起始节点达到所述目的地点概率值最大的一条路径作为推荐路径。
7.根据权利要求6所述的装置,其特征在于,所述构建单元包括建立子单元和转化子单元,所述建立子单元,用于依据获取的历史轨迹数据,建立在目的地点确定的情况下所对应的路网图;所述路网图由各个节点连接组成,一个节点对应表示一个路口;
所述转化子单元,用于根据如下公式,计算出所述路网图中任意两个相邻节点之间的转向概率值,从而将所述路网图转化为有向图;
其中,ni表示所述路网图中的一个节点,nj表示与所述ni相邻的一个节点,Prd(ni→nj)表示从节点ni转向节点nj的转向概率值,func(traj,d)=exp(-dists(traj,d))用来度量一条轨迹traj到达目的地点d的概率值,dists(traj,d)表示所述轨迹traj通过节点ni后的轨迹部分到目的地点d的最短距离。
8.根据权利要求7所述的装置,其特征在于,所述选取单元包括第一选取子单元、第二选取子单元、判断子单元、第一作为子单元、第二作为子单元和替换子单元,所述第一选取子单元,用于依据选定的初始节点,从所述有向图中选取出与所述初始节点相邻的目标节点,并将所述起始节点与各个所述目标节点之间的路径作为子路径存储于集合A中;
所述第二选取子单元,用于从所述集合A中包含的所有所述子路径中选取出概率值最大的一条子路径作为目标子路径,并触发所述判断子单元,所述判断子单元,用于判断所述目标子路径中的目标节点是否为目的地点;若是,则触发所述第一作为子单元;若否,则触发所述第二作为子单元;
所述第一作为子单元,用于将所述目标子路径作为推荐路径;
所述第二作为子单元,用于将所述目标子路径包含的目标节点作为第一节点;并触发所述替换子单元;
所述替换子单元,用于从所述有向图中选取出与所述第一节点相邻并且满足限定条件的目标节点;并将从所述起始节点开始经过所述第一节点达到所述目标节点的子路径替换从所述起始节点达到所述第一节点子路径,存储于集合A中,并触发所述第二选取子单元。
9.根据权利要求8所述的装置,其特征在于,所述第二选取子单元具体用于将第一子路径中包含的各条线段的转向概率值相乘,得出所述第一子路径的概率值;所述第一子路径为所述集合A中包含的所有所述子路径中的任意一条子路径。
10.根据权利要求6-9任意一项所述的装置,其特征在于,还包括备选单元,所述备选单元,用于依据Top-k算法,从所述有向图中选取出与所述推荐路径满足差异条件的k条备选路径。