公开(公告)号：CN109213903A

公开(公告)日：2019-01-15

申请号：CN201810721123.2

申请日：2018-07-04

Applicant: 苏州大学

Inventor： 时久超 ,  赵安琪 ,  刘冠峰

IPC: G06F16/903

Abstract: 本发明公开了一种时序图下多约束路径查询方法，包括以下具体步骤：通过定义一个目标方程，对一条路径的多属性进行聚合，然后根据用户给定的起点和终点，约束值以及时间区间，从终点向起点进行反向搜索，计算出起点到终点的路径以及中间节点到终点的路径的最小目标方程值和最晚时刻下的目标方程值，然后从起点开始正向扩展路径，以最早、最晚、最快和最“短”分别为目标向后扩展，在扩展过程中结合反向求得的两个目标方程值进行剪枝来加快查询速度。通过上述方式，本发明的时序图下多约束路径查询方法，提出正反向结合的方法来综合考虑约束值以及目标值，从而求出符合用户需求的最佳路径，能够高效且有效地查询路径。

公开(公告)号：CN109086302A

公开(公告)日：2018-12-25

申请号：CN201810642766.8

申请日：2018-06-21

Applicant: 苏州大学

Inventor： 时久超 ,  赵安琪 ,  刘冠峰

IPC: G06F17/30

Abstract: 本发明公开了一种时序图下基于Skyline的多约束路径查询方法，包括以下具体步骤：通过充分分析时序图的特点，设计新的数据结构，将时序图转成“静态图”，在此基础上，求解两点间满足多个约束条件的Skyline路径，最后根据求得的Skyline路径计算多种不同类型的路径，其中，在求解Skyline路径时，利用A*算法设计启发函数并通过两个剪枝策略来加速计算，最后在求解多种不同类型的路径时，利用时序图设计类似二分搜索的算法来加速对结果的查询。通过上述方式，本发明考虑了路径上的多个约束条件，解决了在时序图下完成多约束路径查询的问题，极大地减少了查询时间，优化了算法，提高了查询的准确率。