带多约束条件的最优路径选择算法研究

摘要：

传统的启发式算法把NP完全问题转化成一个能够在多项式时间内求解的P问题,却不能保证每次都得到最优路径.利用拉格朗日松弛法把该问题转换成一个P问题,利用次梯度算法来确定最优解,在降低算法时间复杂度的同时提高最优路径查找的成功率.通过实验和分析,该算法的有效性得到了验证,可以应用在地理信息系统和通信网络中.

关键词：拉格朗日松弛、多权值图、最优路径、多约束条件

所属期刊栏目：28

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

资助基金：国家863计划视频GIS关键技术研究项目2007AA12Z238

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

页数：共4页

页码：1101-1103,1110