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

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