%0 Journal Article
%T 采用双向搜索在多权值路网中查找较优长路径
%A 马慧？
%A 李建国？
%A 梁瑞仕？
%J 计算机科学
%D 2014
%R 10.11896/j.issn.1002-137X.2014.07.050
%X 求解最短路径是图研究中的一个经典问题。目前大多数相关研究都假设图中每条边只有一种权值。然而在实际应用中,有时候图中的边设有多种权值,求解最短路时需要综合计算多种权值,并采用用户自定义的聚合函数f将路径的多种权值映射到一个实数上,用以比较路径的长短。当f不是线性函数时,最短路的子路不一定也是最短路,于是大部分求解最短路的算法对此问题并不适用。文中提出了一种双向搜索方法,用以在多权值路网中求解最短路近似解。实验表明,本方法适用于长路径查询。与单向搜索相比,该方法有较高的运行效率。与基于dijkstra算法的贪心算法相比,该方法有较高的准确率。
%K 最短路径
%K 多权值图
%K 双向搜索
%K 长路径中图法分类号tp301.6文献标识码a
%U http://www.jsjkx.com/jsjkx/ch/reader/view_abstract.aspx?file_no=20140750&flag=1