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

摘要：

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

关键词：最短路径、多权值图、双向搜索、长路径

所属期刊栏目：41

分类号：TP301.6(计算技术、计算机技术)

资助基金：广东省自然科学基金S2012040011123;中山市科技项目20114A219;电子科技大学中山学院博士启动项目409YKQ04

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

页数：共5页

页码：242-245,289