软件学报

作者：李艳红，王猛，李国徽，罗昌银，杜小坤

单位：李艳红，中南民族大学 计算机科学学院, 湖北 武汉 43007411,王猛，中南民族大学 计算机科学学院, 湖北 武汉 43007402,李国徽，华中科技大学 软件学院, 湖北 武汉 43007403,罗昌银，人工智能与智慧学习湖北省重点实验室(华中师范大学), 湖北 武汉 430079;国家语言资源监测与研究网络媒体中心, 湖北 武汉 430079;华中师范大学 计算机学院, 湖北 武汉 43007904,杜小坤，中南民族大学 计算机科学学院, 湖北 武汉 43007405

关键词：动态网络;最短时间路径查询;动态阈值;预处理;树的遍历

基金：国家自然科学基金(61572215,61772562);教育部人文社科基金(20YJCZH111);湖北省自然科学基金(2017CFB135);中央高校基本科研业务费项目(CCNU20ZT013)

最佳排序路径查询,是智能交通中的热点问题.在实际的应用中,由于最佳排序路径查询有许多限制条件,现有的算法不能有效地解决动态网络中受限制的路径查询问题.为了解决动态网络中最佳排序路径查询问题,用规则表示每个限制条件,提出了一种新的最佳排序路径查询形式,即多规则的最短路径查询.提供了统一的框架,该框架包含了路径集合查询和最短路径查询.在路径集合查询部分,为了高效地查询出满足多规则的路径集合,在广义规则树的基础上,提出一种新的树的遍历方式,即树的继承全遍历;并基于树的继承全遍历思想,提出一种剪枝技术,对路径集合进行删减,最后求得候选路径集合.在最短路径查询部分,提出一种基于动态阈值的最短路径搜索方法.通过两个真实的动态道路网络的实验验证,所提出的算法能够高效地解决多规则的最短路径查询问题.

来源：2022年第8期

《软件学报》期刊编辑部

查看软件学报杂志2022年第8期