采用双向搜索在多权值路网中查找较优长路径

• 作者: 李建国 梁瑞仕 马慧
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 最短路径 多权值图 双向搜索 长路径
• 年，卷（期）: 2014,（7）
• 所属期刊栏目: 软件与数据库技术
• 页码范围: 242-245,289
• 页数: 5页
• 分类号: TP301.6
• 字数: 6191字
• 语种: 中文
• DOI: 10.11896/j.issn.1002-137X.2014.07.050

摘要

求解最短路径是图研究中的一个经典问题.目前大多数相关研究都假设图中每条边只有一种权值.然而在实际应用中,有时候图中的边设有多种权值,求解最短路时需要综合计算多种权值,并采用用户自定义的聚合函数f将路径的多种权值映射到一个实数上,用以比较路径的长短.当f不是线性函数时,最短路的子路不一定也是最短路,于是大部分求解最短路的算法对此问题并不适用.文中提出了一种双向搜索方法,用以在多权值路网中求解最短路近似解.实验表明,本方法适用于长路径查询.与单向搜索相比,该方法有较高的运行效率.与基于Dijkstra算法的贪心算法相比,该方法有较高的准确率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	马慧	电子科技大学中山学院计算机学院	14	32	4.0	5.0
2	李建国	华南师范大学计算机学院	9	156	5.0	9.0
3	梁瑞仕	电子科技大学中山学院计算机学院	20	80	4.0	8.0