计算机工程

作者：刘蒙蒙, 牛保宁, 杨茸

单位：太原理工大学 信息与计算机学院, 山西 晋中 030600

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

基金：国家自然科学基金面上项目（62072326）；山西省重点研发计划（国际科技合作）（201903D421007）。

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

来源：2022年第6期

《计算机工程》期刊编辑部

查看计算机工程杂志2022年第6期