基于时序图的多约束路径查询
发布时间：2021-09-04 16:17
近年来,随着大数据时代的到来以及在线社交网络的兴起,图上的算法研究越来越受到人们的重视,因为无论是社交网络还是交通道路网都可以被抽象为一张图。迄今为止,许多优秀的图算法已经被运用到实际应用中,并且给人们的生活带来了极大的便利。但是现有的图算法大都基于静态图并且只考虑单个属性,而忽略了实际生活中的时序性以及多属性特征。比如在路网中,不同时刻下两点间是否存在汽车班次;又比如出行时,除了考虑时间因素,人们往往还会考虑道路拥挤程度,汽车油耗等多个属性因素。综合以上情况,本文研究了基于时序图的多约束路径查询问题,在传统的路径查询算法基础上进行扩展和创新,将时序信息和多属性信息嵌入到对图的建模和处理当中,更加真实地模拟了实际情况,也为用户提供了更加准确和细致的结果。本文致力于在时序图上找到满足用户提出的多个属性上的约束的目标路径,这里的目标路径包括最快到达路径以及运行时间最短路径。为了有效并且高效地解决上述问题,本文分别提出了基于Skyline路径的算法以及基于双向搜索的算法。它们充分考虑了图上的时序特征和多属性特征,并在查询的过程中不断剪枝和优化,极大地减少了搜索空间。基于Skyline路径的算...
【文章来源】：苏州大学江苏省 211工程院校
【文章页数】：65 页
【学位级别】：硕士
【部分图文】：
图３－１时序图转静态图实例??，，
Ｓ?爸?ＳＫＹ－Ｓ?，＊??｜?★?ＴＰ－Ｓ?Ｉ?３０?★?ＴＰ－Ｓ?／?ｖ??Ｉ０６?＇?Ｍ?■￣￣＾￣￣＊—一一Ｉ＇?｜?Ｘ??〇＞?〇）?２０?／?■??ｉ°４ｆ?ｉ?／??，丨ｒ??〇▼：?▼?▼?Ｔ?ＩＴ?〇（Ｗ?￣?￣?ｆ?－７：?－?－?■玄??Ｔ１?Ｔ２?Ｔ３?Ｔ４?Ｔ５?Ｔ１?Ｔ２?Ｔ３?Ｔ４?Ｔ５??Ｔｉｍｅ?ｉｎｔｅｒｖａｌ?（Ｏｐｓａｈｌ）?Ｔｉｍｅ?ｉｎｔｅｒｖａｌ?（Ｔａｓｍａｎｉａ）??图５－１时间区间对查询效率的影响??【Ｃ的影响】该组实验研宂的是属性约束值对算法效率的影响。如图５－２所示，??横坐标表示的是约束值的大小，纵坐标表示的是平均响应时间。首先，随着约束值??变大，所有算法的查询时间都变大了，这是因为约束值放宽，有更多的路径满足约?＇??束条件，增大了搜索空间，所以所有算法的响应时间都增加了。其次，本文提出的??两种算法在时间效率上都要明显优于基线算法，因为基于Ｓｋｙｌｉｎｅ路径的算法将时序??图转成了静态图，并且通过设计启发函数值和剪枝策略来加速查询，而基于双向搜??索的方法通过正反向搜索以及相关支配剪枝策略也达到了加速查询的效果。最后，??对比本文提出的两种算法，基于Ｓｋｙｌｉｎｅ路径算法的平均查询效率要优于基于双向搜??索的，原因跟上组实验分析的类似。??３２??
?？?３０?＇?ｘ?ｉ：??§，０２?？?＾?Ｓ．?ｉｒ＾?ｘ??！?ｆ，?！２。??０１＾?’???▼?Ｖ?Ｕ，卜—看?？?？?°??１?ｆ－??－?＊?Ｈｔ－?????■?１?……二琴?羃?■一一…■…＾??６０?１２０?１８０?２４０?３００?６０?１２０?１８０?２４０?３００??Ｖａｌｕｅｓ?ｏｆ?ｃｏｎｓｔｒａｉｎｔｓ?（Ｏｐｓａｈｌ）?Ｖａｌｕｅｓ?ｏｆ?ｃｏｎｓｔｒａｉｎｔｓ?（Ｔａｓｍａｎｉａ）??图５－２约束值对查询效率的影响??【Ｘ的影响】该组实验研宄的是约束个数对算法效率的影响。如图５－３所示，横??坐标表示的是约束的个数，纵坐标表示的是平均响应时间。首先，随着约束个数的??增大，所有算法的查询时间都变大了，原因分别为：对于基线方法来说，它需要分??别处理尺个约束，所以约束个数越多，花费时间越长；对于基于Ｓｋｙｌｉｎｅ路径的算法，??约束个数越多，它涉及的目标方程值就越复杂，其次，两种支配策略处理起来需要??判断的情况也越多，所以时间消耗变大；对于基于双向搜索的算法，约束个数越多，??它处理的属性聚合函数就越复杂，同时，在正反向过程中剪枝的处理就变得较为复??杂，所以平均响应时间也会增加。综合以上分析，这种现象是符合预期的。其次，??本文提出的两种算法在时间效率上都要明显优于基线算法，原因类似于上面两组实??验。最后，本文提出的两种算法相比，基于Ｓｋｙｌｉｎｅ路径算法的平均查询效率也要略??优于基于双向搜索的，原因也跟上面两组实验分析相似。??３３??
【参考文献】：
期刊论文
[1]关于最短路径的SPFA快速算法[J]. 段凡丁. 西南交通大学学报. 1994(02)
本文编号：3383592
【文章来源】：苏州大学江苏省 211工程院校
【文章页数】：65 页
【学位级别】：硕士
【部分图文】：
图３－１时序图转静态图实例??，，
Ｓ?爸?ＳＫＹ－Ｓ?，＊??｜?★?ＴＰ－Ｓ?Ｉ?３０?★?ＴＰ－Ｓ?／?ｖ??Ｉ０６?＇?Ｍ?■￣￣＾￣￣＊—一一Ｉ＇?｜?Ｘ??〇＞?〇）?２０?／?■??ｉ°４ｆ?ｉ?／??，丨ｒ??〇▼：?▼?▼?Ｔ?ＩＴ?〇（Ｗ?￣?￣?ｆ?－７：?－?－?■玄??Ｔ１?Ｔ２?Ｔ３?Ｔ４?Ｔ５?Ｔ１?Ｔ２?Ｔ３?Ｔ４?Ｔ５??Ｔｉｍｅ?ｉｎｔｅｒｖａｌ?（Ｏｐｓａｈｌ）?Ｔｉｍｅ?ｉｎｔｅｒｖａｌ?（Ｔａｓｍａｎｉａ）??图５－１时间区间对查询效率的影响??【Ｃ的影响】该组实验研宂的是属性约束值对算法效率的影响。如图５－２所示，??横坐标表示的是约束值的大小，纵坐标表示的是平均响应时间。首先，随着约束值??变大，所有算法的查询时间都变大了，这是因为约束值放宽，有更多的路径满足约?＇??束条件，增大了搜索空间，所以所有算法的响应时间都增加了。其次，本文提出的??两种算法在时间效率上都要明显优于基线算法，因为基于Ｓｋｙｌｉｎｅ路径的算法将时序??图转成了静态图，并且通过设计启发函数值和剪枝策略来加速查询，而基于双向搜??索的方法通过正反向搜索以及相关支配剪枝策略也达到了加速查询的效果。最后，??对比本文提出的两种算法，基于Ｓｋｙｌｉｎｅ路径算法的平均查询效率要优于基于双向搜??索的，原因跟上组实验分析的类似。??３２??
?？?３０?＇?ｘ?ｉ：??§，０２?？?＾?Ｓ．?ｉｒ＾?ｘ??！?ｆ，?！２。??０１＾?’???▼?Ｖ?Ｕ，卜—看?？?？?°??１?ｆ－??－?＊?Ｈｔ－?????■?１?……二琴?羃?■一一…■…＾??６０?１２０?１８０?２４０?３００?６０?１２０?１８０?２４０?３００??Ｖａｌｕｅｓ?ｏｆ?ｃｏｎｓｔｒａｉｎｔｓ?（Ｏｐｓａｈｌ）?Ｖａｌｕｅｓ?ｏｆ?ｃｏｎｓｔｒａｉｎｔｓ?（Ｔａｓｍａｎｉａ）??图５－２约束值对查询效率的影响??【Ｘ的影响】该组实验研宄的是约束个数对算法效率的影响。如图５－３所示，横??坐标表示的是约束的个数，纵坐标表示的是平均响应时间。首先，随着约束个数的??增大，所有算法的查询时间都变大了，原因分别为：对于基线方法来说，它需要分??别处理尺个约束，所以约束个数越多，花费时间越长；对于基于Ｓｋｙｌｉｎｅ路径的算法，??约束个数越多，它涉及的目标方程值就越复杂，其次，两种支配策略处理起来需要??判断的情况也越多，所以时间消耗变大；对于基于双向搜索的算法，约束个数越多，??它处理的属性聚合函数就越复杂，同时，在正反向过程中剪枝的处理就变得较为复??杂，所以平均响应时间也会增加。综合以上分析，这种现象是符合预期的。其次，??本文提出的两种算法在时间效率上都要明显优于基线算法，原因类似于上面两组实??验。最后，本文提出的两种算法相比，基于Ｓｋｙｌｉｎｅ路径算法的平均查询效率也要略??优于基于双向搜索的，原因也跟上面两组实验分析相似。??３３??
【参考文献】：
期刊论文
[1]关于最短路径的SPFA快速算法[J]. 段凡丁. 西南交通大学学报. 1994(02)
本文编号：3383592
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3383592.html
