点、边带约束成本的最短路问题及其算法

被引：6

作者：

齐东元

汪泽焱

邵军力

机构：

[1] 解放军理工大学通信工程学院

来源：

东南大学学报(自然科学版) | 2003年 / 01期

关键词：

最短路问题; 点、边带约束成本; 拉格朗日松弛算法; 次梯度算法;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

提出了点和边都带有成本约束的最短路问题 ,证明了该问题是NP 完全的 .建立了这类问题的数学规划模型 ,并采用拉格朗日松弛算法对模型进行求解 ,给出了次梯度优化求解算法的一般步骤 .考虑到算法在实际求解过程中收敛速度较慢的问题 ,进一步对拉格朗日松弛算法进行了2个方面的改进 ,一方面确定适当的迭代步长 ,另一方面选择较好的迭代方向 .算法实例表明 ,改进后的拉格朗日松弛算法迭代步数显著减少 ,证明算法是有效的

引用

页码：111 / 114

页数：4