| 点、边带约束成本的最短路问题及其算法 |
| |
| 引用本文： | 齐东元,汪泽焱,邵军力.点、边带约束成本的最短路问题及其算法[J].东南大学学报(自然科学版),2003,33(1):111-114. |
| |
| 作者姓名： | 齐东元 汪泽焱 邵军力 |
| |
| 作者单位： | 解放军理工大学通信工程学院,南京,210007 |
| |
| 基金项目： | 战术通信抗干扰技术国防科技重点实验室基金资助项目 ( 0 0JS0 4 .4 .1.JB380 1) |
| |
| 摘 要： | 提出了点和边都带有成本约束的最短路问题，证明了该问题是NP－完全的，建立了这类问题的数学规划模型，并采用拉格朗日松弛算法对模型进行求解，给出了次梯度优化求解算法的一般步骤，考虑到算法在实际求解过程中收敛速度较慢的问题，进一步对拉格朗日松弛算法进行了2个方面的改进，一方面确定适当的迭代步长，另一方面选择较好的迭代方向，算法实例表明，改进后的拉格朗日松弛算法迭代步数显著较少，证明算法是有效的。
|
| 关 键 词： | 最短路问题 点 边 拉格朗日松弛算法 次梯度算法 成本约束 网络分析 |
| 文章编号： | 1001-0505(2003)01-0111-04 |
Shortest path problem with constraints of node's and edge's cost and its algorithm |
| |
| Qi Dongyuan,Wang Zeyan,Shao Junli.Shortest path problem with constraints of node''s and edge''s cost and its algorithm[J].Journal of Southeast University(Natural Science Edition),2003,33(1):111-114. |
| |
| Authors: | Qi Dongyuan Wang Zeyan Shao Junli |
| |
| Abstract: | The shortest path (SP) problem with constraints of node's cost and edge's cost is put forward, and it is proven to be NP complete. A mathematics programming model of this modified SP is proposed. To solve this model Lagrangean relaxation algorithm is adopted. The general algorithm steps based on subgradient optimization mathematics method are presented. In view of the weak convergence performance in this algorithm, the Lagrangean relaxation algorithm is modified in two points, i.e. determining a proper step length and choosing a better iterative direction. Computational examples show that the modified subgradient optimization algorithm for Lagrangean relaxation can reduce the iterative steps obviously, and is proved to be efficient. |
| |
| Keywords: | shortest path constraints of node's cost and edge's cost Lagrangean relaxation subgradient algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
