典型文献
关键词最优路径查询的分段拓展算法
文献摘要：
关键词最优路径查询(KOR)查找在满足关键词全覆盖和路径长度约束条件下,时间开销最小的路线常用于旅行规划.现有优化算法虽然采用各种剪枝策略缩小搜索规模,但是本质上是广度优先搜索,在查找长路径时,搜索规模依然过大,执行时间长.针对该问题,提出一种关键词最优路径查询的分段拓展算法(SE-KOR).SE-KOR算法根据关键词倒排索引表构建关键词顶点路径,将路径划分为多段分别拓展,降低搜索规模,从而缩短执行时间.该算法在路径拓展时给出路径走向,而现有剪枝策略不控制路径拓展方向,因此提出局部代价阈值剪枝,控制路径的走向沿关键词顶点路径拓展,并综合运用近似支配、可行解目标值剪枝和全局优先拓展策略加速拓展.实验结果表明,在不损失精度的情况下,该算法执行时间分别在不同关键词个数、代价阈值与查询图规模下至少缩短8.0％、61.0％和57.7％.
文献关键词：
多约束;关键词最优路径查询;长路径搜索;分段拓展;局部代价阈值剪枝
中图分类号：
作者姓名：
刘蒙蒙;牛保宁;杨茸
作者机构：
太原理工大学 信息与计算机学院,山西 晋中 030600
文献出处：
引用格式：
[1]刘蒙蒙;牛保宁;杨茸-.关键词最优路径查询的分段拓展算法)[J].计算机工程,2022(06):79-88
A类：
关键词最优路径查询,分段拓展,局部代价阈值剪枝,长路径搜索
B类：
KOR,路径长,开销,广度优先搜索,执行时间,SE,倒排索引,索引表,顶点,多段,路径拓展,控制路径,出局,目标值,拓展策略,略加,失精,算法执行,查询图,下至,多约束
AB值：
0.232948
相似文献
机标中图分类号，由域田数据科技根据网络公开资料自动分析生成，仅供学习研究参考。
