声明
严正声明：本站非期刊官网，非中介代理。
本站仅提供学术规范服务：快速预审、润色编辑服务、中英文查重、降重、去重服务、推荐合适的期刊投稿等学术规范服务。 如需提供学术规范服务请联系在线编辑。
国内刊号：11-2560/TP
国际刊号：1000-9825
发布日期:
作者：郝晋瑶，牛保宁，康家兴
单位：郝晋瑶，太原理工大学 信息与计算机学院, 山西 晋中 03060011,牛保宁，太原理工大学 信息与计算机学院, 山西 晋中 03060002,康家兴，太原理工大学 信息与计算机学院, 山西 晋中 03060003
关键词：个性化旅游路线;关键词覆盖最优路径;大规模路网图;路网图划分;最小代价剪枝
基金：国家自然科学基金（61572345）
游客倾向于采用个性化的旅游路线，规划这样的路线需要综合考量路径长度、路径开销和路径覆盖的兴趣点.关键词覆盖最优路径查询（KOR）就是用于规划这样的路线的一类查询，其处理过程通常包括预处理和路径拓展.由于路网图规模的不断扩大，现有算法预处理所需内存开销急剧上升，由于内存不足，导致较大规模的路网不能处理；路径拓展搜索空间快速膨胀，应用场景可扩展性与查询实时性难以保证.针对这些问题，提出一种大规模路网图下关键词覆盖最优路径查询算法KORL.KORL在预处理阶段将路网划分为若干子图，仅保存子图内路径和子图之间路径的信息，以减小预处理所需内存.在路径拓展阶段，综合运用最小代价剪枝、近似支配剪枝、全局优先拓展和关键词顶点拓展等策略对现有算法进行优化，以高效地搜索近似最优解.采用美国各地区的路网图，在16G内存环境下进行实验，突破了现有算法只能处理顶点数不超过25K路网图的限制.实验结果表明，KORL算法具有良好的可扩展性.
来源：2020年第8期
《软件学报》期刊编辑部
严正声明：本站非期刊官网，非中介代理。
本站仅提供学术规范服务：快速预审、润色编辑服务、中英文查重、降重、去重服务、推荐合适的期刊投稿等学术规范服务。 如需提供学术规范服务请联系在线编辑。