关键词最优路径查询的分段拓展算法

摘要：

关键词最优路径查询(KOR)查找在满足关键词全覆盖和路径长度约束条件下,时间开销最小的路线常用于旅行规划.现有优化算法虽然采用各种剪枝策略缩小搜索规模,但是本质上是广度优先搜索,在查找长路径时,搜索规模依然过大,执行时间长.针对该问题,提出一种关键词最优路径查询的分段拓展算法(SE-KOR).SE-KOR算法根据关键词倒排索引表构建关键词顶点路径,将路径划分为多段分别拓展,降低搜索规模,从而缩短执行时间.该算法在路径拓展时给出路径走向,而现有剪枝策略不控制路径拓展方向,因此提出局部代价阈值剪枝,控制路径的走向沿关键词顶点路径拓展,并综合运用近似支配、可行解目标值剪枝和全局优先拓展策略加速拓展.实验结果表明,在不损失精度的情况下,该算法执行时间分别在不同关键词个数、代价阈值与查询图规模下至少缩短8.0％、61.0％和57.7％.

关键词：多约束、关键词最优路径查询、长路径搜索、分段拓展、局部代价阈值剪枝

所属期刊栏目：48

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金;山西省重点研发计划

在线出版日期：2022-06-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：79-88